computation-theory

41Nhiệt

3Trả lời

Tính toán dựa trên constexpr Turing có hoàn thành không?

Chúng tôi biết rằng C++ template metaprogramming is Turing complete, nhưng preprocessor metaprogramming is not. C++ 11 cho chúng ta một dạng lập trình meta mới: tính toán các hàm constexpr. Đây có phả

6Nhiệt

1Trả lời

Chứng minh rằng tập hợp của tất cả các ngôn ngữ trên một bảng chữ cái hữu hạn là không đếm được

Đang cố gắng để làm một số sửa đổi nhưng không chắc chắn về điều này một: Prove that the set of all languages over a ﬁnite alphabet is uncountable. Tôi có cảm giác nó sẽ yêu cầu sử dụng phương pháp

14Nhiệt

2Trả lời

Sự khác biệt giữa Turing-Decidable và Co-Turing-Decidable

Tôi thực sự đấu tranh với sự hiểu biết về sự khác biệt giữa hai điều này. Từ sách giáo khoa của tôi, về cơ bản, nó mô tả sự khác biệt bằng cách nói rằng một ngôn ngữ được đồng hóa để nhận ra nếu nó bổ

7Nhiệt

1Trả lời

Does Provable == Decidable?

Trong lý thuyết tính toán là các thuật ngữ Có thể hoán đổi và có thể thay đổi được? Chúng có nghĩa là giống nhau không? Ví dụ: bạn thường thấy câu hỏi liệu có điều gì đó có thể chứng minh được gọi là

5Nhiệt

1Trả lời

Thuật toán để tạo ngữ cảnh tự do ngữ cảnh từ bất kỳ regex

Bất kỳ ai có thể phác thảo cho tôi một thuật toán có thể chuyển đổi bất kỳ regex đã cho nào thành một bộ quy tắc CFG tương đương không? tôi biết làm thế nào để giải quyết những thứ tiểu như (a | b) *:

8Nhiệt

5Trả lời

Ngữ cảnh miễn phí ngữ cảnh cho không phải palindrome

Tôi cần một CFG sẽ tạo ra các chuỗi khác với palindromes. Giải pháp đã được cung cấp và như sau (Giới thiệu về lý thuyết tính toán - Sipser) R -> XRX | S S -> aTb | bTa T -> XTX | X | <epsilon> X -

6Nhiệt

3Trả lời

Suy luận chương trình con

Có giấy nào mô tả bất kỳ thuật toán/kỹ thuật nào để suy ra các chương trình con từ một chương trình đã biên dịch không? Nói cách khác: có một thuật toán để tìm các khối mã xuất hiện nhiều lần trong ch

5Nhiệt

7Trả lời

Làm thế nào để viết một liệt kê của tất cả các chức năng tính toán?

Động lực: Tôi muốn có thể sử dụng lập trình chức năng đồ chơi bằng các ngôn ngữ không có chức năng đặt hàng đầu tiên, bằng cách sử dụng các số tự nhiên thay vì chức năng. Chức năng phổ quát là hàm f:

5Nhiệt

3Trả lời

Làm thế nào để biết máy có phải là máy Turing tương đương

Tôi đã tìm thấy bài viết trên Wikipedia là a list of Turing machine equivalents. Tuy nhiên, nó không nói một phương pháp làm thế nào để xác định xem một máy đã cho là máy Turing tương đương hay không.