2010-04-08 21 views
7

Trong mọi ngôn ngữ Turing-Complete, là nó có thể tạo ra một tácCác loại chương trình này có thể tồn tại trong mọi ngôn ngữ Turing hoàn chỉnh không?

  • biên dịch cho chính nó mà đầu tiên chạy trên một phiên dịch viết bằng một số ngôn ngữ khác và sau đó biên dịch nó là mã nguồn riêng? (Bootstrapping)

  • Trình biên dịch C++ chuẩn-Compilant xuất ra các tệp nhị phân, ví dụ: Windows?

  • Regex Parser and Evaluater?

  • Bản sao World of Warcraft? (Giả sử các ngôn ngữ được các ràng buộc API cần thiết như, ví dụ, OpenGL và mã nguồn WoW có sẵn)

(Mọi thứ ở đây lý thuyết)

Chúng ta hãy BrainF * ck như một ngôn ngữ ví dụ.

+3

tôi đang thực hiện một bản sao WoW sử dụng sed, tôi đang tìm một số nhà phát triển quan tâm – LB40

+0

Âm thanh vui nhộn như xa như tôi có thể nói (Không thực sự biết sed) Nếu bạn chuyển sang bộ xử lý 8086, tôi ở: P –

+0

Tôi cho rằng bạn tôi một phiên dịch hoặc một điều hành, vì một Compiler là một khái niệm phụ thuộc kiến ​​trúc VonNuemann? – RBarryYoung

Trả lời

2

Có, tất nhiên, tất cả những điều đó. Đó là những gì "Turing-complete" có nghĩa là, sau khi tất cả: nó có thể tính toán tất cả mọi thứ có thể được tính toán.

+0

Tôi không thể tìm thấy một tham chiếu sao lưu điều này ngay bây giờ, nhưng IIRC nó là một câu hỏi mở có hay không có những vấn đề tính toán mà không thể được giải quyết bằng một máy turing. Tôi nghĩ rằng điều này chủ yếu là do một định nghĩa mơ hồ về những gì "tính toán" thực sự có nghĩa là. – rmeador

+0

@rmeador Turing đã phát minh ra máy tính lý tưởng của mình một cách chính xác để ông có thể lý luận về những gì được và không thể tính toán được. Bài báo giới thiệu khái niệm TM được gọi là "Trên các số tính toán ..." –

+1

@Neil Butterworth - nhưng công việc của Turing về tính toán liên quan đến khía cạnh "vẫy tay", trong đó * giả định rằng mọi thứ có thể tính toán được một máy Turing, hoặc tương đương nó * định nghĩa * một thuật toán có thể tính toán như một thuật toán mà một chương trình máy Turing tồn tại. Công việc của Kleene và Giáo Hội là tương đương, và như Kleene đã nói, tất cả đều mơ hồ và trực quan. –

0

Bất kỳ thuật toán nào có thể được triển khai bằng một ngôn ngữ Turing-Complete có thể được triển khai trong bất kỳ ngôn ngữ nào khác. Câu hỏi của bạn có liên quan nhiều hơn đến các dịch vụ hệ điều hành và API phải được cung cấp thông qua ngôn ngữ được đề cập.

Tóm lại, câu trả lời là có cho tất cả các điểm trên từ quan điểm ngôn ngữ chính thức.

8

Trong mọi ngôn ngữ Turing-Complete, là nó có thể tạo ra một hoạt động ...

Nếu ngôn ngữ một Turing hoàn tất có thể làm điều đó, sau đó tất cả họ đều có thể. Theo nghĩa này, tất cả chúng đều đều "mạnh mẽ". Vì tất cả mọi thứ bạn mô tả đã tồn tại trong ít nhất một ngôn ngữ Turing-hoàn chỉnh, bất kỳ chương trình nào trong số này cũng có thể được viết bằng bất kỳ ngôn ngữ Turing hoàn chỉnh nào khác.

Tuy nhiên, chỉ vì một cái gì đó là thể không có nghĩa là nó dễ dàng , hoặc thậm chí khả thi. Đó là một sự khác biệt rất quan trọng, và đó là mấu chốt của việc tại sao các ngôn ngữ lập trình khác nhau tồn tại. Họ không phải là tất cả tốt như nhau tại làm cho các loại phần mềm cụ thể - nếu chúng được, chúng tôi sẽ chỉ cần một ngôn ngữ!

+1

Tôi không hiểu tại sao nó có thể không khả thi, nếu nó là possilbe không có nghĩa là đó là khả thi? Bạn có một ví dụ? – LB40

+0

@John +1. Hỏi: Tại sao có nhiều hơn một cơ sở dữ liệu? A: Bởi vì tất cả họ đều hút. –

+3

@LB: Khả năng không bằng tính khả thi. Đây là một ví dụ tầm thường. Hãy tưởng tượng một ngôn ngữ Turing-hoàn chỉnh, trong đó viết xuống các hướng dẫn "gán giá trị x để biểu tượng y" đòi hỏi nhiều bộ nhớ hơn tồn tại trong toàn bộ thế giới. Một ngôn ngữ như vậy làm cho nó _possible_ có thể viết các chương trình Turing-complete, nhưng nó không phải là _feasible_ để viết chúng bởi vì nó không thực tế để mã hóa thông tin bạn muốn. –

0

Lý thuyết, có. Nhưng một câu hỏi thú vị hơn nhiều là nếu nó có thể thực tế có thể cho một ngôn ngữ lập trình "bí truyền" nhất định.

-2

Mỗi ngôn ngữ Turing-Complete có thể tính toán cùng một tập hợp các hàm. Vì vậy, một ngôn ngữ hoàn chỉnh có thể làm tất cả những gì bạn đã viết bởi vì mọi thứ được tính toán với các ngôn ngữ hoàn chỉnh khác.

1

Tất cả những gì mà Turing-complete thực sự yêu cầu là bạn có thể làm toán đơn giản, có một số biến và có thể thực hiện một vòng lặp while. Hoặc bất kỳ số lượng những thứ tương đương. Nếu bạn muốn thực hiện các chương trình thực sự, bạn cần nhiều hơn một chút (đáng chú ý là syscalls) và bạn cũng phải lo lắng về hiệu quả (các máy turing có thể rất chậm ...) Về lý thuyết không có sự khác biệt giữa các hệ thống turing-equivalent, nhưng trong thực tế thì có.

Nếu có ai làm khách hàng WoW trong BF, tôi sẽ bị rất gây ấn tượng!

8

Turing-Complete chỉ hiển thị tính toán khả năng, không có gì về I/O khả năng!

+0

StackOverflow điển hình: các câu trả lời sai là vô tình bỏ phiếu-up, và các câu trả lời đúng chỉ languish trong tối tăm. – RBarryYoung

5

Không, Turing hoàn toàn không liên quan gì đến I/O và phần cứng. Tuy nhiên, bạn có thể giả vờ I/O, hệ thống phần cứng và hệ thống đồ họa tồn tại bằng cách sử dụng các biến (hoặc "băng bộ nhớ"). Trong BF, bạn có thể sử dụng 2 tế bào đầu tiên (x, y) cho "giả vờ" độ phân giải màn hình, sau đó một x lần y tế bào cho tất cả các điểm ảnh trên màn hình, sau đó tế bào tiếp theo (n) cho "giả vờ" kích thước hệ thống tập tin, sau đó tiếp theo n tế bào đối với nội dung hệ thống tập tin ...

+0

Câu trả lời đúng đầu tiên tôi đã thấy ở đây. – RBarryYoung

Các vấn đề liên quan