Існування універсальних обчислювачів. Алгоритмічні проблеми і взаємозв'язок алгоритмічних систем.

Існування універсальних обчислювачів.

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

А чи не можна побудувати такий виконавець, який був би здатний виконати будь-який алгоритм, заданий у вигляді програми для Машини Тьюринга? Позитивна відповідь на це питання був би математичним обгрунтуванням існування універсального обчислювача, тобто здатного виконати будь-який належним чином записаний алгоритм, обчислити будь-яку вичіслімую функцію.

Отже, нехай нам треба побудувати Універсальну Машину Тьюринга, назвемо її УМТ, для якої:

вихідними даними є програма іншої машини, назвемо її МТ, з вихідними даними Д останньої;

результат застосування УМТ до цих вихідними даними повинен бути таким же, як застосування МТ до її вихідними даними, тобто

УМТ (МТ, Д) = МТ (Д).

Через чисто технічної громіздкість ми не будемо давати цілком доведено існування УМТ, а дамо лише обгрунтування її існування. У цьому обгрунтуванні ми покажемо основну ідею доказу.

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

інтерпретує алгоритм для УМТ:

оглядав клітинку, під якою написана буква (стан);

Відшукай у таблиці рядок, визначену цією буквою;

В знайденої рядку оглядав трійку символів, яка стоїть на перетині з стовпцем, позначених літерою, вписаною в розглянутих клітинку;

Заміни букву в оглядає, комірці на першу літеру трійки;

Якщо другий буквою трійки є "!", то стоп;

Якщо в оглядає, комірці третя буква "Н", то зітри букву під оглядає, осередком і запиши туди другу літеру трійки (зміна стану);

Якщо в оглядає, трійці третя буква "Л", то зітри букву під оглядає, осередком, зрушимо вліво і запиши під цією осередком другу літеру трійки;

Якщо в оглядає, трійці третя літера "П", то зітри букву під оглядає, осередком, зрушимо вправо і запиши під цією осередком другу літеру трійки;

Перейди до кроку 1.

Для того, щоб перетворити цей опис в програму Машини Тьюринга, треба вирішити дві основні проблеми:

Як задавати програму і конфігурацію имитуємої МТ на стрічці?

Так як довільна МТ може мати довільний алфавіт, то який алфавіт повинен бути у УМТ?

Перша проблема розбивається на дві:

як задати програму на стрічці?

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

Програму МТ будемо записувати п'ятірками

aqbp *, де a, b