машина Тьюринга реалізує операцію складання: в результаті її роботи на стрічці записано підряд стільки одиниць, скільки їх було всього записано по обидві сторони від зірочки перед початком роботи машини.
Цей маленький досвід роботи з машинами Тьюринга дозволяє зробити деякі висновки. Так ретельно описане пристрій цієї машини (розбита на клітинки стрічка, зчитує голівка) по суті не має ніякого значення. Машина Тьюринга - не що інше, як деякий правило (алгоритм) для перетворення слів алфавіту AQ, тобто конфігурацій. Таким чином, для визначення машини Тьюринга потрібно задати її зовнішній і внутрішній алфавіти, програму і вказати, які з символів позначають порожню комірку і заключний стан.
.3 Конструювання машин Тьюринга
Створення (синтез) машин Тьюринга (тобто написання відповідних програм) є завданням значно складнішою, ніж процес застосування даної машини до даних словами.
Приклад 3.1. Побудуємо таку машину Тьюринга, яка з n записаних підряд одиниць залишала б на стрічці n - 2 одиниці, також записані підряд, якщо n? 2, і працювала б вічно, якщо n=0 або n=1.
В якості зовнішнього алфавіту візьмемо Двоелементною безліч A={0, 1}. Кількість необхідних внутрішніх станів буде визначено в процесі складання програми. Вважаємо, що машина починає працювати зі стандартного початкового положення, тобто коли в стані обозревается крайня права одиниця з n, записаних на стрічці.
Почнемо з того, що зітремо перший одиницю, якщо вона є, перейдемо до огляду наступної лівого вічка і зітремо там одиницю, якщо вона в цьому осередку записана. На кожному такому переході машина повинна переходити в нове внутрішній стан, бо в іншому випадку будуть стерті взагалі всі одиниці, записані підряд. Ось команди, що здійснюють описані дії:
1? 0л; 1? 0л.
Машина знаходиться в стані і оглядає третій праворуч осередок із тих, в яких записано дане слово (n одиниць). Не змінюючи вмісту оглядається осередку, машина должна зупинитися, тобто перейти в заключний стан, незалежно від вмісту комірки. Ось ці команди:
0? 0; 1? 1.
Тепер залишається розглянути ситуації, коли на стрічці записана всього одна одиниця або НЕ записано жодної. Якщо на стрічці записана одна одиниця, то після першого кроку (виконавши команду 1? 0л) машина буде перебувати в стані і буде оглядати другий праворуч клітинку, в якій записаний 0. За умовою, в такому випадку машина повинна працювати вічно. Це можна забезпечити, наприклад, такою командою:
0? 0П,
виконуючи яку крок за кроком, машина рухатиметься по стрічці необмежено вправо (або протягувати стрічку через прочитує головку справа наліво). Нарешті, якщо на стрічці не записано жодної одиниці, то машина, за умовою, також повинна працювати вічно. У цьому випадку в початковому стані обозревается осередок з вмістом 0, і вічна робота машини забезпечується наступною командою:
0? 0П.
Запишемо складену програму (функціональну схему) побудованої машини Тьюринга у вигляді таблиці:
0 1 0П 0л 0П 0л 0 1
На закінчення зазначимо таке. Створена нами машина Тьюринга може застосовуватися не тільки до слів в алфавіті А={0,1}, що представляє собою записані підряд n одиниць (n? 2). Вона застосовна і до багатьох інших слів у цьому алфавіті, наприклад до слів: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 і т.д. (виходячи з стандартного початкового положення). З іншого боку, побудована машина не застосовна (тобто при подачі цих слів на вхід машини вона працює вічно) не тільки до слова «1» або до слова, що складається з одних нулів. Вона не застосовна і до наступних словами: 101, 1001, 11101, 101101, 1100101101 і т.д.
1.4 вичіслімого по Тьюрингу функції
Визначення 4.1: Функція називається обчислюваною по Тьюрингу, якщо існує машина Тьюринга, що обчислює її, тобто така машина Тьюринга, яка обчислює її значення для тих наборів значень аргументів, для яких функція визначена, і працююча вічно, якщо функція для даного набору значень аргументів не визначена.
Залишається домовитися про деякі умовності для того, щоб це визначення стало до кінця точним. По-перше, нагадаємо, що мова йде про функції (або можливо про часткові функціях, тобто не всюди визначених), заданих на множині натуральних чисел і приймаючих також натуральні значення. По-друге, потрібно домовитися, як записувати на стрічці машини Тьюринга значення,, ..., аргументів функції f (,, ...,), з якого положення починати переро...
