Máy Turing làm gì? Máy Turing: mô tả và ví dụ về máy Turing. Chức năng của máy Turing

Từ trước đến nay, chúng ta có thể tham khảo kinh nghiệm của lập trình viên khi nói về thuật toán, chương trình, trình thông dịch, thực thi từng bước, v.v. Điều này cho phép chúng tôi bỏ qua các chi tiết về việc xây dựng một số thuật toán nhất định với lý do là người đọc sẽ dễ dàng khôi phục chúng (hoặc ít nhất tin rằng không phải người đọc nào trong đời mình cũng viết được trình thông dịch Pascal bằng Pascal).

Nhưng trong một số trường hợp điều này là không đủ. Ví dụ: giả sử chúng ta muốn chứng minh tính không thể giải quyết được về mặt thuật toán của một số vấn đề, định nghĩa của nó không nói lên điều gì về chương trình (ví dụ, trong phần này, chúng ta sẽ chứng minh tính không thể giải quyết được của bài toán đẳng thức của các từ trong nửa nhóm được xác định bởi máy phát điện và quan hệ). Nó thường được thực hiện như thế này. Chúng tôi chứng minh rằng bài toán dừng dẫn đến bài toán này. Để làm điều này, chúng tôi lập mô hình hoạt động của một thuật toán tùy ý theo vấn đề đang được xem xét (điều này có nghĩa là gì sẽ được hiểu rõ trong ví dụ bên dưới). Đồng thời, điều quan trọng đối với chúng tôi là định nghĩa của thuật toán càng đơn giản càng tốt.

Vậy kế hoạch của chúng tôi là thế này. Chúng ta sẽ mô tả một loại máy có thể định nghĩa khá đơn giản (nó có thể được chọn theo nhiều cách khác nhau; chúng ta sẽ sử dụng cái gọi là máy Turing), sau đó tuyên bố rằng mọi chức năng tính toán đều có thể được tính toán trên một máy như vậy, và sau đó chỉ ra rằng câu hỏi về việc dừng máy Turing có thể được rút gọn thành vấn đề về sự bình đẳng của các từ trong nửa nhóm.

Một lý do khác khiến các mô hình tính toán đơn giản lại quan trọng (có nhiều loại máy Turing, máy địa chỉ, v.v.) liên quan đến lý thuyết về độ phức tạp tính toán, khi chúng ta bắt đầu quan tâm đến thời gian dẫn các chương trình. Nhưng câu hỏi này vượt xa lý thuyết cổ điển về thuật toán.

Máy Turing: định nghĩa

Máy turing có vô cực theo cả hai hướng băng, được chia thành các ô vuông ( tế bào). Mỗi ô có thể chứa một số ký hiệu từ một tập hữu hạn cố định (đối với một máy nhất định) được gọi là bảng chữ cái của chiếc máy này. Một trong các ký tự của bảng chữ cái được tô sáng và được gọi là "khoảng trắng", người ta cho rằng ban đầu toàn bộ băng trống, nghĩa là chứa đầy khoảng trắng.

Máy Turing có thể thay đổi nội dung của băng bằng cách sử dụng đầu đọc và ghi đặc biệt. cái đầu, di chuyển dọc theo băng. Tại mỗi thời điểm, đầu ở trong một trong các tế bào. Máy Turing nhận thông tin từ đầu về ký hiệu mà nó nhìn thấy và tùy thuộc vào điều này (và trạng thái bên trong của nó) sẽ quyết định phải làm gì, nghĩa là ghi ký hiệu nào vào ô hiện tại và di chuyển đến đâu sau đó (trái, đúng, hoặc ở lại hiện trường). Đồng thời, trạng thái bên trong của máy cũng thay đổi (chúng ta giả sử rằng máy, không tính băng, có bộ nhớ hữu hạn, tức là có số lượng hữu hạn các trạng thái bên trong). Chúng ta cũng cần phải thống nhất nơi chúng ta bắt đầu và thời điểm chúng ta kết thúc công việc.

Vì vậy, để xác định máy Turing, bạn cần chỉ định các đối tượng sau:

Bảng chuyển tiếp được sắp xếp như sau: đối với mỗi cặp, một bộ ba được chỉ định. Ở đây sự dịch chuyển là một trong các số -1 (ở bên trái), 0 (tại chỗ) và 1 (ở bên phải). Do đó, bảng chuyển đổi là một hàm có kiểu S x A -> S x A x (-1,0,1) được xác định trên các cặp mà trạng thái không phải là cuối cùng.

Việc còn lại là mô tả hoạt động của máy Turing. Tại mỗi thời điểm đều có một số cấu hình, bao gồm nội dung của băng (nói một cách chính thức, nội dung của băng là ánh xạ tùy ý Z -> A), vị trí hiện tại của đầu (một số số nguyên) và trạng thái hiện tại của máy (phần tử S). Việc chuyển đổi cấu hình sang cấu hình tiếp theo diễn ra theo các quy tắc tự nhiên: chúng ta xem trong bảng những việc cần làm đối với một trạng thái nhất định và đối với một ký hiệu nhất định, tức là chúng ta tìm ra trạng thái mới của máy, thay đổi cấu hình đó. ký hiệu đến biểu tượng đã chỉ định rồi di chuyển đầu sang trái, sang phải hoặc giữ nguyên. Hơn nữa, nếu trạng thái mới là một trong những trạng thái cuối cùng thì hoạt động của máy sẽ kết thúc. Vẫn còn phải thống nhất về cách chúng tôi cung cấp thông tin cho đầu vào của máy và những gì được coi là kết quả công việc của nó. Chúng ta sẽ giả sử rằng bảng chữ cái của máy, ngoài khoảng trắng, còn chứa các ký tự 0 và 1 (và có thể một số ký tự khác). Đầu vào và đầu ra của máy sẽ là các chuỗi hữu hạn số 0 và số 1 (từ nhị phân). Từ đầu vào được ghi trên một băng trống, phần đầu của máy được đặt vào ô đầu tiên, máy được đưa về trạng thái ban đầu và khởi động. Nếu máy dừng, kết quả là một từ nhị phân, có thể đọc từ vị trí đầu và di chuyển sang phải (cho đến khi xuất hiện ký tự khác 0 và 1).

Do đó, bất kỳ máy Turing nào cũng xác định một phần hàm nào đó trên các từ nhị phân. Đó là điều tự nhiên khi gọi tất cả các chức năng như vậy tính toán được trên máy Turing.

Máy Turing: thảo luận

Tất nhiên, định nghĩa của chúng tôi chứa đựng nhiều chi tiết cụ thể có thể thay đổi được. Ví dụ, một cuộn băng chỉ có thể kéo dài vô tận theo một hướng. Bạn có thể tặng chiếc xe hai dải ruy băng. Chúng ta có thể coi máy có thể viết một ký tự mới hoặc di chuyển, nhưng không thể thực hiện cả hai. Bạn có thể giới hạn bảng chữ cái, ví dụ như nó phải có chính xác 10 ký tự. Bạn có thể yêu cầu rằng cuối cùng không có gì trên băng ngoại trừ kết quả của công việc (các ô còn lại phải trống). Tất cả những điều trên và nhiều thay đổi khác không làm thay đổi loại hàm có thể tính toán được trên máy Turing. Tất nhiên, cũng có một số thay đổi vô hại. Ví dụ, nếu bạn cấm ô tô di chuyển sang trái, thì điều này sẽ thay đổi hoàn toàn mọi thứ; về cơ bản, cuốn băng sẽ trở nên vô dụng vì sẽ không thể quay lại bản ghi cũ nữa.

Làm thế nào để bạn biết những thay đổi nào là vô hại và những thay đổi nào là không? Rõ ràng, ở đây cần có một số kinh nghiệm lập trình thực tế trên máy Turing, ít nhất là một chút. Sau này, bạn có thể tưởng tượng khả năng của máy mà không cần viết ra toàn bộ chương trình mà chỉ được hướng dẫn bằng mô tả gần đúng. Ví dụ: chúng tôi sẽ mô tả một máy nhân đôi từ đầu vào (tạo ra từ XX nếu đầu vào là từ X).

Nếu máy thấy có khoảng trắng (từ đầu vào trống) thì máy sẽ ngừng hoạt động. Nếu không, nó sẽ ghi nhớ ký tự hiện tại và đánh dấu (trong bảng chữ cái, ngoài các ký tự 0 và 1, còn có các “biến thể được đánh dấu” và ) của chúng. Sau đó, cô ấy di chuyển sang bên phải đến một ô trống, sau đó cô ấy viết một bản sao của biểu tượng đã ghi nhớ vào đó. Sau đó cô ấy di chuyển sang trái cho đến khi được đánh dấu; Sau khi vùi mình vào dấu ấn, anh ta lùi lại và ghi nhớ ký tự tiếp theo, v.v. cho đến khi sao chép được toàn bộ từ.

Với một số kinh nghiệm, bạn có thể thấy đằng sau tất cả các cụm từ này là các phần cụ thể của chương trình dành cho máy Turing. Ví dụ: cụm từ “nhớ ký hiệu và di chuyển sang bên phải” có nghĩa là có hai nhóm trạng thái, một nhóm dành cho tình huống ghi nhớ số 0, nhóm còn lại khi nhớ một số 1 và trong mỗi nhóm chuyển động sang trạng thái khác. bên phải được lập trình cho ô trống đầu tiên.

Kinh nghiệm thêm một chút, bạn có thể hiểu rằng cách mô tả này có sai sót, không có cơ chế dừng khi sao chép toàn bộ từ, vì bản sao của các ký tự không khác gì ký tự của từ gốc. Cách sửa lỗi cũng rõ ràng: bạn cần viết các ký tự đặc biệt và dưới dạng bản sao, và ở giai đoạn cuối, hãy xóa tất cả các dấu.

77 . Chứng minh rằng hàm đảo ngược, làm đảo ngược một từ, có thể tính toán được bằng máy Turing.

