Деякі операції над МТ

Робота МТ повністю визначається стартовим станом стрічки та логічного блока.

Нагадаємо, що композицією двох функцій та є функція

Означення.

Композицією МТ М1 та М2 є дві машини Тюрінга, що мають спільний зовнішній алфавіт та різні внутрішні алфавіти та

Композицією машин М1 та М2 є машина М, що має зовнішній алфавіт

та внутрішній і програмою, що створюється так:

У всіх командних символах , а інші символи залишаються без змін.

У всіх командах символи замінюються на відповідні .

При такій заміні машини М1 та М2 діють послідовно, по черзі обчислюючи та міняючи стрічку.

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

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

Часто не є відомості в про обчислюваність МТ даної функції.

Виникає проблема її зупинки. Так от існує теорема, що не існує МТ такої, що могла б зупинити задану.

Дата добавления: 2015-07-15