Наша взаимовыгодная связь https://banwar.org/
Анотація: Визначення машин Тьюринга і класу обчислюваних ними функцій. Приклади роботи машин Тьюринга. Тьюрінгово програмування: послідовна і паралельна композиція, розгалуження (умовний оператор), повторення (оператор циклу)
Основні визначення
Вже згадана в цьому розділі модель алгоритмів була запропонована англійським математиком Тьюрингом в 1937 р ще до створення сучасних комп'ютерів1 Він виходив із загальної ідеї моделювання роботи обчислювача, що оперує відповідно до деякого суворим приписом. У машині Тьюринга розчленовування процесу обчислення на елементарні кроки доведено в даному разі до межі. Елементарним дією є заміна одного символу в комірці на інший і переміщення до сусідньої осередку. При такому підході процес обчислення значно подовжується, але зате логічна структура процесу сильно спрощується і набуває зручний для теоретичного дослідження вид.
Машина Тьюринга (м.т.) складається з необмеженої в обидві сторони стрічки, розбитою на осередки, по якій пересувається головка машини. Така "нескінченність" стрічки є математичною абстракцією, що відбиває потенційну необмеженість пам'яті обчислювача. Зрозуміло, в кожному завершується обчисленні використовується тільки кінцева частина цієї пам'яті - кінцеве число осередків. У кожному осередку стрічки записаний один символ з кінцевого зовнішнього алфавіту машини 
. Головка машини являє кінцевий автомат, який в кожен момент часу знаходиться в одному з внутрішніх станів Q = {q0, q1, ..., qn}. На кожному кроці головка в залежності від свого внутрішнього стану і символу в комірці, яку вона спостерігає, змінює свій внутрішній стан і вміст спостерігається осередки і може зрушити на одну клітинку вправо або вліво або залишитися на місці.
Дамо більш формальне визначення.
Визначення 9.1. Машина Тьюринга - це система виду
що включає наступні компоненти:
Виділимо в алфавіті 
спеціальний порожній символ 
і будемо вважати, що у всіх осередках стрічки, крім кінцевого їх числа, в початковий і в усі наступні моменти знаходиться порожній символ.
Будемо говорити, що деякий символ стирається, якщо він замінюється на порожній. Два слова з 
будемо вважати рівними, якщо вони збігаються після відкидання всіх порожніх символів зліва і справа. наприклад, 
, але 
.
Як і для кінцевих автоматів, програму P можна задавати за допомогою таблиці розміру nxm, рядки якої відповідають станам з Q, а стовпці - символам з вхідного алфавіту 
в якій на перетині рядка qi і шпальти aj варто трійка qk al C - права частина команди qi aj -> qk al C.
Визначення 9.2. Назвемо конфігурацією М.Т. 
в певний момент часу слово K = Wл qi aj Wп, де 
- слово на стрічці лівіше текушего положення головки, qi - внутрішній стан в даний момент, aj - символ, оглядає головкою, 
- слово на стрічці правіше текушего положення головки.
Будемо вважати, що слово Wл aj Wп містить всі значущі символи на стрічці. Тому, з точністю до описаного вище рівності слів, конфігурація визначена однозначно. Зокрема, якщо 
, Тобто порожньо, то лівіше положення головки все осередки порожні, а якщо 
, То правіше положення головки все осередки порожні.
Початкова конфігурація - це конфігурація виду q0w, тобто в початковий момент часу головка в стані q0 оглядає перший символ вхідного слова w. {It Заключна} конфігурація - це конфігурація виду w1 qf w2, в якій машина знаходиться в заключному стані qf.
Визначення 9.3. Скажімо, що конфігурація K = w1 qi aj w2 м.т. 
за один крок (такт) переходить в конфігурацію 
, Якщо в програмі є команда qi aj -> qk al C і при цьому,
Як завжди, через 
позначимо рефлексивне і транзитивне замикання відношення 
а 
буде означати, що конфігурація K за n кроків переходить в K '. (Якщо з контексту ясно, про яку машину йде мова, то індекс будемо опускати).
Приклад 9.1.
Мал.9.1.
Виконання команди q3 0 -> q5 1 П
Наприклад, ситуації, представленої на рис.9.1 зліва відповідає конфігурація 
. Припустимо, що програма P містить команду q30 -> q51 П. Тоді після виконання цієї команди K перейде за один крок в конфігурацію 
, Показану на цьому малюнку праворуч. отже, 
.
Визначення 9.4. Обчислення м.т. 
на вході w - це кінцева або нескінченна послідовність конфігурацій 
така, що K0 = q0w - початкова конфігурація. Ця послідовність кінцева, коли її остання конфігурація Kn = v1 qf v2 - заключна. У цьому випадку обчислення назвемо результативним, а слово v = v1 v2 - його результатом на вході w (завжди будемо припускати, що v не містить порожніх символів зліва і справа).
Визначення 9.5. Скажімо, що м.т. обчислює часткову словникову функцію 
якщо для кожного слова w з області визначення f існує результативне обчислення 
з результатом 
, А якщо f (w) не визначена 
, То обчислення на вході w нескінченно.
Скажімо, що дві м.т. 
і 
еквівалентні, якщо вони обчислюють однакові функції.
Далі ми будемо також розглядати обчислення арифметичних функцій, тобто функцій з натуральними аргументами, які приймають натуральні значення. Для подання натуральних чисел використовуємо унарное кодування: число n буде представлятися як слово з n паличок | n, а послідовні аргументи будемо відокремлювати *.
Визначення 9.6. Скажімо, що м.т. обчислює часткову арифметичну функцію f: Nk -> N, якщо для будь-якого набору чисел (x1, x2, ..., xk), на якому f визначена, існує результативне обчислення на вході 
з результатом 
, а якщо 
, То обчислення на відповідному вході нескінченно.
Аналогічне визначення можна дати і для інших спосбов кодування чисел (двійкового, десяткового і ін.). Нижче ми покажемо, що клас обчислюваних функцій не залежить від вибору одного з таких кодувань.