Một ví dụ khác về lý luận không chính thức: hãy giải thích tại sao không thể sử dụng các ký tự bổ sung ngoài 0, 1 và ký tự trống. Giả sử có một chiếc máy có bảng chữ cái lớn gồm N ký tự. Hãy xây dựng một máy mới mô phỏng hoạt động của máy cũ, nhưng mỗi ô của máy cũ sẽ tương ứng với một khối k ô của máy mới. Kích thước khối (số k) sẽ được cố định sao cho trong khối tất cả các ký tự của bảng chữ cái lớn có thể được mã hóa bằng số 0 và số 1. Các ký tự gốc 0 , 1 và trống sẽ được mã hóa thành 0 theo sau là (k-1) ký tự trống, 1 theo sau là (k-1) ký tự trống và một nhóm k ký tự trống. Đầu tiên, bạn cần di chuyển các chữ cái của từ đầu vào cách nhau một khoảng k, việc này có thể được thực hiện mà không cần thêm ký hiệu (khi đến chữ cái bên ngoài, hãy di chuyển nó ra xa, sau đó khi đến chữ cái tiếp theo, hãy di chuyển nó và chữ cái ngoài cùng). một, v.v.); bạn chỉ cần hiểu rằng bạn có thể xác định phần cuối của một từ là một vị trí được theo sau bởi hơn k ký tự trống. Rõ ràng, trong quá trình này, chúng ta phải lưu trữ một lượng thông tin hữu hạn trong bộ nhớ, vì vậy điều này là có thể. Sau đó, có thể mô phỏng từng bước hoạt động của máy ban đầu và để làm được điều này, bộ nhớ hữu hạn (e số hữu hạn trạng thái) cũng là đủ, vì chỉ một vùng lân cận nhỏ của phần đầu của máy mô phỏng là đủ. quan trọng với chúng tôi. Cuối cùng, chúng ta cần nén kết quả lại.

Để kết thúc cuộc thảo luận, chúng tôi trình bày lập luận đã hứa ở trên ủng hộ thực tế là mọi hàm tính toán đều có thể tính toán được trên máy Turing. Hãy để có một chức năng mà một người có thể tính toán. Đồng thời, đương nhiên anh ta phải sử dụng bút chì và giấy, vì lượng thông tin số lượng anh ta có thể lưu trữ “trong tâm trí” là có hạn. Chúng ta sẽ giả định rằng anh ta viết trên những tờ giấy riêng biệt. Ngoài tờ giấy hiện tại còn có một chồng giấy ở bên phải và một chồng giấy ở bên trái; Bạn có thể đặt trang tính hiện tại vào bất kỳ trang tính nào trong số chúng, sau khi hoàn thành công việc với nó và lấy trang tiếp theo từ chồng trang kia. Một người đàn ông có một cây bút chì và một cục tẩy. Vì các chữ cái rất nhỏ không thể nhìn thấy được nên số lượng trạng thái có thể phân biệt rõ ràng của trang tính là hữu hạn và chúng ta có thể giả sử rằng tại mỗi thời điểm, một chữ cái từ một bảng chữ cái hữu hạn nào đó (mặc dù rất lớn) được viết trên trang tính. Một người cũng có trí nhớ hữu hạn, vì vậy trạng thái của anh ta là một phần tử của một tập hợp hữu hạn nào đó. Trong trường hợp này, bạn có thể lập một bảng trong đó ghi lại cách công việc của anh ta trên một tờ giấy với nội dung nhất định, bắt đầu ở một trạng thái nhất định, sẽ kết thúc (những gì sẽ có trên trang tính, một người sẽ ở trạng thái nào). và tờ tiếp theo sẽ được lấy từ gói nào). Giờ đây rõ ràng là hành động của con người tương ứng chính xác với hoạt động của máy Turing với bảng chữ cái lớn (nhưng hữu hạn) và số lượng lớn (nhưng hữu hạn) các trạng thái bên trong.

Vào nửa đầu thế kỷ 20, khi những chiếc máy tính đầu tiên được phát minh. Tuy nhiên, cùng với những cỗ máy hữu hình về mặt vật lý, những cỗ máy ý tưởng cũng xuất hiện. Một trong số đó là “Máy Turing” - một thiết bị điện toán trừu tượng được phát minh vào năm 1936 bởi Alan Turing, một nhà khoa học được coi là một trong những người sáng lập ngành khoa học máy tính.

Tầm nhìn của ông mở rộng từ lý thuyết lượng tử và nguyên lý tương đối đến tâm lý học và khoa học thần kinh. Và như một cách để biết và truyền tải kiến ​​thức của mình, Turing đã sử dụng bộ máy toán học và logic. Ông đã tìm ra giải pháp cho những vấn đề tưởng chừng như không thể giải quyết được, nhưng lại đam mê nhất với ý tưởng về một “Cỗ máy vạn năng” có khả năng tính toán mọi thứ về nguyên tắc có thể tính toán được.

Tuổi thơ, học vấn, sở thích

Alan Turing sinh ra ở đó vào ngày 23 tháng 6 năm 1912. Anh ấy có một người anh trai, John. Julius Turing vẫn tiếp tục phục vụ chính phủ và cha mẹ của Alan phải thường xuyên đi lại giữa Hastings và Ấn Độ, để lại hai con trai của họ cho một cặp vợ chồng quân nhân đã nghỉ hưu chăm sóc. Turing đã bộc lộ những dấu hiệu thiên tài ngay từ khi còn nhỏ.

Khi còn nhỏ, Alan và anh trai John hiếm khi gặp cha mẹ - cha của họ phục vụ ở Ấn Độ cho đến năm 1926; Những đứa trẻ vẫn ở Anh và sống dưới sự chăm sóc của các nhà riêng, nhận được sự nuôi dạy nghiêm khắc của người Anh phù hợp với vị trí của chúng trên bậc thang xã hội. Là một phần của nền giáo dục như vậy, việc nghiên cứu các nguyên tắc cơ bản của khoa học tự nhiên thực sự không được cung cấp.

Cậu bé Alan có một tâm trí rất tò mò. Tự học đọc từ năm 6 tuổi, anh đã xin phép giáo viên của mình để đọc những cuốn sách khoa học phổ thông.

Năm 11 tuổi, cậu đã thực hiện những thí nghiệm hóa học khá thành thạo, cố gắng chiết xuất iốt từ tảo. Tất cả những điều này khiến mẹ anh vô cùng lo lắng, bà sợ rằng sở thích của con trai bà, đi ngược lại với sự giáo dục truyền thống, sẽ ngăn cản anh đăng ký vào Trường Công (một cơ sở giáo dục tư thục đóng cửa ở Anh dành cho nam sinh, việc học tập là bắt buộc đối với trẻ em ở các vùng nông thôn). quý tộc). Nhưng nỗi sợ hãi của cô là vô ích: Alan đã có thể vào Trường Công lập Sherborne danh tiếng.

Năm sáu tuổi, Alan Turing đến trường St. Michael ở Hastings, nơi hiệu trưởng ngay lập tức ghi nhận tài năng của anh. Năm 1926, ở tuổi 13, Turing theo học trường tư thục nổi tiếng Sherborne ở Sherborne, Dorset. Ngày đầu tiên đến trường của anh trùng với cuộc Tổng đình công năm 1926. Vì vậy, Turing phải đạp xe quãng đường khoảng 100 km từ Southampton đến Sherborne, qua đêm tại một khách sạn trên đường đi.

Niềm đam mê toán học của Turing không nhận được nhiều sự ủng hộ từ các giáo viên tại Trường Sherborne, nơi họ chú ý nhiều hơn đến nhân văn. Hiệu trưởng nhà trường viết cho phụ huynh: “Tôi hy vọng rằng cháu sẽ không cố ngồi trên hai chiếc ghế cùng một lúc. Nếu anh ta có ý định tiếp tục học ở một trường tư thục thì anh ta phải phấn đấu để có được một “sự giáo dục”. Nếu anh ta chỉ muốn trở thành một “chuyên gia khoa học” thì học trường tư là một sự lãng phí thời gian đối với anh ta.”

Sự thành công ở trường của Alan được chứng minh một cách hùng hồn qua tạp chí của lớp, trong đó bạn có thể tìm thấy những bài viết sau đây chẳng hạn:

Tôi có thể nhắm mắt làm ngơ trước những bài viết của anh ấy, mặc dù trong đời tôi chưa bao giờ thấy điều gì khủng khiếp hơn thế, tôi cố gắng chịu đựng sự sơ suất không thể lay chuyển và sự siêng năng tục tĩu của anh ấy; nhưng tôi vẫn không thể chịu đựng được sự ngu ngốc đáng kinh ngạc trong những phát biểu của anh ấy trong một cuộc thảo luận hoàn toàn lành mạnh về Tân Ước.

Năm 1928, ở tuổi 16, Turing làm quen với công trình của Einstein, công trình mà ông hiểu đến mức có thể đoán được từ văn bản về những nghi ngờ của Einstein về tính khả thi của các Định luật Newton, vốn không được nêu rõ ràng trong bài báo. .

Trường đại học

Đại học Cambridge, nơi được các quốc vương Anh ban tặng những đặc quyền, từ lâu đã nổi tiếng với truyền thống tự do và tinh thần tự do tư duy luôn ngự trị trong các bức tường của trường. Tại đây Turing đã tìm thấy - có lẽ là lần đầu tiên - ngôi nhà thực sự của mình, nơi ông có thể cống hiến hết mình cho khoa học.

Vị trí chính trong cuộc đời ông được đảm nhận bởi việc nghiên cứu nhiệt tình các ngành khoa học mà ông rất quan tâm - toán học và vật lý lượng tử. Những năm đó là thời kỳ phát triển nhanh chóng của vật lý lượng tử, và Turing đã làm quen với công trình mới nhất trong lĩnh vực này trong những năm sinh viên của mình. Ông rất ấn tượng với cuốn sách “Cơ sở toán học của cơ học lượng tử” của John von Neumann, trong đó ông tìm thấy câu trả lời cho nhiều câu hỏi mà ông quan tâm từ lâu.

Khi đó Turing có lẽ không biết rằng vài năm sau von Neumann sẽ mời ông vào học tại Princeton, một trong những trường đại học nổi tiếng nhất nước Mỹ. Thậm chí sau này, von Neumann, giống như Turing, còn được gọi là “cha đẻ của khoa học máy tính”. Nhưng sau đó, vào đầu những năm 30 của thế kỷ XX, mối quan tâm khoa học của cả hai nhà khoa học xuất sắc trong tương lai đều không còn ở máy tính - cả Turing và von Neumann đều chủ yếu tham gia vào các vấn đề toán học “thuần túy”.

Turing xuất thân từ một gia đình quý tộc, nhưng chưa bao giờ là một “người có thẩm mỹ”: Giới chính trị và văn học Cambridge xa ​​lạ với ông. Anh ấy thích nghiên cứu môn toán yêu thích của mình và trong thời gian rảnh rỗi để tiến hành các thí nghiệm hóa học và giải các câu đố cờ vua.

Trong khi thực hiện các thí nghiệm hóa học, anh ấy đã chơi một trò chơi đặc biệt “Đảo sa mạc” do chính anh ấy phát minh ra. Mục tiêu của trò chơi là thu được nhiều loại hóa chất “hữu ích” khác nhau từ “vật liệu ngẫu hứng” - bột giặt, nước rửa chén, mực và các “hóa chất gia dụng” tương tự.

