Máy Turing là một thiết bị thực hay một khái niệm tưởng tượng?

Question

Khi tôi đang nghiên cứu về máy Turing và PDA, tôi đã nghĩ rằng thiết bị tính toán đầu tiên là máy Turing. Do đó, tôi nghĩ rằng có một máy thực tế được gọi là máy Turing và các trạng thái của nó có thể được đại diện bởi một số thiết bị đặc biệt (như flip-flops) và nó có thể chấp nhận đầu vào trong băng từ.

Do đó tôi đã hỏi nghi ngờ How input string is represented in magnetic tapes?. Nhưng bởi câu trả lời và các chi tiết được đưa ra trong cuốn sách của tôi, tôi đã biết rằng máy Turing là một số giả thuyết.

Câu hỏi của tôi là, máy Turing sẽ được triển khai như thế nào? Ví dụ, làm thế nào nó được sử dụng để kiểm tra lỗi chính tả trong bộ vi xử lý hiện tại của chúng tôi.

Máy Turing đã lỗi thời chưa? Hay họ vẫn đang được sử dụng?

Answer 1

Máy kéo không được sử dụng trong thực tế vì nhiều lý do. Đối với người mới bắt đầu, không thể xây dựng một cái, vì bạn cần tài nguyên vô hạn để xây dựng băng vô hạn. Hơn nữa, máy Turing vốn đã chậm hơn so với các mô hình tính toán khác vì bản chất tuần tự của truy cập dữ liệu của chúng. Ví dụ, các máy turing không thể nhảy vào giữa một mảng mà không đi qua tất cả các phần tử của mảng mà nó muốn bỏ qua. Trên hết, máy Turing cực kỳ khó thiết kế. Hãy thử viết một máy Turing để sắp xếp một danh sách các số nguyên 32 bit, ví dụ. (Thực ra, xin đừng. Thật là khó!)

Điều này sau đó đặt ra câu hỏi ... tại sao lại nghiên cứu máy Turing? May mắn thay, có một số lượng lớn lý do để thực hiện việc này:

1. Để giải thích về giới hạn của những gì có thể được tính toán. Vì máy Turing có khả năng mô phỏng bất kỳ máy tính nào trên hành tinh (hoặc theo luận án Church-Turing, bất kỳ thiết bị tính toán vật lý nào), nếu chúng ta có thể chỉ ra những giới hạn của những gì máy Turing có thể tính toán, có thể hy vọng được hoàn thành trên một máy tính thực sự.

2. Để chính thức hóa định nghĩa của thuật toán. Tại sao tìm kiếm nhị phân một thuật toán trong khi câu lệnh "đoán câu trả lời" thì không? Để trả lời câu hỏi này, chúng ta phải có một mô hình chính thức về máy tính là gì và thuật toán là gì.Có máy Turing như là một mô hình tính toán cho phép chúng tôi xác định một cách chặt chẽ thuật toán là gì. Không ai thực sự muốn dịch thuật toán sang định dạng, nhưng khả năng làm như vậy sẽ cho phép lĩnh vực thuật toán và lý thuyết tính toán là nền tảng toán học vững chắc.

3. Để chính thức hóa các định nghĩa của thuật toán xác định và không xác định. Có lẽ câu hỏi mở lớn nhất trong khoa học máy tính hiện nay là câu hỏi liệu P = NP. Câu hỏi này chỉ có ý nghĩa nếu bạn có một định nghĩa chính thức cho P và NP, và chúng lần lượt yêu cầu định nghĩa nếu tính toán xác định và nndeterministic (mặc dù về mặt kỹ thuật chúng có thể được định nghĩa bằng logic thứ hai). Có máy Turing sau đó cho phép chúng ta nói về các vấn đề quan trọng trong NP, cùng với việc cho chúng ta một cách để tìm các vấn đề NP-complete. Ví dụ, bằng chứng rằng SAT là NP-complete sử dụng thực tế là SAT có thể được sử dụng để mã hóa một máy Turing và nó thực hiện trên một đầu vào.

Hy vọng điều này sẽ hữu ích!

Answer 2

Đây là thiết bị khái niệm không thể thực hiện được (do yêu cầu băng vô hạn). Một số người đã xây dựng hiện thực vật lý của một máy Turing, nhưng nó không phải là một máy Turing thực sự do hạn chế về thể chất.

Dưới đây là một đoạn video của một: http://www.youtube.com/watch?v=E3keLeMwfHY

Answer 3

Đó là một máy lý thuyết, đoạn sau đây từ Wikipedia

máy

Một Turing là một thiết bị lý thuyết đó thao túng ký hiệu trên một dải băng theo một bảng quy tắc. Mặc dù đơn giản của nó, một máy Turing có thể được điều chỉnh để mô phỏng logic của bất kỳ thuật toán máy tính nào, và đặc biệt hữu ích trong việc giải thích các chức năng của một CPU bên trong một máy tính. Blockquote

máy này cùng với các máy khác như máy không xác định (không tồn tại trong thực tế) là rất hữu ích trong việc tính toán phức tạp và chứng minh rằng một thuật toán là khó hơn khác hoặc một thuật toán không thể giải quyết được .. .etc

Answer 4

Máy bảo dưỡng không chính xác là máy vật lý, thay vào đó chúng là máy khái niệm cơ bản. Turing khái niệm là giả thuyết và điều này là rất khó thực hiện trong thế giới thực vì chúng tôi yêu cầu băng vô hạn cho giải pháp nhỏ và dễ dàng quá.