From Wikipedia, the free encyclopedia
Máy Turing là một mô hình toán học về thiết bị xử lý các ký tự, tuy đơn giản, nhưng có thể thực hiện được tất cả các thuật toán máy tính. Các máy Turing đã được Alan Turing trình bày vào năm 1936. Nó được xây dựng không dành cho việc trực tiếp chế tạo ra máy tính, mà là dành cho các thí nghiệm tưởng tượng để tìm hiểu về các giới hạn của việc tính toán trên máy móc. Việc nghiên cứu các tính chất của máy Turing cho biết nhiều kiến thức quan trọng trong lĩnh vực khoa học máy tính và lý thuyết về độ phức tạp tính toán.
Máy Turing mà có khả năng mô phỏng lại hoạt động của tất cả các máy Turing khác được gọi là máy Turing vạn năng (hay đơn giản là máy vạn năng). Máy vạn năng cũng đã được Alonzo Church mô tả, khi xây dựng các lý thuyết về phép tính lambda. Lý thuyết của Church và Turing được tổng kết lại trong luận đề Church-Turing. Luận đề này khẳng định mọi hàm toán học tính được thì cũng có thể dùng các máy Turing để tính, và do đó cho phép định nghĩa các khái niệm như sự tính được của hàm hay thuật toán.
Trong lý thuyết về ngôn ngữ hình thức, máy Turing có khả năng đoán nhận tất cả các ngôn ngữ sinh bởi văn phạm cấu trúc câu.
Ở dạng đơn giản và thông dụng, máy Turing có thể được mô tả với các bộ phận sau:
Trong một số mô hình, nếu máy đang ở trạng thái Si và đầu đọc đọc được ký tự Ci, nhưng chưa có quy tắc nào quy định việc hành xử của máy lúc đó, thì máy được dừng lại và không tiếp tục chạy nữa.
Trong số các trạng thái trong S, có thể quy định ra những trạng thái được gọi là trạng thái kết thúc. Trong lý thuyết về ngôn ngữ hình thức, nếu một đoạn ký tự (gọi là một từ hay một câu) ghi trên dải băng đưa máy Turing chạy từ trạng thái ban đầu đến một trong số các trạng thái kết thúc thì câu viết đó được gọi là đoán nhận bởi máy Turing đã cho.
Ngoài mô hình đã miêu tả, còn có nhiều dạng khác như dải băng chỉ có một đầu (trái hoặc phải) là vô tận; hoặc máy có nhiều dải băng, nhiều đầu đọc,... tuy nhiên tất cả các máy đó đều có hoạt động tương đương với máy đã mô tả. Cụ thể hơn, trong lý thuyết ngôn ngữ hình thức, nếu có thể xây dựng máy theo một dạng bất kỳ đoán nhận một tập hợp các từ nào đó, thì luôn có thể xây dựng máy Turing theo dạng đã mô tả ở trên đoán nhận cùng tập hợp các từ này.
Về mặt toán học, máy Turing có thể được định nghĩa bằng một bộ chứa các phần tử sau:
Ngoài ra có thể định nghĩa thêm:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.