Anh cũng tìm thấy sự thư giãn trong các môn thể thao cường độ cao như chèo thuyền và chạy. Chạy marathon sẽ vẫn là sở thích thực sự đam mê của anh ấy trong suốt quãng đời còn lại.

Turing hoàn thành xuất sắc khóa học kéo dài 4 năm của mình. Một trong những tác phẩm của ông, dành cho lý thuyết xác suất, đã được trao giải thưởng đặc biệt và ông được bầu vào hiệp hội khoa học của King's College. Năm 1935, Turing xuất bản “Sự tương đương của tính chu kỳ gần trái và phải”, trong đó ông đơn giản hóa ý tưởng của von Neumann trong lý thuyết nhóm liên tục, một lĩnh vực cơ bản của toán học hiện đại. Có vẻ như anh ấy sẽ có một sự nghiệp thành công với tư cách là một giảng viên Cambridge hơi lập dị làm việc trong lĩnh vực toán học “thuần túy”.

Tuy nhiên, Turing không bao giờ bị giữ trong bất kỳ “khuôn khổ” nào. Không ai có thể đoán trước được bài toán kỳ lạ nào sẽ đột nhiên thu hút anh ta, và anh ta có thể nghĩ ra cách phi thường về mặt toán học nào để giải nó.

Ngoài ra, Alan còn tham dự các bài giảng của Ludwig Wittenstein tại Cambridge. Wittenstein khẳng định một lý thuyết về tính không nhất quán của toán học. Theo ông, toán học không tìm kiếm sự thật mà tự nó tạo ra nó. Alan không đồng ý với điều này và tranh cãi rất nhiều với Ludwig. Turing ủng hộ "chủ nghĩa hình thức" - một phong trào triết học toán học không yêu cầu dịch chính xác các từ và bị giới hạn ở ý nghĩa gần đúng. Và Ludwig đang tìm kiếm sự chính xác tuyệt đối.

Khi còn học đại học, Alan Turing đã nghiên cứu những kiến ​​thức cơ bản về mật mã - tức là giải mã dữ liệu. Điều này rất hữu ích trong Thế chiến thứ hai, khi nhà khoa học này nghiên cứu giải mã các tin nhắn của Đức.

Máy turing

Ông đã chứng minh rằng một cỗ máy như vậy sẽ có khả năng thực hiện bất kỳ phép tính toán học nào có thể được biểu diễn dưới dạng thuật toán. Turing tiếp tục chỉ ra rằng không có giải pháp nào cho bài toán Entscheidungs ​​bằng cách trước tiên chứng minh rằng Vấn đề dừng là không thể giải quyết được đối với máy Turing: nói chung, không thể xác định bằng thuật toán liệu một máy Turing nhất định có bao giờ dừng hay không.

Mặc dù chứng minh của Turing được công bố ngay sau chứng minh tương đương của Alonzo Church, sử dụng phép tính Lambda, nhưng bản thân Turing lại không quen thuộc với nó. Cách tiếp cận của Alan Turing được coi là dễ tiếp cận và trực quan hơn. Ý tưởng về một “Cỗ máy vạn năng” có khả năng thực hiện các chức năng của bất kỳ máy nào khác, hay nói cách khác, tính toán mọi thứ có thể tính toán được về nguyên tắc là cực kỳ độc đáo. Von Neumann thừa nhận rằng khái niệm về máy tính hiện đại được dựa trên tác phẩm này của Alan Turing. Máy Turing vẫn là đối tượng nghiên cứu chính trong lý thuyết thuật toán.

Đối với câu hỏi: “Máy Turing là gì và nó liên quan gì đến lập trình?” Một người dùng Toster đã trả lời:

