слення. p> Зауваження 1.1. Клас ширше класу. Будь функції від натурального аргументу зі значеннями в можна зіставити предикат за правилом, де позначає довжину слова. Обмеження такого предиката на слова довжини тотожно дорівнює 0 або 1 (залежно від). Схемна складність таких функцій обмежена константою. Тому всі такі предикати з визначення належать P/poly, хоча серед них є і нерозв'язні предикати. p> Справедливо наступне посилення теореми.
Теорема 1.3. належить тоді і тільки тоді, коли
В
існує МТ, яка за кількістю за час будує схему обчислення.
Доказ. Дане в доведенні теореми 1.2. опис неважко перетворити в МТ, яка будує схему обчислення за поліноміальний по час (схема має просту структуру: кожна змінна пов'язана з попередніми одними і тими ж правилами узгодження).
Настільки ж просто. Обчислюємо розмір вхідного слова. Потім будуємо з цього розміру схему обчислення, використовуючи зазначену в умові 2 машину. Після цього обчислюємо на машині, яка за описом схеми і значенням вхідних змінних обчислює значення схеми за поліноміальний від довжини входу час. p> Завдання
Побудуйте машину Тьюринга, яка записує вхідний двійкове слово в зворотному порядку.
Побудуйте машину Тьюринга, яка складає два числа, записані в двійковій системі. Для визначеності вважайте, що записи чисел розділені спеціальним символом алфавіту "". p> Доведіть, що не існує алгоритму, який по машині Тьюринга і входу визначає, чи зупиниться вона на цьому вході.
Доведіть, що не існує алгоритму, який виписує одну за одною всі машини Тьюринга, які не зупиняються, будучи запущеними на порожній стрічці.
Нехай - максимальний час, який може пройти до зупинки машини Тьюринга із станами та символами алфавіту, якщо її запустити на порожній стрічці. Доведіть, що функція зростає швидше будь обчислюваною всюди певної функції, тобто. p> Набір елементарних інструкцій у описаних вище машин Тьюринга вкрай бідний. Є різноманітні їх узагальнення, наприклад, багатострічкові машини Тьюринга. На відміну від описаної вище, така МТ має кілька (кінцеве безліч) стрічок, кожна зі своєю головкою, керуючому пристрою доступні символи, що знаходяться в осередках, на яких розташовані головки стрічок. Виділено дві стрічки: вхідна, з якою дозволяється тільки читати символи, і вихідна, на яку дозволяється тільки писати символи. Решта стрічки називаються робітниками. Багатострічковій машина називається-стрічкової, якщо у неї робочих стрічок. Дія за такт роботи полягає у зміні стану керуючого пристрою, зміну символів в комірках під головками і зміну положень головок на стрічках (кожна головка зсувається не більше, ніж на одну позицію). Ця дія однозначно визначається станом керуючого пристрою і набором символів в комірках під головками. Якщо дія виконати не можна, машина зупиняється. p> На початку роботи багатострічковій машини Тьюринга всі стрічки порожні, окрім вхідної, на якій записаний вхід. Результат роботи ма...
