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