Читайте также: |
|
Робота МТ повністю визначається стартовим станом стрічки та логічного блока.
Нагадаємо, що композицією двох функцій та є функція
Означення.
Композицією МТ М1 та М2 є дві машини Тюрінга, що мають спільний зовнішній алфавіт та різні внутрішні алфавіти та
Композицією машин М1 та М2 є машина М, що має зовнішній алфавіт
та внутрішній і програмою, що створюється так:
У всіх командних символах , а інші символи залишаються без змін.
У всіх командах символи замінюються на відповідні .
При такій заміні машини М1 та М2 діють послідовно, по черзі обчислюючи та міняючи стрічку.
Так от, якщо та є функції, що можуть обчислюватись МТ то і їх композиція також може бути обчисленою.
Машина Тюрінга володіє універсальністю. Було доведено, що МТ може обчислити довільну функцію, лише б вона була обчислюваною.
Часто не є відомості в про обчислюваність МТ даної функції.
Виникає проблема її зупинки. Так от існує теорема, що не існує МТ такої, що могла б зупинити задану.
Дата добавления: 2015-07-15; просмотров: 142 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Означення. | | | І. ВСТУП |