Trước hết, đây là định nghĩa chính thức của thuật toán. Một vấn đề được coi là có thể giải được bằng thuật toán khi và chỉ khi giải pháp của nó có thể được lập trình bằng máy Turing (hoặc một số phương pháp tương đương khác). Định nghĩa này làm cho nó có thể, ví dụ, trình bày các vấn đề không thể giải quyết bằng thuật toán. Cho phép bạn giới thiệu khái niệm về ngôn ngữ "Turing-Complete" - nếu máy Turing có thể được triển khai bằng một ngôn ngữ, thì bất kỳ thuật toán nào cũng có thể được viết bằng ngôn ngữ đó (bộ tiền xử lý của ngôn ngữ C không phải như vậy, nhưng C# thì có).

Nói chung, MT là một cách để xác định một loại thuật toán nhất định:

Một số vấn đề có thể được giải quyết bằng máy trạng thái hữu hạn;
- một số sẽ yêu cầu máy trạng thái có bộ nhớ ngăn xếp;
- đối với những người khác, máy Turing là đủ;
- đối với phần còn lại, cần phải có sự mặc khải thiêng liêng hoặc các phương pháp phi thuật toán khác.

Vào tháng 6 năm 1938, Turing bảo vệ luận án tiến sĩ của mình, “Hệ thống logic dựa trên số thứ tự”, trong đó đưa ra ý tưởng về việc rút gọn Turing, bao gồm việc kết hợp máy Turing với một nhà tiên tri. Điều này cho phép chúng ta khám phá những vấn đề không thể giải quyết chỉ bằng máy Turing.

Phân tích mật mã

“Bletchley Park cần một tài năng đặc biệt, một thiên tài xuất chúng, và thiên tài của Turing chính là điều đó.”

Từ tháng 9 năm 1938, Turing làm việc bán thời gian cho GCHQ, một tổ chức của Anh chuyên phá mã. Cùng với Dilly Knox, anh ấy đã tham gia vào việc giải mã Enigma. Ngay sau cuộc họp ở Warsaw vào tháng 7 năm 1939, tại đó Cục Mật mã Ba Lan đã cung cấp cho Anh và Pháp các chi tiết về các kết nối trong rôto Enigma và phương pháp giải mã các thông điệp, Turing và Knox đã bắt đầu công việc của họ bằng cách giải quyết vấn đề một cách triệt để hơn. vấn đề.

Phương pháp của Ba Lan dựa trên những thiếu sót trong quy trình chỉ báo, mà người Đức đã sửa chữa vào tháng 5 năm 1940. Cách tiếp cận của Turing tổng quát hơn và dựa trên phương pháp liệt kê các chuỗi văn bản nguồn, nhờ đó ông đã phát triển đặc tả chức năng Bombe ban đầu.

Một máy được chế tạo từ thông số kỹ thuật này đã tra cứu các cài đặt có thể được sử dụng để mã hóa thông báo (thứ tự rô-to, vị trí rô-to, kết nối bảng vá lỗi) dựa trên văn bản gốc đã biết. Đối với mỗi cài đặt rôto có thể có (có 10^19 trạng thái hoặc 10^22 trong phiên bản được sử dụng trên tàu ngầm), máy đã đưa ra một loạt giả định logic dựa trên văn bản gốc (nội dung và cấu trúc của nó).

Tiếp theo, máy xác định mâu thuẫn, loại bỏ bộ tham số và chuyển sang bộ tham số tiếp theo. Vì vậy, hầu hết các tập hợp có thể đã bị loại bỏ và chỉ còn lại một số lựa chọn để phân tích kỹ lưỡng.
Chiếc máy đầu tiên được đưa vào hoạt động vào ngày 18 tháng 3 năm 1940. Việc tìm kiếm chìa khóa được thực hiện bằng trống cơ quay, kèm theo âm thanh tương tự như tiếng tích tắc của đồng hồ.

Đặc điểm kỹ thuật của Bom chỉ là thành tựu đầu tiên trong năm thành tựu lớn của Turing trong lĩnh vực giải mã quân sự.

Nhà khoa học cũng xác định quy trình chỉ thị của Hải quân Đức; đã phát triển một cách hiệu quả hơn để sử dụng Bombe, dựa trên phân tích thống kê và được gọi là "Banburismus"; phương pháp xác định các thông số bánh xe của máy Lorenz, được gọi là “Thuringerie”; Khi chiến tranh kết thúc, Turing đã phát triển máy xáo trộn giọng nói di động Delilah.

Phương pháp thống kê nhằm tối ưu hóa việc nghiên cứu các xác suất khác nhau trong quá trình giải mật mã mà Turing đã sử dụng là một từ mới trong khoa học. Turing đã viết hai bài báo: “Bài báo về khả năng áp dụng phương pháp tiếp cận xác suất đối với phân tích mật mã” và “Bài báo về thống kê và lặp lại”, có giá trị đối với GCCS và sau này là GCHQ (Trụ sở Truyền thông Chính phủ) đến nỗi chúng chưa được phát hành vào Lưu trữ Quốc gia cho đến tháng 4 năm 2012, ngay trước lễ kỷ niệm 100 năm ngày sinh của nhà khoa học. Một quan chức của GCHQ cho biết thực tế này cho thấy tầm quan trọng chưa từng có của công việc này.

Turing cũng tham gia vào việc phát triển mật mã cho thư từ giữa Churchill và Roosevelt, trải qua khoảng thời gian từ tháng 11 năm 1942 đến tháng 3 năm 1943 tại Hoa Kỳ.

Năm 1945, Turing được Vua George VI trao tặng Huân chương OBE vì nghĩa vụ quân sự của ông, nhưng sự thật này vẫn được giữ bí mật trong nhiều năm.

Những năm sau chiến tranh

Mặc dù việc xây dựng ACE là khả thi, nhưng sự bí mật xung quanh Công viên Blatchley đã dẫn đến sự chậm trễ trong quá trình bắt đầu công việc, khiến Turing thất vọng.

Turing trải qua năm học 1947–1948 tại Cambridge. Trong khi Alan Turing ở Cambridge, Pilot ACE được chế tạo khi ông vắng mặt.

Franklin ACE 1200

Ông hoàn thành chương trình đầu tiên vào ngày 10 tháng 5 năm 1950. Mặc dù phiên bản đầy đủ của ACE chưa bao giờ được tạo ra nhưng một số máy tính có nhiều điểm tương đồng với nó, chẳng hạn như DEUCE và Bendix G-15.

Vào tháng 5 năm 1948, ông nhận được lời đề nghị đảm nhận vị trí giáo viên và phó giám đốc phòng thí nghiệm máy tính tại Đại học Manchester, nơi vào thời điểm đó đã dẫn đầu trong việc phát triển công nghệ máy tính ở Anh.

Năm 1948, Alan cùng với đồng nghiệp cũ của mình bắt đầu viết một chương trình cờ vua cho một chiếc máy tính lúc đó chưa tồn tại.

Cùng năm đó, Turing đã phát minh ra phương pháp phân rã LU, được sử dụng để giải các hệ phương trình tuyến tính, ma trận nghịch đảo và tính định thức.

Kiểm tra Turing

Đồng thời, Turing tiếp tục nghiên cứu các vấn đề toán học trừu tượng hơn, và trong tác phẩm "Máy tính và trí thông minh" (Tạp chí Mind, tháng 10 năm 1950), ông đã đề cập đến vấn đề trí tuệ nhân tạo và đề xuất một thí nghiệm mà sau này được gọi là Thí nghiệm Turing. Bài kiểm tra.

Ý tưởng của ông là một máy tính có thể được coi là “suy nghĩ” nếu người tương tác với nó không thể phân biệt được máy tính với người khác trong quá trình giao tiếp. Trong tác phẩm này, Turing gợi ý rằng thay vì cố gắng tạo ra một chương trình mô phỏng tâm trí của người lớn, sẽ dễ dàng hơn nhiều khi bắt đầu với tâm trí của một đứa trẻ và sau đó huấn luyện nó. CAPTCHA, dựa trên bài kiểm tra Turing ngược, được sử dụng rộng rãi trên Internet.

Năm 1951, Turing được bầu làm thành viên của Hiệp hội Hoàng gia Luân Đôn.

Trong công thức ban đầu, “Thử nghiệm Turing” giả định một tình huống trong đó hai người, một nam và một nữ, giao tiếp qua một kênh nào đó loại trừ khả năng nhận biết giọng nói của một người thứ ba cách họ một bức tường, người này cố gắng xác định giới tính của từng người đối thoại bằng các câu hỏi gián tiếp; trong trường hợp này, người đàn ông cố gắng làm người hỏi bối rối, và người phụ nữ giúp người hỏi tìm ra sự thật.

Câu hỏi đặt ra là liệu một cỗ máy có thể tham gia thành công vào “trò chơi bắt chước” này thay vì con người hay không (liệu người hỏi có thường xuyên mắc sai lầm trong kết luận của mình hay không). Sau đó, một hình thức kiểm tra đơn giản hóa đã trở nên phổ biến, trong đó nó xác định liệu một người, giao tiếp trong tình huống tương tự với một người đối thoại nhất định, có thể xác định xem anh ta đang giao tiếp với người khác hay với một thiết bị nhân tạo.

Thí nghiệm tưởng tượng này có một số hậu quả cơ bản. Đầu tiên, ông đề xuất một số tiêu chí hoạt động để trả lời câu hỏi “Máy móc có thể suy nghĩ được không?”

Thứ hai, tiêu chí này hóa ra mang tính ngôn ngữ: câu hỏi cụ thể đã được thay thế rõ ràng bằng câu hỏi liệu máy có thể giao tiếp đầy đủ với con người bằng ngôn ngữ tự nhiên hay không. Turing đã viết trực tiếp về sự thay đổi trong công thức, đồng thời bày tỏ sự tin tưởng rằng “phương pháp hỏi đáp phù hợp để bao quát hầu hết mọi lĩnh vực hoạt động của con người mà chúng tôi muốn đưa vào xem xét”.

Hậu quả của điều này là vai trò quan trọng của nghiên cứu về mô hình hóa sự hiểu biết và sản xuất ngôn ngữ tự nhiên trong sự phát triển hơn nữa của trí tuệ nhân tạo, ít nhất là cho đến những năm 1980. Năm 1977, P. Winston, giám đốc phòng thí nghiệm trí tuệ nhân tạo tại Viện Công nghệ Massachusetts, đã viết rằng việc dạy máy tính hiểu ngôn ngữ tự nhiên cũng giống như việc đạt được trí thông minh nói chung.

Máy Turing là một trong những khám phá trí tuệ hấp dẫn và thú vị nhất của thế kỷ 20. Nó là một mô hình trừu tượng đơn giản và hữu ích của điện toán (máy tính và kỹ thuật số), đủ tổng quát để thực hiện bất kỳ tác vụ tính toán nào. Nhờ mô tả đơn giản và phân tích toán học, nó tạo thành nền tảng của khoa học máy tính lý thuyết. Nghiên cứu này đã mang đến sự hiểu biết sâu sắc hơn về tính toán và phép tính số, bao gồm cả sự hiểu biết rằng có một số vấn đề về tính toán không thể giải được trên máy tính lớn.

Nó là gì và ai đã tạo ra nó

Alan Turing đã tìm cách mô tả mô hình nguyên thủy nhất của một thiết bị cơ khí có những khả năng cơ bản giống như một chiếc máy tính. Turing lần đầu tiên mô tả chiếc máy này vào năm 1936 trong bài báo "Về các số tính toán được với ứng dụng cho bài toán giải được", xuất hiện trong Kỷ yếu của Hiệp hội Toán học Luân Đôn.

Máy Turing là một thiết bị điện toán bao gồm đầu đọc/ghi (hoặc "máy quét") với một băng giấy chạy qua nó. Băng được chia thành các ô vuông, mỗi ô mang một ký hiệu duy nhất - "0" hoặc "1". Mục đích của cơ chế này là nó vừa đóng vai trò là phương tiện cho đầu vào và đầu ra, vừa là bộ nhớ làm việc để lưu trữ kết quả của các giai đoạn tính toán trung gian.

Thiết bị này bao gồm những gì?

Mỗi máy như vậy bao gồm hai thành phần:

1. Nguồn cấp dữ liệu không giới hạn. Nó là vô hạn theo cả hai hướng và được chia thành các ô.
2. Chương trình điều khiển tự động, đầu quét đọc ghi dữ liệu. Nó có thể ở một trong nhiều trạng thái tại bất kỳ thời điểm nào.

Mỗi máy kết nối hai chuỗi dữ liệu hữu hạn: một bảng chữ cái gồm các ký hiệu đến A = (a0, a1, ..., am) và một bảng chữ cái gồm các trạng thái Q = (q0, q1, ..., qp). Trạng thái q0 được gọi là thụ động. Người ta tin rằng thiết bị sẽ kết thúc công việc khi chạm vào nó. Trạng thái q1 được gọi là ban đầu - máy bắt đầu tính toán khi bắt đầu hoạt động. Từ đầu vào nằm trên băng, mỗi chữ cái liên tiếp ở mỗi vị trí. Hai bên của nó chỉ có những ô trống.

Cơ chế hoạt động như thế nào

Máy Turing có điểm khác biệt cơ bản so với các thiết bị máy tính - thiết bị lưu trữ của nó có một băng vô tận, trong khi ở các thiết bị kỹ thuật số, thiết bị như vậy có một dải có độ dài nhất định. Mỗi lớp nhiệm vụ chỉ được giải quyết bằng một máy Turing được chế tạo. Các vấn đề thuộc loại khác yêu cầu viết một thuật toán mới.

Thiết bị điều khiển ở một trạng thái có thể di chuyển theo bất kỳ hướng nào dọc theo dây đai. Nó ghi và đọc từ các ô các ký tự của một bảng chữ cái hữu hạn. Trong quá trình di chuyển, một phần tử trống sẽ được phân bổ và lấp đầy các vị trí không chứa dữ liệu đầu vào. Thuật toán máy Turing xác định các quy tắc chuyển tiếp cho thiết bị điều khiển. Họ đặt các tham số sau cho đầu đọc-ghi: viết một ký tự mới vào một ô, chuyển sang trạng thái mới, di chuyển sang trái hoặc phải dọc theo băng.

Thuộc tính cơ chế

Máy Turing, giống như các hệ thống máy tính khác, có những tính năng vốn có và chúng giống với các thuộc tính của thuật toán:

1. Sự kín đáo. Máy kỹ thuật số chỉ chuyển sang bước tiếp theo n+1 sau khi hoàn thành bước trước đó. Mỗi bước được thực hiện sẽ gán n+1 sẽ là bao nhiêu.
2. Trong trẻo. Thiết bị chỉ thực hiện một hành động cho một ô. Nó nhập một ký tự trong bảng chữ cái và thực hiện một chuyển động: trái hoặc phải.
3. Chủ nghĩa quyết định. Mỗi vị trí trong cơ chế tương ứng với một tùy chọn duy nhất để thực hiện một sơ đồ nhất định và ở mỗi giai đoạn, các hành động và trình tự thực hiện chúng là rõ ràng.
4. Năng suất. Kết quả chính xác cho từng giai đoạn được xác định bằng máy Turing. Chương trình thực hiện thuật toán và sau một số bước hữu hạn sẽ chuyển sang trạng thái q0.
5. Nhân vật đại chúng. Mỗi thiết bị được xác định dựa trên các từ hợp lệ có trong bảng chữ cái.

Chức năng của máy Turing

Trong việc giải các thuật toán, việc thực hiện hàm thường được yêu cầu. Tùy thuộc vào khả năng viết chuỗi để tính toán, một hàm được gọi là giải được bằng thuật toán hoặc không giải được. Là tập hợp các số tự nhiên hoặc hữu tỉ, các từ trong bảng chữ cái hữu hạn N cho máy, dãy của tập B được xem xét - các từ trong bảng chữ cái mã nhị phân B = (0,1). Ngoài ra, kết quả tính toán còn tính đến giá trị “không xác định” xảy ra khi thuật toán bị treo. Để thực hiện chức năng này, điều quan trọng là phải có ngôn ngữ hình thức trong bảng chữ cái cuối cùng và giải quyết được vấn đề nhận dạng mô tả chính xác.

Chương trình thiết bị

Các chương trình dành cho cơ chế Turing được định dạng trong các bảng trong đó hàng và cột đầu tiên chứa các ký hiệu của bảng chữ cái bên ngoài và các giá trị của các trạng thái bên trong có thể có của máy tự động - bảng chữ cái bên trong. Dữ liệu dạng bảng là các lệnh mà máy Turing chấp nhận. Việc giải quyết vấn đề diễn ra theo cách này: chữ cái được đọc bởi phần đầu trong ô mà nó hiện đang nằm trên đó và trạng thái bên trong của phần đầu của máy xác định lệnh nào cần được thực thi. Lệnh cụ thể này nằm ở giao điểm của các ký hiệu bảng chữ cái bên ngoài và bên trong nằm trong bảng.

Các thành phần tính toán

Để xây dựng một máy Turing nhằm giải quyết một bài toán cụ thể, bạn cần xác định các tham số sau cho nó.

Bảng chữ cái bên ngoài. Đây là một tập hợp các ký hiệu hữu hạn nhất định, được biểu thị bằng ký hiệu A, các phần tử cấu thành của chúng được gọi là các chữ cái. Một trong số chúng - a0 - phải trống. Ví dụ: bảng chữ cái của thiết bị Turing làm việc với các số nhị phân trông như sau: A = (0, 1, a0).

Một chuỗi các chữ cái và ký hiệu liên tục được ghi trên băng được gọi là một từ.

Thiết bị tự động là thiết bị hoạt động không cần sự can thiệp của con người. Trong máy Turing, nó có một số trạng thái khác nhau để giải quyết vấn đề và trong những điều kiện nhất định phát sinh, nó sẽ chuyển từ vị trí này sang vị trí khác. Tập hợp các trạng thái vận chuyển như vậy là bảng chữ cái bên trong. Nó có ký hiệu bằng chữ cái có dạng Q=(q1, q2...). Một trong những vị trí này - q1 - phải là vị trí ban đầu, tức là vị trí khởi động chương trình. Một yếu tố cần thiết khác là trạng thái q0, là trạng thái cuối cùng, tức là trạng thái kết thúc chương trình và đưa thiết bị về vị trí dừng.

Bảng chuyển tiếp. Thành phần này là một thuật toán cho hoạt động của thiết bị tùy thuộc vào trạng thái hiện tại của máy và giá trị của ký hiệu đã đọc.

Thuật toán cho máy

Trong quá trình vận hành, việc vận chuyển thiết bị Turing được điều khiển bởi một chương trình thực hiện chuỗi hành động sau trong mỗi bước:

1. Viết một ký tự của bảng chữ cái bên ngoài vào một vị trí, kể cả ký tự trống, thay thế phần tử có trong đó, kể cả ký tự trống.
2. Di chuyển một bước ô sang trái hoặc phải.
3. Thay đổi trạng thái bên trong của bạn.

Vì vậy, khi viết chương trình cho từng cặp ký tự hoặc vị trí cần mô tả chính xác 3 tham số: a i - một phần tử trong bảng chữ cái A đã chọn, chiều dịch chuyển ("←" sang trái, "→" sang bên phải, "dấu chấm" - không chuyển động) và q k - trạng thái mới của thiết bị. Ví dụ: lệnh 1 “←” q 2 có nghĩa là thay ký tự bằng 1, di chuyển đầu vận chuyển sang bên trái một ô và chuyển sang trạng thái q 2”.

Máy Turing: ví dụ

Ví dụ 1. Nhiệm vụ được giao là xây dựng một thuật toán thêm một vào chữ số cuối cùng của một số cho trước nằm trên một cuộn băng. Dữ liệu đầu vào - một từ - các chữ số của một số nguyên thập phân, được ghi vào các ô liên tiếp trên băng. Ban đầu, thiết bị được đặt đối diện với ký hiệu ngoài cùng bên phải - chữ số của số.

Giải pháp. Nếu chữ số cuối cùng là 9 thì phải thay bằng 0 rồi thêm 1 vào ký tự trước đó. Chương trình trong trường hợp này cho một thiết bị Turing nhất định có thể được viết như sau:

Ở đây q 1 là trạng thái thay đổi chữ số, q 0 là dừng. Nếu trong q 1 máy sửa một phần tử ở hàng 0..8 thì nó thay thế phần tử đó bằng một trong 1..9 tương ứng, sau đó chuyển sang trạng thái q 0, tức là thiết bị dừng lại. Nếu cố định số 9 thì cỗ xe thay số 0 rồi chuyển động sang trái và dừng ở trạng thái q 1. Chuyển động này tiếp tục cho đến khi thiết bị đăng ký một số nhỏ hơn 9. Nếu tất cả các ký tự bằng 9, chúng được thay thế bằng số 0, số 0 được viết vào vị trí của phần tử cao nhất, dấu xuống dòng di chuyển sang trái và số 1 được ghi vào một ô trống. Bước tiếp theo sẽ là chuyển sang trạng thái q 0 - dừng.

Ví dụ 2. Một loạt các ký hiệu biểu thị dấu ngoặc đơn mở và đóng được đưa ra. Cần phải xây dựng một thiết bị Turing có thể loại bỏ một cặp dấu ngoặc tương hỗ, nghĩa là các phần tử nằm trong một hàng - “()”. Ví dụ: dữ liệu ban đầu: “) (() (()”, câu trả lời phải là: “) . . ((”. Giải pháp: cơ chế nằm trong q 1, phân tích phần tử ngoài cùng bên trái trong dòng.

Trạng thái q 1: nếu gặp ký hiệu “(” thì dịch sang phải và đến vị trí q 2; nếu xác định được “a 0” thì dừng lại.

Trạng thái q 2: dấu ngoặc “(” được phân tích về sự hiện diện của cặp đôi; nếu có sự trùng khớp thì kết quả sẽ là “)”. Nếu phần tử được ghép nối thì thực hiện di chuyển ngược về bên trái và đến q 3.

Trạng thái q 3: đầu tiên xóa ký hiệu “(”, rồi đến “)” và chuyển đến q 1.

trình mô phỏng để học người biểu diễn phổ quát

Nó là gì?

Trình mô phỏng máy Turing là mô hình đào tạo của một người thực thi phổ quát (máy tính toán trừu tượng), được A. Turing đề xuất vào năm 1936 để làm rõ khái niệm về thuật toán. Theo luận điểm của Turing, bất kỳ thuật toán nào cũng có thể được viết dưới dạng chương trình cho máy Turing. Người ta đã chứng minh rằng máy Turing có khả năng tương đương với máy Post và các thuật toán Markov thông thường.

Máy Turing bao gồm một cỗ xe (đầu đọc và ghi) và một cuộn băng vô tận được chia thành các ô. Mỗi ô của băng có thể chứa một ký tự từ một số bảng chữ cái A=(a 0 ,a 1 ,…,a N ) . Bất kỳ bảng chữ cái nào cũng chứa ký tự khoảng trắng, được ký hiệu là 0 hoặc Λ. Khi nhập lệnh, khoảng trắng được thay thế bằng dấu gạch dưới “_”.

Máy Turing là một máy tự động được điều khiển bằng bàn. Các hàng trong bảng tương ứng với các ký tự của bảng chữ cái A đã chọn và các cột tương ứng với trạng thái của máy Q=(q 0 ,q 1 ,…,q M ) . Khi bắt đầu hoạt động, máy Turing ở trạng thái q 1. Trạng thái q 0 là trạng thái cuối cùng: khi ở trong đó, máy sẽ kết thúc hoạt động.

Trong mỗi ô của bảng, tương ứng với một số ký hiệu a i và một số trạng thái q j, có một lệnh gồm ba phần:

1. ký tự từ bảng chữ cái A;
2. hướng di chuyển: > (phải),
3. trạng thái mới của máy

Tin tức

1. Falina I.N. Chủ đề “Máy Turing” trong khóa học khoa học máy tính ở trường (inf.1september.ru).
2. Mayer R.V. Máy Post và Turing (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Máy Turing và thuật toán Markov. Giải quyết vấn đề, M.: MSU, 2006.
4. Bekman I.N. Khoa học máy tính. Bài giảng 7. Thuật toán (profbeckman.narod.ru)
5. Soloviev A. Toán rời rạc không có công thức (lib.rus.ec)
6. Ershov S.S. Các yếu tố của lý thuyết thuật toán, Chelyabinsk, Trung tâm xuất bản SUSU, 2009.
7. Varpakhovsky F.L. Các yếu tố của lý thuyết thuật toán, M: Prosveshchenie, 1970.
8. Vereshchagin NK, Shen A. Các hàm tính toán được, M: MTsNMO, 1999.

Phải làm gì về nó?

Ở đầu chương trình có một trường soạn thảo trong đó bạn có thể nhập tình trạng vấn đề ở dạng tự do.

Dải băng di chuyển sang trái và phải bằng cách sử dụng các nút nằm ở bên trái và bên phải của dải băng. Bằng cách bấm đúp vào ô ruy-băng (hoặc bấm chuột phải), bạn có thể thay đổi nội dung của nó.

Sử dụng thực đơn Ruy-băng bạn có thể lưu trữ trạng thái của băng trong bộ đệm bên trong và khôi phục băng từ bộ đệm.

Trong lĩnh vực Bảng chữ cái các ký tự của bảng chữ cái đã chọn được chỉ định. Một khoảng trắng sẽ tự động được thêm vào các ký tự đã nhập.

Chương trình được gõ vào bảng ở cuối cửa sổ. Cột đầu tiên chứa các ký tự chữ cái và được điền tự động. Dòng đầu tiên liệt kê tất cả các trạng thái có thể có. Bạn có thể thêm và xóa các cột (trạng thái) của bảng bằng cách sử dụng các nút nằm phía trên bảng.

Khi nhập lệnh vào ô trong bảng, trước tiên bạn cần nhập ký tự mới, sau đó là hướng chuyển tiếp và số trạng thái. Nếu một ký tự bị bỏ qua, nó sẽ được giữ nguyên theo mặc định. Nếu số trạng thái bị bỏ qua thì theo mặc định trạng thái của máy không thay đổi.

Ngay tại cánh đồng Một lời bình luận Bạn có thể nhập nhận xét dạng tự do về giải pháp. Thông thường nó giải thích ý nghĩa của từng trạng thái của máy Turing.

Chương trình có thể được thực hiện liên tục (F9) hoặc theo bước (F8). Lệnh sẽ được thực thi bây giờ sẽ được đánh dấu bằng nền màu xanh lá cây. Tốc độ thực hiện được điều chỉnh bằng menu Tốc độ.

Các vấn đề về máy Turing có thể được lưu trong tập tin. Điều kiện nhiệm vụ, bảng chữ cái, chương trình, nhận xét và trạng thái ban đầu của băng sẽ được lưu lại. Khi một tác vụ được tải từ một tệp và được lưu vào tệp đó, trạng thái băng sẽ tự động được lưu vào bộ đệm.

Nếu bạn nhận thấy sai sót hoặc có đề xuất, nhận xét, khiếu nại, yêu cầu hoặc phát biểu, hãy viết thư.

Yêu cầu kỹ thuật

Chương trình chạy theo hệ điều hành của dòng các cửa sổ trên bất kỳ máy tính hiện đại nào.

Giấy phép

Chương trình này miễn phí cho mục đích sử dụng phi thương mại. Mã nguồn của chương trình không được phân phối.

Chương trình đã đến" như vậy", nghĩa là tác giả không chịu bất kỳ trách nhiệm nào về mọi hậu quả có thể xảy ra khi sử dụng nó, bao gồm những tổn thất về tinh thần và vật chất, lỗi thiết bị, thương tích về thể chất và tinh thần.

Khi đăng chương trình lên các trang web khác, cần phải có liên kết đến nguồn ban đầu.

1. 1) xuất bản tài liệu dưới bất kỳ hình thức nào, bao gồm cả việc đăng tài liệu lên các trang Web khác;
2. 2) phân phối các tài liệu không đầy đủ hoặc bị thay đổi;
3. 3) đưa tài liệu vào bộ sưu tập trên bất kỳ phương tiện truyền thông nào;
4. 4) thu được lợi ích thương mại từ việc bán hoặc sử dụng nguyên liệu khác.

Tải xuống tài liệu có nghĩa là bạn chấp nhận các điều khoản của thỏa thuận cấp phép này.

Tải xuống

Sau khi giải nén kho lưu trữ, chương trình sẽ hoạt động bình thường và không yêu cầu bất kỳ cài đặt bổ sung nào.

Về mặt logic, với sự trợ giúp của khái niệm máy Turing, một lý thuyết về các bài toán không thể giải được đã được xây dựng, nhưng trong thực tế tính toán, chúng ta thường phải giải quyết các bài toán có thể giải được nhưng “khó giải”. Khi chọn máy Turing làm mô hình tính toán ở đây, chúng tôi được hướng dẫn bởi thực tế là nó đơn giản và cho phép các ngôn ngữ giống như máy tính, đồng thời độ phức tạp của các phép tính trên máy Turing là đa thức theo số bước của máy tính.

Máy Turing là một máy tính trừu tượng bao gồm bộ điều khiển trạng thái hữu hạn và một băng vô hạn được chia thành các ô, mỗi ô lưu trữ một ký hiệu băng và một trong các ô là vị trí hiện tại của đầu băng. Ký hiệu hình thức của máy Turing là tập có thứ tự M = (X, Q, q 0, F, I), trong đó

X - bảng chữ cái bên ngoài của các ký hiệu (chữ cái trên băng), bao gồm ký hiệu L;

Q là bảng chữ cái cuối cùng của các trạng thái bên trong;

q 0 – trạng thái ban đầu (bắt đầu vận hành), q 0 О Q;

F – tập hợp các trạng thái cuối cùng, FÌ Q;

I là một tập hợp các lệnh hoặc lệnh máy, mỗi lệnh thuộc về tập hợp (Q \ F) ` X ` (®) ` Q ` X ` (R, L, S).

Việc chuyển đổi được thực hiện dựa trên trạng thái hiện tại và ký tự đang được đầu đọc xem sang trạng thái tiếp theo, viết lại ký tự và dịch chuyển đầu (phải R, trái L, ở vị trí S).

Bạn có thể xác định hàm chuyển tiếp

d: (Q \ F) ` X* ® Q ` X* ` (R,L,S), trong đó X* là các từ trong bảng chữ cái X.

Trong trường hợp hàm d duy nhất, máy Turing được gọi là máy Turing xác định.

Cấu hình hiện tại của máy Turing là một chuỗi các ký hiệu quan trọng (trừ L) được ghi trên băng tại một thời điểm nhất định, cùng với ký hiệu trạng thái được đặt trong chuỗi trước khi ký hiệu được quan sát.

Việc dừng (tắt) xảy ra ở trạng thái cuối cùng hoặc khi phía bên trái (trước ®) của không có lệnh máy nào có trong cấu hình nhận được. Một chiếc máy được cho là sẽ chấp nhận mục nhập nếu nó dừng lại ở trạng thái cuối cùng.

Ví dụ, hãy xem xét hoạt động của máy Turing xác định tính hàm ïm - nï. Chúng ta biểu diễn một cặp số tự nhiên có thứ tự (m,n) là từ 0 m 10 n trong bảng chữ cái X \ (L) = (0,1), các ô bên trái và bên phải chứa ký hiệu L.

Q 0 0 ® LRq 1 Biểu tượng trạng thái

Q 1 0 ® 0Rq 1 0 1 L

q 1 1 ® 1Rq 2 q 0 LRq 1 1Sq 5 0Sq 5

q 2 0 ® 1Lq 3 q 1 0Rq 1 1Rq 2 ¾

q 2 1 ® 1Rq 2 q 2 1Lq 3 1Rq 2 LLq 4

q 3 1 ® 1Lq 3 q 3 0Lq 3 1Lq 3 LRq 0

q 3 0 ® 0Lq 3 q 4 0Lq 4 LLq 4 0Sq 5

q 3 L ® LRq 0 q 5 ¾ LRq 5 ¾

q 2 L ® LLq 4 *

q 4 1 ® LLq 4 Bảng 1. Chương trình tính hàm ôm - nô,

q 4 0 ® 0Lq 4 trong đó hàm chuyển đổi được cho bởi bảng

q 0 1 ® 1Sq 5 *

Máy Turing M thừa nhận (từ chối) từ wО X * , nếu nó dừng lại ở đó, đã đạt đến trạng thái thừa nhận (cuối cùng). Xe hơi cho phép ngôn ngữ LÍ X * nếu nó thừa nhận tất cả các từ của ngôn ngữ L. Máy M nhận biết ngôn ngữ LÍ X * nếu nó thừa nhận tất cả các từ trong L và dừng ở các từ trong X * \ L mà không ở trạng thái cuối cùng. Chúng tôi gọi các ngôn ngữ được máy Turing cho phép có thể đếm được một cách đệ quy.

Ngôn ngữ L được phép (được công nhận) phía sau thời gian đa thức, nếu có một máy M chấp nhận (nhận dạng) một ngôn ngữ L và mọi từ wÎ L đều được chấp nhận (nhận dạng) trong thời gian O(n k), trong đó n là độ dài của từ w và k là một số độc lập với w.

Bây giờ bạn có thể xác định lớp P, là tập hợp các ngôn ngữ LÍ (0,1) * được nhận dạng trong thời gian đa thức .

Định lý. Lớp học P có nhiều ngôn ngữ được phép sử dụng trong thời gian đa thức.

Bằng chứng. Theo một hướng thì không quan trọng, nếu máy M nhận ra ngôn ngữ L thì nó chấp nhận ngôn ngữ L. Ngược lại, giả sử ngôn ngữ L được máy M chấp nhận trong thời gian O(n k), tức là. tồn tại một hằng số c sao cho bất kỳ từ nào trong L có độ dài n đều được phép thực hiện không quá T = c×n k bước. Mặt khác, các từ không phải L không được phép sử dụng bất cứ lúc nào. Hãy xây dựng một máy M *, trên từ w, mô hình không quá T = c×n k bước của máy M và dừng, đưa ra 1 nếu M(w) = 1, nếu không thì máy dừng, lấy T = c×n k bước, đưa ra đầu ra 0. Do đó, máy M* nhận dạng ngôn ngữ L và lớp phức tạp P có thể coi là tập hợp các ngôn ngữ được phép trong thời gian đa thức. -

Máy Turing đa băng.

Để mô phỏng hoạt động của máy tính, chúng được sử dụng máy Turing nhiều băng. Trong cấu hình ban đầu của máy nhiều băng, băng đầu tiên chứa đầu vào (chuỗi ký hiệu cuối cùng không bao gồm L), tất cả các ô của các băng còn lại chứa ký hiệu L và đầu đọc của tất cả các băng đều nằm trong trạng thái ban đầu.

Trong một lần chuyển đổi, các hành động sau được thực hiện:

Quản lý chuyển sang một trạng thái mới,

Một ký hiệu mới (hoặc giống nhau) được viết trên mỗi băng;

Đầu đọc của mỗi băng được dịch chuyển độc lập bởi một ô (R, L, S).

Các ngôn ngữ được máy Turing băng đơn cho phép có thể đếm được đệ quy. Các ngôn ngữ đếm được không đệ quy có được chấp nhận trên máy nhiều băng không? Câu trả lời nằm ở định lý tiếp theo.

Định lý. Mỗi ngôn ngữ L được máy Turing nhiều băng cho phép được liệt kê đệ quy.

Bằng chứng. Máy Turing băng đơn có thể được coi là nhiều bài hát, chỉ định các đối số của nó dưới dạng bộ dữ liệu. Trong trường hợp này, một bản nhạc lưu trữ dữ liệu và bản nhạc còn lại là nhãn hiệu. Chúng ta hãy mô hình một máy băng k M như một máy nhiều rãnh N chứa 2k rãnh, trong đó mỗi rãnh thứ hai chứa một điểm đánh dấu cho biết vị trí đầu của băng tương ứng. Máy N phải truy cập từng điểm đánh dấu đầu băng k và thay đổi ký hiệu đại diện cho băng tương ứng cho phù hợp, di chuyển điểm đánh dấu theo cùng hướng như trên băng tương ứng. Cuối cùng, N thay đổi trạng thái của M được ghi trong điều khiển cuối cùng N. Tất cả các trạng thái lưu trữ trạng thái thừa nhận của M đều được chọn làm trạng thái chấp nhận của N. Như vậy, máy M và N đồng thời thừa nhận ngôn ngữ L. Nhưng tất cả các ngôn ngữ ​​​​​được chấp nhận bởi máy băng đơn N , có thể đếm được đệ quy, vì vậy tất cả các ngôn ngữ được máy đa băng M chấp nhận đều có thể đếm được đệ quy.

Định lý. Thời gian cần thiết để máy băng đơn N mô phỏng n chuyển tiếp của máy băng k M là O(n 2).

Bằng chứng. Sau n lần di chuyển của máy M, các điểm đánh dấu đầu được cách nhau không quá 2n ô, do đó máy N cần di chuyển không quá 2n ô sang phải để tìm tất cả các điểm đánh dấu đầu. Bây giờ cô ấy cần chuyển sang trái, thay đổi nội dung của băng M và dịch chuyển các điểm đánh dấu ở đầu, việc này sẽ yêu cầu không quá 2n lần dịch chuyển sang trái cộng với không quá 2k lần chuyển đổi để thay đổi hướng chuyển động và viết điểm đánh dấu đến tế bào. Như vậy, số lần chuyển đổi N để mô phỏng một trong các chuyển đổi của máy M không quá 4n+2k, tức là. TRÊN). Đối với n lần chuyển đổi, thời gian dài hơn n lần, tức là O(n 2). -

