Проблема останова для машини Тьюринга

ЛЕКЦІЯ 6. Алгоритмічно нерозв'язні проблеми

Універсальна машина Тьюринга

Будь-яка програма для машини Тьюринга може бути закодована деяким кодом. Позначимо через d (М) код програми машини Тьюринга. Тоді можна побудувати таку машину Тьюринга М¢(d (М)* W) на вхід якої буде подаватися код d (М) разом із вхідним словом W. Тоді машина Тьюринга спочатку перевіряє, чи є d (М) синтаксично правильним програмним кодом для машини Тьюринга, і якщо це так, то виконує програму машини М над словом W; якщо ж ні, те вона зупиняється в стані “ немає!”. Така машина Тьюринга називається універсальною машиною Тьюринга.

Універсальна машина Тьюринга є математичним апаратом для доказу алгоритмічної нерозв'язності проблем[2]. Аналогічно можна побудувати й універсальний алгоритм Маркова.

Історично першою алгоритмічно нерозв'язною проблемою, доведеної Тьюрингом, була проблема останова для машини Тьюринга. Вона формулюється так: чи можна побудувати таку універсальну машину Тьюринга М¢, що будучи застосованої до слова (d (М)* W), вона буде зупинятися в “ так!” стані, якщо машина Тьюринга М застосовна до слова W, тобто зупиняється на цьому слові, і зупинятися в “ немає!” стані, якщо машина М не застосовна до слова W.

Теорема. Проблема останова для машини Тьюринга алгоритмічно нерозв'язна.

Доказ. Припустимо, що така універсальна машина Тьюринга М¢ побудована. Це означає, що в таблиці програми універсальної машини Тьюринга є дві команди, по яких вона в деякому стані q¢ на деякому символі s зупиняється в “ так!” стані, і в деякому стані q¢¢ на деякому символі t зупиняється в “ немає!” стані (тобто в її таблиці є клітки:

Побудуємо тепер машину Тьюринга М¢¢ так, що змінимо в ній тільки одну команду: у стані q¢ на символі s машина не зупиняється, а продовжує нескінченно писати символ s у ту саму осередок. Таблиця для машини М¢¢ показана нижче.

	q ¢	q ¢¢
s	s даний
t		t немає!

Тепер на вхід машини М¢ подамо її власний код, для якого вхідним словом буде код машини Тьюринга М¢¢: М¢(d( M¢)* d (M¢¢)). Чи зможе тепер машина М¢ розпізнати, чи зупиниться вона сама на коді машини Тьюринга М¢¢? Універсальна машина Тьюринга працює так, як машина, код якої поданий на її стрічку, отже, дійшовши до символу s у стані q ¢ (у коді машині М¢¢ – слові, що переробляється,), машина М(зупиниться в стані “ так!”, у той час як М¢¢ не зупиняється! І навпаки, коли в стані q ¢¢ машина М¢¢ бачить символ t, вона видає повідомлення “ ні ” і зупиняється, а машина М¢ для цієї ситуації теж зупиняється в стані “ ні ”, тобто вона видає повідомлення про те, що машина М¢¢ не зупиняється!

Таким чином, машина Тьюринга М¢ не розпізнає свій власний останов на коді машини М¢¢. Сам факт можливості побудови такої машини Тьюринга, що не може розпізнати останов, доводить алгоритмічну нерозв'язність цієї проблеми.

Проблема алгоритмічної нерозв'язності зв'язана з проблемою самозастосовності.

Дата добавления: 2014-01-07