в якості вихідної, то робота машини буде полягати в тому, щоб послідовно (крок за кроком) перетворювати вихідну конфігурацію відповідно до програми машини до тих пір, поки не буде досягнута заключна конфігурація. Після цього робота машини Тьюринга вважається закінчилася, а результатом роботи вважається досягнута заключна конфігурація.
Будемо говорити, що непорожнє слово? в алфавіті А {} =, ...,} сприймається машиною в стандартному положенні, якщо воно записано в послідовних комірках стрічки, всі інші комірки порожні, і машина оглядає крайню справа осередок із тих, в яких записано слово?. Стандартне положення називається початковим (заключною), якщо машина, що сприймає слово в стандартному положенні, знаходиться в початковому стані (відповідно в стані зупинки). Нарешті, будемо говорити, що слово? переробляється машиною в слово b, якщо від слова?, сприйманого в початковому стандартному положенні, машина після виконання кінцевого числа команд приходить до слова b, сприйманому в положенні зупинки.
1.2 Застосування машин Тьюринга до слів
Проілюструємо на прикладах всі введені поняття, пов'язані з машинами Тьюринга.
Приклад 2.1. Дана машина Тьюринга із зовнішнім алфавітом А={0,1} (тут 0-символ порожнього вічка), алфавітом внутрішніх станів Q={,,} і з наступного функціональною схемою (програмою):
0? 0П; 0? 1; 1? 1П; 1? 1? 1П.
Подивимося, в яке слово переробить ця машина слово 101, виходячи зі стандартного початкового положення. Будемо послідовно виписувати конфігурації машини при переробці нею цього слова. Маємо стандартне початкове положення.
Таким чином, вихідне слово 101 перероблено машиною в слово 10101.
Отриману послідовність конфігурацій можна записати більш коротким способом. Конфігурація (1) записується у вигляді наступного слова в алфавіті А Q: 1 жовтня (вміст оглядається осередку записано праворуч від стану, в якому знаходиться в даний момент машина). Далі, конфігурація (2) записується так: 101 0, конфігурація (3) - 1010 0 і, нарешті, (4) - 1010 1. Вся послідовність записується так:
1= gt; 101 0= gt; 1010 0= gt; 1010 1.
Наведемо послідовність конфігурацій при переробці цією машиною слова 11011, виходячи з початкового положення, при якому в стані обозревается крайня ліва комірка, в якій міститься символ цього слова (самостійно проаналізуйте кожен крок роботи машини, вказуючи, яка команда зумовила його).
Більш коротка запис цієї послідовності конфігурацій, тобто процесу роботи машини, буде
11011= gt; 1 1011= gt; 11011= gt; 110 11= gt; тисячі сто один 1= gt; 11011 0= gt; 11011 1.
Таким чином, слово 11011 перероблено машиною в слово 110111.
Приклад 2.2. Машина Тьюринга задається зовнішнім алфавітом А={0,1, *} (як і в попередньому прикладі 0 - символ порожнього вічка), алфавітом внутрішніх станів Q= {,,,} і програмою:
0? 0л, 0? 1П, 0? 0л, 1? 0л, 1? 1Л, 1? 1П, *? 0, *? * Л, *? * П.
Подивимося, як ця машина переробляє деякі слова, і постараємося виявити закономірність у її роботі.
Попередньо зауважимо, що програма машини може бути записана також у вигляді такої таблиці:
0 1 * 0л 0л 0 1П 1Л * Л 0л 1П * П
Щоб визначити по таблиці, що робитиме машина, перебуваючи, наприклад, у стані і спостерігаючи в оглядається осередку символ 1, потрібно знайти в таблиці клітку, що знаходиться на перетині стовпця і рядка, що містить 1. У цій клітці записано 1Л. Це означає, що на наступному кроці машина залишиться в колишньому стані, збереже вміст оглядається осередку 1 і перейде до огляду наступної лівого вічка на стрічці.
Застосуємо цю машину до слова 11 * 11. Ось послідовність конфігурацій, що виникають у процесі роботи машини (вихідна конфігурація - стандартна початкова):
* 1. +1= gt; 11 * 10= gt; 11 * 10= gt;-1 1 * 10= gt; 11 * 10= gt; 011 * 10= gt; 11 * 10= gt; +11 1 * 10= gt; 111 * 10= gt; 111 * 10= gt; 111 * 1 0= gt; 111 * 10= gt; 111 * 00= gt; +11 1 * 0= gt; 11 Січня * 0= gt; 111 * 0= gt; 0111 * 0= gt; 1111 * 0= gt; 11 листопада * 0= gt; 111 1 * 0= gt; 1 111 * 0= gt; 1 111 * 0= gt; 1 111 * 0= gt; 1 111 00.
Пропонується перевірити самостійно, що дана машина Тьюринга здійснює такі перетворення конфігурацій:
* 1= gt; 111 0; 1 * 111 1= gt; 11111 0; 11 * 11 +1= gt; 11111 0; 11111 * 1. +1= gt; 1111111 0.
Неважко помітити, що дана ...