Sự khác biệt về thời gian tính toán trên các máy có số lượng băng khác nhau đảm bảo độ phức tạp đa thức và đối với máy một băng được giới hạn ở c×T(n) 2 và dung lượng là c×S(n) (đối với đầu vào có độ dài n ), trong đó T(n), S(n) – thông số của máy băng k. Mối quan hệ giữa công suất và thời gian của máy kéo k là tuyến tính: S £ kT ; cho đầu vào w có độ dài n

Máy Turing không xác định.

Vì những lý do sẽ sớm trở nên rõ ràng, máy Turing không đơn định là một khái niệm then chốt trong lý thuyết các bài toán NP-đầy đủ. Máy Turing không xác định khác với máy Turing thông thường (xác định) ở chỗ nó có thể có nhiều lần chuyển đổi từ cấu hình hiện tại sang cấu hình tiếp theo. Máy không xác định thừa nhận lời nói w , nếu có ít nhất một chuỗi cấu hình dẫn từ cấu hình ban đầu đến cấu hình cuối cùng. Sự tồn tại của các chuỗi cấu hình khác không dẫn đến trạng thái (chấp nhận) cuối cùng là không liên quan. Hoạt động của một máy không xác định ở đầu vào w có thể được biểu diễn dưới dạng cây, trong đó mỗi đường đi từ gốc w đến lá biểu thị một trình tự nhất định các bước có thể có của máy. Nếu s w là trình tự ngắn nhất của các bước vận hành máy có thể kết thúc bằng cấu hình chấp nhận được thì ½s w ½ là thời gian mà máy xử lý đầu vào w. Nếu ở đầu vào w không có chuỗi nào dẫn đến cấu hình thừa nhận thì thời gian xử lý w là không xác định. Người ta tin rằng máy Turing không xác định ở đầu vào w thực hiện song song tất cả các chuỗi bước có thể có cho đến khi nó đạt đến trạng thái chấp nhận hoặc hóa ra chương trình của nó không thể áp dụng được cho cấu hình kết quả.

Câu hỏi vẫn là liệu có những ngôn ngữ được cho phép bởi máy Turing không xác định với độ phức tạp về thời gian và công suất nhất định và không được phép bởi bất kỳ máy xác định nào có cùng độ phức tạp hay không.

Máy Turing không xác định cho phép các ngôn ngữ giống như ngôn ngữ xác định. Tuy nhiên, cần lưu ý rằng sau này phải trả giá cho việc này với độ phức tạp về thời gian tăng mạnh.

Ta ký hiệu L(M) tập hợp tất cả các từ wÎX* được máy M chấp nhận, L(M) được gọi là ngôn ngữ máy M

Định lý. Nếu M là máy không xác định có độ phức tạp thời gian đa thức T(n), thì tồn tại máy xác định M ’ , với L(M ’ ) = L(M) và độ phức tạp về thời gian O(c T(n)).

Bằng chứng. Chứng minh dựa trên thực tế là đối với bất kỳ máy Turing M không xác định nào, một máy xác định M được xây dựng ’ , kiểm tra trình tự cấu hình (đường dẫn trong cây của máy không xác định) và nếu nó tìm thấy ít nhất một cấu hình có trạng thái chấp nhận được thì chính nó sẽ chuyển sang trạng thái chấp nhận được. Các cấu hình được khảo sát được xếp thành hàng đợi có độ dài k (k=1,2...) Hãy xây dựng một máy đa băng xác định M ’ , mô hình hóa máy không xác định M. Băng đầu tiên của máy M ’ lưu trữ một chuỗi các cấu hình của máy M và nhãn cho trạng thái hiện tại của máy M. Các bản ghi ở bên trái nhãn được coi là đã được kiểm tra và sau đó bị bỏ qua. Các cấu hình bên phải được xem xét theo thứ tự ưu tiên. Chương trình máy M được lưu trữ trong bộ điều khiển cuối cùng M ’ . Quá trình xử lý cấu hình hiện tại trên băng đầu tiên như sau:

