Функції, обчислюванні за Тьюрінгом. Теза Тьюрінга.

Означення. Функція , , називається частковою числовою функцією, якщо аргументи  набувають значень з підмножин множини  натуральних чисел і сама вона набуває значень в підмножині множини  натуральних чисел. Таким чином, часткова числова функція – це відображення : .

Область визначення часткової числової функції

;

множина значень

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

За точним означення алгоритму, алгоритм – це машина Тьюрінга, алгоритмічний процес – це процес роботи машини Тьюрінга. Побудуємо машину Тьюрінга, яка обчислює функцію .

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

Зобразимо натуральні числа  в алфавіті  (в одиничному коді) у такий спосіб: будь-яке число  зображається словом , набір  зображається словом

                                          (1)

Машина  починає переробку (даного) слова (1) зі стандартного початкового стану. Якщо функція  визначена при даному наборі аргументів , то машина  переробить (дане) слово (1) у слово ; якщо функція не визначена, то машина  буде працювати нескінченно.

Означення. Часткова числова функція  називається обчислюванною за Тьюрінгом, якщо існує машина Тьюрінга  така, що

1)

2) для будь-якого набору  такого, що

3) для будь-якого набору  такого, що  не визначено машина , запущена в стандартному початковому стані, працює нескінченно.

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

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

Приклад. Для будь-якої машини Тьюрінга  існує еквівалентна їй машина, що не містить у командах символ .

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

 

⇐ Предыдущая1234567

Поделиться: