Відмінність МТ від сучасного комп’ютера

 

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

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

Принципова різниця між МТ і обчислювальними машинами полягає в тому, що її запам'ятовуючий пристрій являє собою нескінченну стрічку, яка не знає можливості її фізичної реалізації. Стрічка розділена на клітинки, в кожній із яких може бути записаний один із символів кінцевого алфавіту: A = {a₀, a₁,..., a_m}, який називають вхідним алфавітом МТ. У процесі роботи МТ може бути заповнене кінцеве число клітинок. Зчитуюча головка в кожен момент часу оглядає клітинку стрічки, залежно від символу в ній та стану управляючого пристрою, записує в клітинку новий символ або залишає його без зміни, переміщується на клітинку вліво, вправо або залишається на місці. При цьому управляючий пристрій переходить в новий стан або залишається в попередньому. Серед станів управляючого пристрою виділено початковий – q₀ і заключний – q_к стани.

Таким чином, за один такт роботи МТ може зчитати символ, записати замість нього новий або залишити його без зміни і перемістити головку на одну клітинку вліво або вправо, або залишити її на місці.

Можна констатувати такі відмінності МТ порівнянно з ЕОМ:

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

2 Зовнішня пам'ять в МТ зображується нескінченою стрічкою, яка розбита на клітинки. Жодна реально існуюча машина не може мати нескінченну стрічку, і в цьому сенсі МТ являє собою лише ідеалізовану схему, яка відображає потенційну можливість збільшення об’єму пам’яті.

Така ідеалізація виправдовується зв’язком між поняттям алгоритму та поняттям машини з потенційно необмеженою пам’яттю [4].

Систему команд МТ можна інтерпретувати і як опис роботи конкретного механізму, і як програму. Природно поставити завдання побудови МТ, яка б реалізувала алгоритм відтворення роботи МТ – універсальної машини U. Універсальна МТ за заданим кодом довільної машини Тьюринга Т та кодуванням вхідного ланцюжка х буде моделювати поведінку машини Т із вхідним ланцюжком х. Існування універсальної машини Тьюринга означає, що систему команд будь–якої машини Тьюринга можна уявити двояко: або як опис роботи конкретного пристрою машини Т, або як програму для універсальної машини U. Для інженера, який проектує систему управління, будь–який алгоритм управління може бути реалізований або апаратурною побудовою відповідної схеми, або у вигляді програми для універсальної управляючої ЕОМ.

 

ПРОГРАМА ALGO 2000

 

Програма ALGO 2000 – це інтерпретатор машини Поста та машини Тьюринга [8]. Під поточною машиною розуміється машина Поста або машина Тьюринга залежно від того, яка з них є активною в даний момент часу. Файл машини Поста має розширення *.pst, а файл МТ – *.tur

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