Máy M ’ kiểm tra trạng thái và biểu tượng đang được theo dõi, nếu trạng thái hợp lệ thì cũng chuyển sang trạng thái hợp lệ.

Nếu trạng thái không cho phép và có k chuyển đổi từ cấu hình này thì M ’ sử dụng băng thứ hai để tạo k bản sao, được ghi vào cuối hàng đợi trên băng 1.

M ’ thay đổi k cấu hình theo chương trình của máy M.

M ’ di chuyển dấu cấu hình hiện tại sang dấu tiếp theo ở bên phải và chu trình lặp lại từ bước 1.

Giả sử m là số lựa chọn tối đa của máy M trong mọi cấu hình. Khi đó có một trạng thái ban đầu M, không quá m cấu hình có thể truy cập trong 1 bước, không quá m2 cấu hình có thể truy cập trong 2 bước, v.v. Do đó, sau n lần chuyển đổi, máy M có thể đạt được tối đa 1+ m +m 2 +…+m n £ n×m n cấu hình. Thứ tự máy M ’ khám phá các cấu hình, được gọi là "tìm kiếm theo chiều rộng", tức là M ’ khám phá tất cả các cấu hình có thể đạt được của máy M trong 0 bước, có thể đạt được trong 1 bước, v.v.

Cấu hình cho phép của máy M sẽ được máy M xem xét ’ trong số các cấu hình n×m n đầu tiên. Do đó, nếu máy M thừa nhận thì máy M ’ cũng cho phép, tức là L(M) = L(M ’ ). “

Lưu ý rằng công của máy xác định M ’ có thể yêu cầu nhiều thời gian hơn theo cấp số nhân so với thời gian chạy của máy không xác định M trong mô hình. Sự khác biệt giữa thời gian đa thức và thời gian hàm mũ là ranh giới giữa những gì máy tính có thể giải được và những gì thực tế không thể giải được.

Định lý. Nếu M là máy Turing không xác định có độ phức tạp dung lượng S(n), thì tồn tại máy Turing tất định M ’ với độ phức tạp công suất O(S 2 (n)) và L(M ’ ) = L(M).

Bằng chứng. Cho M là một máy Turing không xác định (có thể là băng k) với độ phức tạp dung lượng S(n). Khi đó, số lượng cấu hình khác nhau mà máy M có thể nhận được từ cấu hình ban đầu với đầu vào có độ dài n không vượt quá một số nhất định c S (n) , chính xác hơn là ½Q1(½X1+1) k S(n) (S (n)) k , trong đó k – số lượng băng. Khi đó, số lần chuyển đổi từ cấu hình C 1 sang cấu hình C 2 (C 1 ├ C 2) trên bất kỳ băng nào không vượt quá c S (n). Bạn có thể tìm hiểu xem quá trình chuyển đổi C 1 ├ C 2 có tồn tại trong 2i bước hay không bằng cách kiểm tra tất cả C 3 xem quá trình chuyển đổi C 1 ├ C 3 và C 3 ├ C 2 có tồn tại trong i bước hay không. Sau mỗi lần gọi thủ tục, số i giảm đi một nửa.

Ý tưởng mô hình hóa hoạt động của máy M bằng máy M được đưa ra trong phần chứng minh định lý trước đó. Chiến lược vận hành máy M’ -

xác định xem cấu hình ban đầu C 0 có dẫn tới bất kỳ cấu hình cho phép nào C f hay không. Để tìm điện dung trên giới hạn cho máy M ’ , chúng ta đặt các cấu hình (có độ dài O(S(n))) trên các ngăn xếp có cùng kích thước. Tại mỗi thời điểm, số mảnh ngăn xếp không vượt quá 1+ log éc S (n) ù , tức là. O(S(n)). Toàn bộ ngăn xếp của máy M sẽ yêu cầu các ô O(S 2 (n)). -

Định lý. Nếu ngôn ngữ L được cho phép bởi máy Turing không xác định k-băng M = (X, Q, q 0, F, I) với độ phức tạp thời gian T(n), thì ngôn ngữ đó được cho phép bởi máy Turing không xác định băng đơn máy có độ phức tạp về thời gian O(T 2(n)).

Bằng chứng. Giả sử M là một máy Turing không xác định một băng với 2k rãnh trên băng, tức là. Các ký hiệu băng của máy M 1 được biểu diễn bằng các bộ số hạng 2k, trong đó các vị trí số lẻ chứa các ký hiệu bảng chữ cái X và các vị trí số chẵn chứa ký hiệu L hoặc dấu #. Các rãnh đánh số lẻ tương ứng với k băng của máy M, và mỗi rãnh đánh số chẵn 2j chứa ký hiệu L trong tất cả các ô ngoại trừ một ô, trong đó có dấu # đánh dấu vị trí của đầu máy M trên băng j, mà bài hát 2j-1 tương ứng. Máy M 1 mô hình một bước vận hành của máy M như sau. Giả sử rằng phần đầu của máy M 1 trước tiên xem ô chứa phần đầu ngoài cùng bên trái của máy M.

Đầu máy M 1 di chuyển sang phải cho đến khi vượt qua tất cả k điểm đánh dấu vị trí đầu trên các rãnh số chẵn. Trong trường hợp này, M 1 ghi nhớ ở trạng thái của nó các ký hiệu được xem bởi mỗi đầu của máy M. Bây giờ M 1 tạo một nhánh không xác định dựa trên trạng thái của máy M, máy M 1 đã nhớ ở trạng thái của nó và các ký hiệu được máy M xem trên băng, máy M I cũng tìm thấy 1.

Sau khi chọn bước của máy M để lập mô hình, máy M 1 sẽ thay đổi trạng thái của máy M theo nó và nó ghi nhớ trạng thái của nó. Sau đó M 1 di chuyển đầu sang trái và đi qua tất cả các điểm đánh dấu, thay đổi biểu tượng ruy-băng trên đường phía trên điểm đánh dấu và di chuyển điểm đánh dấu nhiều nhất là một ô vuông (L,R,S).

Máy M 1 mô phỏng một bước hoạt động của máy M. Hành động của máy M 1 tại bước này được xác định. Đầu của nó nằm ở bên phải điểm đánh dấu bên trái không quá hai ô. Bắt đầu từ điểm đánh dấu này, chu kỳ có thể được lặp lại.

Nếu máy M thừa nhận một chuỗi w có độ dài n thì nó thực hiện tối đa T(n) chuyển tiếp. Rõ ràng, trong một chuỗi T(n) bước, các đầu của máy M có thể phân kỳ không quá T(n) ô, và do đó, M 1 có thể mô phỏng một bước của chuỗi này không quá O(T). (n)) các bước của nó. Do đó, M 1 thừa nhận một chuỗi w, thực hiện tối đa các chuyển đổi O(T 2 (n)). Điều này ngụ ý rằng M 1 chấp nhận ngôn ngữ L và có độ phức tạp về thời gian O(T 2 (n)). -

Hệ quả 1. Nếu một ngôn ngữ được chấp nhận bởi máy Turing xác định băng k với độ phức tạp thời gian T(n), thì ngôn ngữ đó được chấp nhận bởi máy Turing xác định băng đơn với độ phức tạp thời gian O(T 2 (n)). -

Hệ quả 2. Nếu một ngôn ngữ L được chấp nhận bởi máy Turing không xác định k-băng có độ phức tạp công suất S(n), thì nó được chấp nhận bởi máy Turing không xác định băng đơn có độ phức tạp công suất S(n). -

Hệ quả 3. Nếu một ngôn ngữ được chấp nhận bởi máy Turing xác định băng k có độ phức tạp dung lượng S(n), thì ngôn ngữ đó được chấp nhận bởi máy Turing xác định băng đơn có độ phức tạp dung lượng S(n). -

