Правильна обчислювальність функцій за Т’юрингом

Визначення. Будемо говорити, що машина Т’юринга правильно обчислює функцію , якщо початкове слово вона переводить у слово і при цьому не добудовує в процесі роботи на стрічці нових комірок ні ліворуч ні праворуч.

Якщо функція f не визначена на даному наборі значень аргументів, то, почавши роботу з указаного положення, машина Тюринга в процесі роботи не буде добудовувати комірки стрічки ліворуч.

Приклад 6.

Записати програми машини Т’юринга, що правильно обчислює функції

а) ,

б) .

Розв’язання. а) Функція здійснює перехід за допомогою команд:

.

б) Функція здійснює перехід за допомогою команд

.

Відповідну машину Т’юринга назвали О.

Приклад 7.

Побудувати машину Т’юринга (зміщення ліворуч) та (зміщення праворуч).

Перша з стандартного початкового положення перебудовує вхідне слово в те саме слово і зупиняється, оглядаючи крайню ліву комірку з нулем за допомогою команд: .

Програму машини можна отримати з програми машини шляхом заміни символа “ ” на символ “ ”. Існує програма, яку називають транспозицією (позначають ), що дозволяє здійснити перехід .

Композиція машин Т’юринга.

Нехай задані машини Т’юринга і , що мають загальний зовнішній алфавіт і алфавіти внутрішніх станів та . Композицією машин (або добутком машини на ) та називається нова машина з тим самим зовнішнім алфавітом і внутрішнім алфавітом та програмою, що отримуємо наступним чином: у всіх командах із , що містять символ зупинки заміняємо його на . Всі інші символи в командах з залишаються незмінними. В командах з символ залишається незмінним, а всі інші стани заміняємо відповідно на . Сукупність всіх команд, що отримані за вищезазначеними правилами утворює програму машини композиції .

Поняття композиції є зручним інструментом для конструювання машин Т’юринга.

Теза Т’юринга.

Чисельні дослідження вчених та багаторічний досвід показує, що клас функцій, які можуть бути обчислені за допомогою машин Т’юринга дуже великий. Кожну функцію, для обчислення значень якої існує алгоритм, можна обчислити за допомогою деякої машини Т’юринга. Цей факт дав підстави Алану Т’юрингу висунути гіпотезу, яку назвали основною гіпотезою теорії алгоритмів або тезою Т’юринга.

Для знаходження значень функції, що задана в деякому алфавіті, тоді і тільки існує алгоритм, коли функція є обчислювальною за Т’юрингом, тобто, коли вона може обчислюватись на відповідній машині Т’юринга.

Зауваження 1. Дана теза не може бути доведена математично, так як одна із сторін тези, а саме поняття алгоритму не є математично точним поняттям.

Зауваження 2. Теоретично існує можливість того, що теза Т”юринга буде спростована, але для цього необхідно створити функцію, для обчислення якої існує алгоритм, а машину Т’юринга для її обчислення створити не можна. Але це малоймовірно.

Лекція №5

Машина Поста.

1. Структура машина Поста.

2. Робота Машина Поста.

3. Обчислювальні за Постом функції. Теза Поста.