Mô phỏng máy Turing trên máy tính và máy tính trên máy Turing.

Các thành phần chính của máy tính bao gồm RAM và bộ xử lý. Các chương trình và dữ liệu, được biểu diễn bằng bảng chữ cái nhị phân, được đặt trong bộ nhớ. Khi một chương trình được thực thi, các lệnh riêng lẻ của nó và dữ liệu cần thiết sẽ được lấy từ bộ nhớ vào bộ xử lý và ngược lại - các giá trị thu được khi thực thi lệnh được ghi vào các ô nhớ.

Bộ nhớ bao gồm một số ô lưu trữ (thanh ghi) nhất định dùng để lưu trữ trung gian các giá trị toán hạng và để lưu trữ các thông tin cần thiết khác để thực thi lệnh, thanh ghi để kiểm soát các ô lưu trữ, địa chỉ ô và các trường của chính các ô đó.

Bộ xử lý bao gồm bộ điều khiển (CU) và bộ số học (AU). Thiết bị điều khiển chứa bộ đếm chu kỳ xung nhịp, lệnh, v.v., tạo ra các tín hiệu điều khiển để thực thi lệnh, truyền dữ liệu, v.v. Bộ xử lý chứa các thanh ghi toán hạng, đường truyền thông và đường trễ để thực hiện trực tiếp các quá trình tính toán.

Cùng với bộ xử lý và bộ nhớ, máy tính cũng cần có thiết bị đầu vào/đầu ra.

Mô phỏng máy Turing trên máy tính. Cho M là một máy Turing, một trong những thành phần của nó là bộ điều khiển hữu hạn. Vì M có số lượng trạng thái hữu hạn và số quy tắc chuyển đổi hữu hạn, nên một chương trình máy tính có thể mã hóa các trạng thái dưới dạng chuỗi ký hiệu, giống như các ký hiệu của bảng chữ cái bên ngoài của nó và sử dụng bảng chuyển đổi của máy M để chuyển đổi chuỗi. Băng vô hạn của máy Turing có thể được mô phỏng bằng các đĩa di động được đặt tương ứng trong hai kho lưu trữ dữ liệu nằm ở bên trái và bên phải của đầu đọc trên băng. Dữ liệu nằm trong tạp chí càng xa thì nó càng cách xa đầu trên băng.

Để mô phỏng máy tính trên máy Turing hai điều cần thiết:

Có hướng dẫn nào có thể được thực thi bởi máy tính mà máy Turing không thể truy cập được không?

Máy tính có hoạt động nhanh hơn máy Turing không, tức là nhiều hơn sự phụ thuộc đa thức phân chia thời gian chạy của máy tính và máy Turing khi giải một bài toán.

Mô hình không chính thức của một máy tính thực:

Một bộ nhớ bao gồm một chuỗi các từ và địa chỉ của chúng. Các số tự nhiên 0,1,… sẽ được dùng làm địa chỉ;

Một chương trình máy tính được viết bằng các từ bộ nhớ, mỗi từ biểu thị một lệnh đơn giản. Cho phép “địa chỉ gián tiếp” bằng con trỏ;

Mỗi lệnh sử dụng một số lượng từ hữu hạn và thay đổi giá trị của nhiều nhất một từ;

Có những từ bộ nhớ có khả năng truy cập nhanh (thanh ghi), nhưng tốc độ truy cập vào các từ khác nhau chỉ ảnh hưởng đến hệ số không đổi, không làm biến dạng sự phụ thuộc đa thức.

Thiết kế khả thi của máy Turing để mô phỏng máy tính

thể hiện trong hình.

Hình trang 369

Máy có nhiều dây đai. Băng đầu tiên đại diện cho tất cả bộ nhớ của máy tính - địa chỉ và giá trị (ở dạng nhị phân). Địa chỉ kết thúc bằng dấu *, các giá trị kết thúc bằng dấu #. Phần đầu và phần cuối của bản ghi của băng thứ 1 được biểu thị bằng dấu $. Băng thứ hai, “bộ đếm lệnh”, chứa một số nguyên nhị phân duy nhất biểu thị một trong các vị trí đầu đọc trên băng đầu tiên, địa chỉ của lệnh sẽ được thực thi tiếp theo. Băng thứ ba chứa địa chỉ và giá trị của nó sau khi địa chỉ đó được đặt trên băng đầu tiên. Để thực thi một lệnh, máy Turing phải tìm một giá trị từ một hoặc nhiều địa chỉ bộ nhớ nơi lưu trữ dữ liệu liên quan đến tính toán. Địa chỉ mong muốn được sao chép vào băng 3 và so sánh với địa chỉ trên băng 1 cho đến khi khớp. Giá trị tại địa chỉ này được sao chép sang băng thứ ba và di chuyển đến vị trí mong muốn, thường là tại một trong những địa chỉ bắt đầu đại diện cho các thanh ghi của máy tính. Băng thứ tư mô phỏng tập tin đầu vào. Băng thứ năm là bộ nhớ làm việc, dùng để thực hiện các phép tính. Lệnh thừa nhận của máy Turing tương ứng với việc in ra tệp đầu ra.

Hoạt động của một máy mô phỏng như vậy:

1. Sau khi tìm thấy địa chỉ trên băng thứ nhất khớp với số hướng dẫn trên băng thứ 2, hãy kiểm tra giá trị của địa chỉ đó và sao chép nó sang băng thứ 3. Các bit đầu tiên của lệnh chỉ định hành động (sao chép, dán, rẽ nhánh, v.v.), các bit còn lại chỉ định địa chỉ hoặc các địa chỉ được sử dụng trong hành động này.

2. Nếu lệnh chứa một giá trị tại một địa chỉ nhất định thì địa chỉ này sẽ được sao chép sang băng thứ 3 và vị trí lệnh sẽ được sao chép vào rãnh thứ 2 của băng thứ 1.

a) sao chép sang địa chỉ khác;

Địa chỉ thứ hai được trích ra từ lệnh, đặt trên băng thứ 3, nằm trên băng thứ 1 và giá trị của nó được sao chép vào khoảng trống dành riêng cho nó. Nếu giá trị mới yêu cầu nhiều (ít) bộ nhớ hơn giá trị cũ thì không gian sẽ được thay đổi bằng cách dịch chuyển, cụ thể là:

(1) phần băng ở bên phải nơi đặt giá trị mới được sao chép vào băng làm việc;

(2) giá trị mới được ghi vào băng thứ nhất;

(3) phần làm việc được sao chép trở lại băng thứ 1 bên phải giá trị mới.

b) thêm giá trị tìm thấy vào địa chỉ khác;

Chúng tôi tìm địa chỉ thứ hai trên băng đầu tiên, thêm giá trị tại địa chỉ này và địa chỉ đó được ghi trên băng thứ 3.

c) tiến hành thực hiện lệnh tại địa chỉ được ghi trên băng thứ 3, băng 3 được sao chép sang băng 2 và chu kỳ của lệnh bắt đầu lại.

4. Sau khi hoàn thành hướng dẫn (không phải là chuyển tiếp), hãy thêm 1 vào bộ đếm trên băng 2 và bắt đầu lại chu trình hướng dẫn.

Bây giờ chúng ta cần đảm bảo rằng nếu một bài toán có thể được giải trong thời gian đa thức trên máy tính thì nó cũng có thể được giải trong thời gian đa thức trên máy Turing và ngược lại. Như sau, từ các định lý đã được chứng minh ở trên, việc sử dụng máy Turing nhiều băng là đủ, vì sự khác biệt về thời gian hoạt động của máy Turing một băng và nhiều băng là đa thức.

Thời gian chạy của máy Turing mô phỏng máy tính

Hãy để chúng tôi giới thiệu những hạn chế sau đây trên kiểu máy tính:

Không có lệnh máy tính nào tạo ra một từ dài hơn 1 bit toán hạng của nó.

Lệnh áp dụng cho các từ có độ dài m phải được thực hiện không quá 0(m2) bước trên máy Turing nhiều băng.

Hãy gọi các hoạt động như vậy chấp nhận được.

Các điều kiện này được thỏa mãn bằng cách cộng, dịch chuyển 1 bit, so sánh các giá trị được thực hiện trên máy Turing nhiều băng theo bước 0(m). Và cả phép nhân các số nguyên m-bit, nếu được mô phỏng bằng cách sử dụng m phép cộng liên tiếp với độ dịch chuyển 1 bit sang trái. Thời gian cần thiết để thực hiện phép nhân sẽ tỷ lệ thuận với bình phương độ dài của các thừa số. .

Định lý.Đối với một máy tính có các thuộc tính được chỉ định, mô hình máy Turing được mô tả ở trên có thể mô phỏng m bước máy tính với không quá 0(m3)bước.

Bằng chứng. Ban đầu, băng đầu tiên chỉ chứa chương trình máy tính, độ dài của nó không phụ thuộc vào n (số bước để thực hiện lệnh). Từ hoặc địa chỉ máy tính lớn nhất tìm thấy trong chương trình sẽ được ký hiệu là c và d là số lượng từ của chương trình.

Sau n bước, máy tính không thể tạo ra một từ dài hơn c+n và không thể tạo hoặc sử dụng địa chỉ dài hơn c+n bit. Mỗi lệnh tạo ra nhiều nhất một địa chỉ mới nhận một giá trị, vì vậy sau khi thực hiện n lệnh chúng ta có địa chỉ d+n. Mỗi giá trị địa chỉ chiếm không quá 2(c+n) +2 bit và sau n lệnh được thực thi không quá 2(d+n)(c+n+1) hoặc 0(n 2)

Phải mất 0(n 2) thời gian để tra cứu địa chỉ của một lệnh máy tính, các từ dài 0(n) và các lệnh được thực thi bởi máy Turing trong thời gian 0(n 2), dịch chuyển để tạo khoảng trống cho một lệnh mới word liên quan đến việc sao chép dữ liệu có giá trị 0(n 2) từ băng 1 sang băng đang hoạt động và ngược lại. Do đó, máy Turing bắt chước một bước của máy tính theo 0(n 2) bước của nó và n bước có thể được bắt chước theo 0(n 3) bước của máy Turing. -

Định lý. Việc thực hiện n bước của máy tính có thể được mô phỏng trên máy Turing băng đơn với không quá 0(n 6) bước.

Bằng cách này, máy Turing có thể mô phỏng bộ nhớ và điều khiển của một máy tính thực, chỉ sử dụng một băng để ghi lại tất cả các thành phần bộ nhớ và nội dung của chúng - các thanh ghi, bộ nhớ chính, đĩa và các thiết bị lưu trữ khác. Từ đây chúng ta có thể chắc chắn rằng mọi thứ mà máy Turing không thể thực hiện được thì máy tính cũng không thể tính toán được. -