Машина Тюрінга для опису алгоритмів

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ВСП ЗВО “Відкритий міжнародний університет “Україна”

Миколаївський інститут розвитку людини

Кафедра економіки та інформаційних технологій

Курсова робота

З дисципліни «Алгоритми та структури даних»

На тему: Машина Тюрінга для опису алгоритмів

Роботу виконав:

Студент(ка): Приходько Олексій Сергійович

Миколаїв 2021

Зміст

Список скорочень

1. Історія розвитку Машини Тюрінга та принципи її використання

2. Створення Машини Тюрінга

3. Системи числення, правила переведення чисел з однієї системи числення в іншу

Висновки

Список використаних джерел

Додаток

Список скорочень

МТ-(машина Тюрінга).

Q - осередок зберігає символ стану, а Р - осередок - символ зсуву.

1. Історія розвитку Машини Тюрінга та принцип її використання

Машина Тюрінга -- математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму. Названа на честь англійського математика Алана Тюрінга, який запропонував це поняття у 1936. Аналогічну конструкцію машини згодом і незалежно від Тюрінга ввів американський математик Еміль Пост.

Основна ідея, що лежить в основі машини Тюрінга, дуже проста.

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

Історія виникнення Машини Тюрінга.

Формальні визначення алгоритму з'явилися в тридцятих-сорокових роках 20 століття. Одним із перших було визначення англійського математика Алана Тюрінга, який у 1936 році описав схему деякої гіпотетичної (абстрактної) машини і запропонував називати алгоритмами те, що вміє робити така машина. При цьому визначенні, якщо щось не може бути зроблено машиною Тюрінга, це вже не алгоритм. Інакше кажучи, Тюрінг формалізував правила виконання дій за допомогою опису роботи деякої конструкції.

Визначення

У кожної машини Тюрінга є стрічка, потенційно нескінченна в обидві сторони. Є скінченна множина символів стрічки S0, …, Sn, що називається алфавітом машини. У кожен момент часу кожна комірка може бути зайнята не більш ніж одним символом. Машина має деяку скінченну множину внутрішніх станів q0, q1, …, qn. У кожен даний момент часу машина знаходиться лише в одному із цих станів.

Нарешті, є голівка, яка у кожен даний момент часу знаходиться на одній із комірок стрічки. Машина діє не безупинно, а лише у дискретні моменти часу. Якщо у якийсь момент t голівка сприймає комірку (тобто знаходиться на комірці), що містить символ Si, і машина знаходиться у внутрішньому стані qj, то дія машини визначена однією із чотирьох дій,

голівка затирає символ Si, і записує у тій же комірці новий символ Sk,

голівка пересувається в сусідню ліву комірку,

голівка пересувається в сусідню праву комірку,

машина зупиняється.

У випадках (1)-(3) машина переходить у новий внутрішній стан qr, і готова знову до дії у наступний момент t + 1. Припустимо, що символ S0 представляє порожню комірку, і отже, голівка завжди сприймає деякий символ.

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

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

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

Можливості машини Тюрінга,

Багатство можливостей конструкції Тюрінга виявляється в тому, що якщо якісь алгоритми A та B реалізуються машинами Тюрінга, то можна будувати програми машин Тюрінга, які реалізують композиції алгоритмів A та B, наприклад, виконати A, потім виконати B або виконати A. Якщо в результаті утворилося слово так, то виконати B. У протилежному випадку не виконувати B або виконувати по черзі A, B, поки B не дасть відповідь ні.

У інтуїтивному сенсі такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Тюрінга служить одним із засобів обґрунтування універсальності конструкції Тюрінга.

Реалізованість таких композицій доводиться у загальному вигляді, незалежно від особливостей конкретних алгоритмів A та B. Доведення полягає в тому, що вказується засіб побудови з програм A та B програми потрібної композиції. Нехай, наприклад, потрібно побудувати машину А*В , еквівалентну послідовному виконанню алгоритмів A та B. Поки виконується алгоритм A, у програмі А*В працює частина A без урахування частини B. Коли алгоритм A дійде до кінця, то замість зупинки відбудеться перехід у перший стан частини B, і потім частина B буде працювати звичайним чином, наче частини A і не було.

Аналогічно конструюють й інші композиції машин Тюрінга; щораз будуються загальні правила: що на що змінювати у вихідних програмах.

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

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

Лямбда-числення, або л-числення -- формальна система, що використовується в теоретичній кібернетиці для дослідження визначення функції, застосування функції, та рекурсії. Це числення було запропоноване Алонсо Черчем та Стівеном Кліні в 1930-ті роки, як частина більшої спроби розробити базис математики на основі функцій, а не множин (задля уникнення таких перешкод, як Парадокс Рассела). Однак, Парадокс Кліні-Россера демонструє, що лямбда числення не здатне уникнути теоретико-множинних парадоксів. Не зважаючи на це, лямбда числення виявилось зручним інструментом в дослідженні обчислюваності функцій, та лягло в основу парадигми функціонального програмування. Лямбда числення може розглядатись як ідеалізована, мінімалістича мова програмування, в цьому сенсі лямбда числення подібне до машини Тюринга, іншої мінімалістичної абстракції, здатної визначати будь-який алгоритм. Відмінність між ними полягає в тому, що лямбда числення відповідає функціональній парадигмі визначення алгоритмів, а машина Тюринга, натомість -- імперативній. Тобто, машина Тюринга має певний «стан» -- перелік символів, що можуть змінюватись із кожною наступною інструкцією. На відміну від цього, лямбда числення уникає станів, воно має справу з функціями, котрі отримують значення параметрів та повертають результати обчислень (можливо, інші функції), але не спричиняють до зміни вхідних даних (сталість).

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

Вони не такі складні, як здаються на перший погляд. Просто треба трохи звикнути до префіксної форми запису. Більше немає ні інфіксних (), ні постфіксних (x2) операцій. Крім того, аргументи функцій просто записуються в список після функції, розділені пропуском. Тому, всюди де математики пишуть sin(x) в лямбда-численні пишуть sin x (хоча математики самі часто грішать опусканням дужок. Програмісти в цьому плані культурніші). Так само замість пишуть , а замість x2 - .

2. Створення Машини Тюрінга

Побудувати МТ для опису алгоритмів арифметичних дій (віднімання) в шістнадцятковій системі числення.

Арифметичні операції у всіх позиційних системах обчислення виконуються за одними і тими ж правилами:

- переповнювання розряду наступає тоді, коли значення числа в ньому стає рівним або завбільшки основи;

- складання багаторозрядних чисел відбувається з урахуванням можливих перенесень з молодших розрядів в старші;

- віднімання багаторозрядних чисел відбувається з урахуванням можливих заїмок в старших розрядах;

- множення багаторозрядних чисел відбувається з послідовним множенням множеного на чергову цифру множника;

- перенесення в наступний розряд при складанні і заїмка із старшого розряду при відніманні визначається величиною основи системи обчислення;

- для проведення арифметичних операцій над числами, представленими в різних системах обчислення, необхідно заздалегідь перевести їх в одну систему.

Складання

В основі складання двійкової системи обчислення лежить таблиця складання однорозрядних двійкових чисел:

0 + 0 = 00

0 + 1 = 01

1 + 0 = 01

1 + 1 = 10

Як приклад складемо в стовпчик двійкові числа 1102 і 112.

1102

+

112

10012

Віднімання

Розглянемо віднімання двійкових чисел. В основі лежить таблиця віднімання однозначних двійкових чисел. При відніманні з меншого числа (0) більшого (1) проводиться заїмка із старшого розряду (в таблиці заімки позначена 1 з межею):

13

0 - 0 = _0

0 - 1 = 11

1 - 0 = 01

1 - 1 = 00

Як приклад проведемо віднімання двійкових чисел 1102 і 112.

1102

-

112

112

Множення

В основі множення лежить таблиця множення однозначних чисел:

0 · 0 = _0

0 · 1 = 11

1 · 0 = 01

1 · 1 = 0

Як приклад проведемо множення двійкових чисел 1102 і 112.

1102

х

112

110

110 _

100102

Ділення

Як приклад проведемо розподіл числа 1102 на 112.

110 | 11

____

11 10

0

14

Аналогічно, можна виконувати арифметичні дії у вісімковій і шістнадцятковій системах обчислення.

Приклади арифметичних операції

Приклад

Розвязання

3. Системи числення, правила переведення чисел з однієї системи числення в іншу

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

Класичним прикладом такої системи числення і римська. В ній для запису чисел використовуються букви латинського алфав.ту. При цьому буква I означає одиницю, V - п'ять, Х - десять, L - п'ятдесят, C- сто, D - п'ятсот, M - тисячу. Для отримання кількісного еквівалента числа в римській системі числення треба підсумувати кількісні еквіваленти цифр, що в нього входять.

Набір знаків, які використовуються в системі числення, називаються алфавітом системи.

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

A=a_n-1·p^n-1+a_n-2·p^n-2+…+a₁·p¹+a₀·p⁰

де: р - основа системи числення (деяке позитивне число); а - цифра даної системи числення; n - номер старшого розряду.

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

Двійкова система числення - це позиційна система запису чисел з основою два. У повсякденному житті ми звикли користуватися десяткової системою запису чисел за основою 10. Тобто для запису чисел у нас є десять символів від 0 до 9, а місце кожного символу (позиція) вказує його вага - одиниці, десятки, сотні і т.д. У двійковій системі числення все влаштовано аналогічним чином, тільки для запису чисел у нас всього два символи - 0 і 1. Через те, що для запису числа у нас тільки два символи (0 і 1), вона знайшла широке застосування в електронних пристроях та обчислювальної техніки. Незважаючи на численні спроби використання для обчислень аналогових пристроїв, системи з трійковою логікою (потрійна система числення з символами 0, 1 і 2), системи з двійковій логікою в даний час займають домінуюче становище. Втім, з приходом квантових обчислень, ситуація, швидше за все, зміниться.

Як влаштований запис чисел в двійковій системі

За аналогією зі звичною десятковою системою, при переповненні розряду, необхідно додати ще один, що заповнюється одиницею. У десятковій системі максимальне значення в одному розряді - число 9. Якщо нам потрібно додати одиницю - то поточний розряд обнуляється, а в сусідньому (старшому) розряді з'являється одиниця: 9 додаємо 1, отримуємо 10 (Старший розряд - одиниця, молодший - обнулився) Тепер "порахуємо до десяти" в двійковій системі. 0. У двійковій системі так і буде - 0. 1. У двійковій системі так і буде - 1. 2. Символу 2 в двійковій системі немає. Тому молодший розряд скидається, а старший додається як 1. Отримуємо 10. 3. Додаємо одиницю. Оскільки у нас було 10, молодший розряд може бути збільшений на 1, отримуємо - 11. 4. Молодший розряд знову досяг максимального значення, тому ми повинні його скинути, але наступний розряд теж досяг максимального значення (1), його теж скидаємо і додаємо новий розряд. Отримуємо - 100. 5. Додаємо одиницю в молодший регістр. У нас було записано число 4 як 100, додаємо 1 в молодший розряд і отримуємо 101. 6. Додаємо одиницю в молодший розряд, але він досяг максимального значення, скидаємо його і додаємо одиницю в наступний. Отримуємо 110. 7. Додаємо одиницю в молодший регістр. Отримуємо - 111. 8. Намагаємося додати одиницю до двійкового числа 111 і бачимо, що нам потрібно послідовно скинути вже цілих три розряди і додати ще один розряд. Отримаємо 1000. 9. Додаємо одиницю до двійкового числа 1000, отримуємо - 1001. 10. Додаємо одиницю до молодшого розряду, але він досяг максимального значення, скидаємо його і додаємо одиницю до наступного. Отримуємо 1010. Підведемо підсумки:

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

У десятковій системі	У двійковій системі
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010

Як розрізняють числа, записані в двійковій і десяткової системах

Для того, щоб не переплутати число 100, записане в десятковій системі з числом 100 в двійковій (що еквівалентне 4 в десяткового) використовують додаткові символи в кінці або на початку числа. Наприклад: 100₁₀ и100₂. В даному випадку у вигляді нижнього індексу вказується основа системи числення. У літературі, присвяченій програмування найчастіше використовують позначення чисел, що застосовуються в сімействі мов програмування С (С. С #, C ++). У цих мовах прийнято позначати двійкові числа префіксом 0b. Тоді 100 в десятковій системі буде записано без змін, а 100 в двійковій системі буде записано як 0b100.

Додавання і віднімання двійкових чисел Додавання і віднімання двійкових чисел можна робити абсолютно аналогічно принципам додавання і віднімання "в стовпчик" десяткових чисел. Проведемо складання двох чисел 7 і 9. У двійковій системі числення 7₁₀ = 111₂ 9₁₀ = 1001₂ Тоді

Таблиця 2 16₁₀ =10000₂

			1	1	1
+		1	0	0	1
	1	0	0	0	0

Як бачимо, складання 1 і 1 в молодшому розряді призведе до досягнення максимального значення, тобто він повинен бути скинутий (в нуль), а одиниця повинна бути додана до наступного розряду. Але там при додаванні вже є одиниця і додавання одиниці призведе нас до аналогічних дій - знову скидаємо розряд в нуль, переносимо одиницю в наступний і так далі. Перетворення чисел з двійкової системи в десяткову

Для перетворення чисел, записаних в двійковій системі, в десяткову, нам буде потрібно таблиця ступенів числа 2. Запишемо ступеня двійки у вигляді наступного рядка:

Таблиця 3 Тепер будь-яке двійкове число можна буде перерахувати в десяткове наступним чином:

256	128	64	32	16	8	4	2	1

Таблиця 4 Таким чином 1001101₂ = 77₁₀.

+256	+128	+64	+32	+16	+8	+4	+2	+1	Результат перерахунку
		1	0	0	1	1	0	1	64+8+4+1 = 77

Шістнадцяткова система числення -- позиційна система числення з цілочисленому основи 16. Алфавіт системи числення-- (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Іншими словами, використовуються цифри від 0 до 9 і латинські літери від A до F для позначення цифр від 1010 до 1510. Широко використовується в низкоуровневом програмуванні та комп'ютерної документації, оскільки в сучасних комп'ютерах мінімальною одиницею пам'яті є 8-бітовий байт, значення якого зручно записувати двома шістнадцятковими цифрами. Таке використання розпочалося з системи IBM/360, де вся документація використовувала шістнадцяткову систему, в той час як в інших документації комп'ютерних систем того часу (навіть з 8-бітними символами, як, наприклад, PDP-11 або БЭСМ-6) використовували вісімкову систему. В стандарті Unicode номер символу прийнято записувати в шістнадцятковому вигляді, використовуючи не менше 4 цифр (при необхідності -- з ведучими нулями). Шістнадцятковий колір -- запис трьох компонент кольору (R, G і B) в шістнадцятковому вигляді.

Способи запису:

В математиці основа системи числення прийнято вказувати в десятковій системі у нижньому індексі. Наприклад, десяткове число 1443 можна записати як 144310или як 5A316.

Приклад 1. Перетворити двійкове число 1110102 на шістандцятковий еквівалент. Для перетворення двійкового числа на шістандцятковий еквівалент треба поділити його на тетроди, починаючи з наймолодшого розряду, а потім кожну тетроду замінити еквівалентною шістнадцятковою цифрою. Значення молодшої тетроди 10102 = А16 , старшої - 00112 = 316. Отже 1110102 = 3А16.

Приклад 2. Перетворити шістнадцяткове число 7F16 на двійковий еквівалент. Для перетворення шістнадцяткового числа на двійковий еквівалент кожну шістнадцяткову цифру слід замінити на двійковий еквівалент - тетроду (табл. 5). Еквівалентом шістнадцяткової цифри 716 є двійкове число 01112, а цифри F16 -- число 11112. Отже, 7F16 = 111101112.

Приклад 3. Перетворити шістнадцяткове число 2С6Е16 на десятковий еквівалент. Перетворення виконують згідно з табл. 1. Кожну цифру шістнадцяткового числа множать на відповідну вагу позиції. Сума цих добутків дає десяткове число 11374₁₀.

Таблиця 5 - Двійкові та шістнадцяткові еквіваленти десяткових чисел

Таблиця 6 - Перетворення десяткового числа на десяткове

Приклад 4. Перетворити десяткове число 15797 на шістнадцятко вий еквівалент.

При перетворенні десяткове число 15797₁₀ ділять на 16, що дає частку 987₁₀ і остачу 5₁₀ = 5₁₆. Таким чином, молодший розряд шістнадцяткового числа має значення 5. Частка 98710 стає діленим і її знову ділять на 16, що дає частку 61₁₀ і остачу 11₁₀ = В₁₆, яка стає значенням другого розряду шістнадцяткового числа.

Ділення 611₀ на 16 дає частку 3₁₀ і остачу 13₁₀ = D₁₆. Ділення 3₁₀ на 16 дає частку 0 і остачу 3₁₀ = 3₁₆ . Оскільки остання частка дорівнює 0, то цифра 3₁₆ стає значенням старшого розряду шістнадцяткового числа:

1579710 : 16 = 987₁₀ остача 5₁₀ = 5₁₆

987₁₀ : 16 = 61₁₀ остача 11₁₀ = В₁₆

61₁₀ : 16 = 3₁₀ остача 13₁₀ = D₁₆

3₁₀ : 16 = 0 остача 3₁₀ = 3₁₆

3 D В 5

Отже, 15797₁₀ = 3DB5₁₆.

Перетворення чисел із шістнадцяткової системи у десяткову

Розглянемо, як перетворити шістнадцяткове число 2DB₁₆ у його десятковий еквівалент. Ваги перших трьх розрядів шістнадцяткового числа рівні відповідно 256, 16 і 1.

Рис.1

У цьому шістнадцятковому числі є одиннадцять одиниць, в розряді з вагою 16 стоїть число 13, яке при множенні на вагу розряду дає число 208, а двійка в розряді з вагою 256 позначає число 512. Складаючи суму 11+208+512, знаходимо число 73110. Таким чином, 2DB16=73110.

Перетворення чисел із десяткової системи в шістнадцяткову

Розглянемо тепер зворотне перетворення десяткового числа 47 в його шістнадцятковий еквівалент. Покажемо процедуру послідовних ділень на 16.

Рис.2

Перше ділення десяткового числа 47 на 16 дає частку 2 і остачу 15. Цю остачу (тобто число F в шістнадцятковій системі) слід взяти як останню вагому цифру шуканого шістнадцяткового числа. Частку (у даному випадку 2) потрібно прийняти далі як ділиме і знову розділити його на 16. У результаті получиться частка 0 з остачею 2; цю цифру потрібно вважати наступною цифрою шуканого шістнадцяткового числа. На цьому процес перетворення закінчується, оскільки получилась частка, рівна 0. Запишемо результат: 47₁₀=2F₁₆.

Перетворення чисел із шістнадцяткової системи у двійкову

Рис.3

Перетворення чисел із шістнадцяткової системи у двійкову та із двійкової системи у шістнадцяткову - це типова операція, що реалізується у мікропроцесорах та ЕОМ. Розглянемо це перетворення на прикладі числа С316 і знайдемо еквівалентне йому двійкове число. Нижче показано, як кожний символ шіснадцяткового числа переводиться в його чотиризначний двійковий еквівалент.

Шістнадцятковий символ С відповідає чотирирозрядному двійковому числу 1100, а шіснадцятковий символ 3 - двійковому числу 0011. Об'єднуючи ці дві двійкові групи, отримуємо С316=110000112.

Перетворення чисел із двійкової системи у шістнадцяткову

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

Рис.4

В результаті маємо 111010102=ЕА16.

Десяткова система числення - позиційна система числення по целочисленному основи 10. Одна з найбільш поширених систем. У ній використовуються цифри 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, звані арабськими цифрами. Передбачається, що основою 10 пов'язано з кількістю пальців рук у людини.

1. Визначення

Один десятковий розряд в десятковій системі числення іноді називають декадою. У цифровій електроніці одному десятковому розряду десяткової системи числення відповідає один десятковий тригер.

Ціле число x в десятковій системі числення представляється у вигляді кінцевої лінійної комбінації степенів числа 10:

,

Де - Це цілі числа, звані цифрами, що задовольняють нерівності

Зазвичай для ненульового числа x вимагають, щоб старша цифра a _{n - 1} в десятковому поданні x була також ненульовий.

Наприклад, число сто три представляється в десятковій системі числення у вигляді:

За допомогою n позицій в десятковій системі числення можна записати цілі числа від 0 до 10 ⁿ - 1, Тобто, всього 10 ⁿ різних чисел.

Дробові числа записуються у вигляді рядка цифр з роздільником десяткова кома, званої десятковим дробом:

де n - число розрядів цілої частини числа, m - число розрядів дробової частини числа.

Переведення чисел із однієї системи в іншу

Переведення чисел із будь-якої системи числення в десяткову

Для переведення чисел із будь-якої системи числення в десяткову необхідно це число представити у вигляді полінома і розкрити всі члени полінома в десятковій системі числення.

Приклад:

Таблиця 7 Перевід чисел із 2-кової с.ч. у 8-кову та 16-кову с.ч. та навпаки

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

Далі нижче буде наведено принцип роботи машини Тюрінга.

Здвиг праворуч: [ {1}1111111-111= ]"

Здвиг праворуч: [ 1{1}111111-111= ]"

Здвиг праворуч: [ 11{1}11111-111= ]"

Здвиг праворуч: [ 111{1}1111-111= ]"

Здвиг праворуч: [ 1111{1}111-111= ]"

Здвиг праворуч: [ 11111{1}11-111= ]"

Здвиг праворуч: [ 111111{1}1-111= ]"

Здвиг праворуч: [ 1111111{1}-111= ]"

Здвиг праворуч: [ 11111111{-}111= ]"

Здвиг праворуч: [ 11111111-{1}11= ]"

Здвиг праворуч: [ 11111111-1{1}1= ]"

Здвиг праворуч: [ 11111111-11{1}= ]"

Здвиг праворуч: [ 11111111-111{=} ]"

Здвиг ліворуч: [ 11111111-11{1} ]"

Здвиг ліворуч: [ 11111111-1{1}= ]"

Здвиг ліворуч: [ 11111111-{1}1= ]"

Здвиг ліворуч: [ 11111111{-}11= ]"

Перевірка: [ 1111111{1}-11= ]"

Здвиг праворуч: [ 1111111 {-}11= ]"

Здвиг праворуч: [ 1111111 -{1}1= ]"

Здвиг праворуч: [ 1111111 -1{1}= ]"

Здвиг праворуч: [ 1111111 -11{=} ]"

Здвиг ліворуч: [ 1111111 -1{1} ]"

Здвиг ліворуч: [ 1111111 -{1}= ]"

Здвиг ліворуч: [ 1111111 {-}1= ]"

Перевірка: [ 1111111{ }-1= ]"

Перевірка: [ 111111{1} -1= ]"

Здвиг праворуч: [ 111111 { }-1= ]"

Здвиг праворуч: [ 111111 {-}1= ]"

Здвиг праворуч: [ 111111 -{1}= ]"

Здвиг праворуч: [ 111111 -1{=} ]"

Перевірка: [ 111111 -{1} ]"

Вихід на мінус: [ 111111 {-}= ]"

Перевірка: [ 111111 { }-= ]"

Перевірка: [ 111111{ } -= ]"

Перевірка: [ 11111{1} -= ]"

Здвиг праворуч: [ 11111 { } -= ]"

Здвиг праворуч: [ 11111 { }-= ]"

Здвиг праворуч: [ 11111 {-}= ]"

Здвиг праворуч: [ 11111 -{=} ]"

Вихід на мінус : [ 11111 {-} ]"

Кінець: [ 11111 { }- ]"

Машина Тьюрінга

Одне з уточнень понять алгоритму було дано Е. Постом і А. Тьюрінгом незалежно один від одного в 1936-1937гг. Основна думка їх полягала в тому, що алгоритмічні процеси - це процеси, які може здійснити відповідним чином влаштована "машина". Ними були описані гіпотетичні (умовні) пристрої, які отримали назву «Машина Поста» і «Машина Тьюрінга» (МТ). Так як в них багато спільного, то розглянемо тільки машину Тьюрінга.

Машина Тьюрінга складається з наступних частин:

1. Інформаційної стрічки, що представляє нескінченну пам'ять машини. Це нескінченна стрічка, розділена на осередки. У кожній клітинці можна помістити лише один символ з можливого їх безлічі S = {S 1, S 2, ...., S m}, яка складає зовнішній алфавіт МТ. У цьому алфавіті один з символів (нехай це буде S 1) відповідає порожньому символу.

2. Голівки, що зчитує - чутливого спеціального елемента, здатного оглядати вміст комірок. Стрічка може переміщатися уздовж головки так, що в кожний момент часу головка оглядає одну клітинку.

3. Керуючого пристрою (УУ), яке в кожний момент часу знаходиться в деякому стані. Число станів звичайно. Позначимо множину станів як {q 1, q 2, ..., q n}. Серед станів одне відповідає заключного, при якому МТ зупиняється. УУ пов'язано зі зчитування голівкою.

Крім того, УУ виробляє три команди на переміщення стрічки: П, Л, Н, де

П - переміститися на сусідню праворуч осередок;

Л - переміститися сусідню зліва осередок;

Н - продовжувати оглядати ту ж комірку.

Сукупність символів {q 1, q 2, ..., q n} і {П, Л, Н} утворюють внутрішній алфавіт МТ.

Робота машини відбувається в дискретному часі. У початковий момент часу в обмежений ділянка стрічки записано слово в алфавіті S, що представляє вихідна умова завдання. В інших осередках передбачається записаним порожній символ. Керуючий пристрій знаходиться в початковому стані q 1. На кожному кроці роботи МТ оглядає на стрічці символ S k і залежно від нього і від стану q i, переходить в стан q j, замінює S k на символ S l і пересуває стрічку (або ні) на одну клітинку.

Кожна елементарна операція має вигляд q i S k ® q j S l П (Л, Н).

Безліч елементарних операцій впорядковано і утворить абстрактну програму, яка представляє алгоритм.

Зчитує головка і керуючий пристрій утворюють логічний блок, який представляє собою (2,3)-полюснік.

SHAPE \ * MERGEFORMAT S k

S 1

ЛБ

q i

q j

{П, Л, Н}

Структура МТ має наступний вигляд:

		S 1	S 2	...	S k	...	S m

Q

P

S l

S k

q i

q j

П (Л, Н)

Рис. 5

У них відбувається затримка даних символів до початку наступного такту.

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

Якщо зупинка і сигнал про зупинку ніколи не надходять, то говорять, що МТ не може бути застосована до послідовності U.

Розглянемо функціонування МТ на прикладі складання двох чисел, які будемо зображати у вигляді набору одиниць.

Зовнішній алфавіт буде складатися з символів: {1, +, Щ}, де Щ - порожній символ.

Внутрішній алфавіт буде складатися з чотирьох символів {q 1, q 2, q 3,!}, Де символ q 1 означає початковий стан, а! - Заключне стан.

Абстрактна програма, що реалізує операцію складання, буде мати вигляд: 1q 1 > Щq 3 П

1q 3 > 1q 3 П + Q 3 > + q 3 П

Щq 3 > 1q 2 H + q 2 > + q 2 Л

1q 2 > 1q 2 Л Щq 2 > Щq 1 П + Q 1 > Щ! Н

Основна гіпотеза теорії алгоритмів (теза Черча),

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

Обґрунтування гіпотези.

Мова не йде про доведення гіпотези, так як вона містить не формалізовані математичні поняття.

Впевненість у справедливості гіпотези заснована, головним чином, на досвіді. Усі відомі до цього часу алгоритми можуть бути задані за допомогою тьюрінгових функціональних схем. Крім того, всередині самої теорії алгоритмів основна гіпотеза не застосовується, тобто при доказі теорем цієї теорії посилань на основну гіпотезу не робиться.

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

Універсальна машина Тюрінга

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

Вимоги до кодування:

1. різним буквах повинні зіставлятися різні кодові групи, і одна і та ж буква скрізь замінюється однієї і тієї ж кодової групою;

2. Рядок тексту повинна однозначним чином розбиватися на кодові групи.

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

Теорема Триттера визначає, що мінімальна універсальна машина Тюрінга має 4 символу в зовнішньому алфавіті та її УУ має 6 станів.

Застережні СКЛАДНОСТІ Алгоритм

Оцінка алгоритму

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

Під просторової ефективністю розуміють обсяг пам'яті, необхідної для виконання програми.

Тимчасова ефективність програми визначається часом, необхідним для її виконання. При цьому необхідно враховувати наступні моменти.

По-перше, час роботи програми може обмежуватися її призначенням. Якщо ця програма реального часу, наприклад, бронювання авіаквитків, то час обробки завдання не повинно перевищувати декількох хвилин. Якщо ця програма автоматичного управління будь-яким пристроєм (наприклад, управлінням літака), то вона повинна «встигати» відпрацьовувати надходить, і своєчасно видавати керуючі впливу.

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

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

Найпростішим способом оцінити алгоритм - зіставити йому число елементарних операцій в описі. При реалізації це може бути кількість команд у програмі або обсяг пам'яті, яку займає програма. У цьому випадку оцінка d алгоритму A є деяке число k: d (A) = k.

Більш цікавою може бути оцінка пари: алгоритму A і конкретного завдання a, яка їм вирішується. Наприклад, оцінкою може бути обсяг пам'яті під програму, вихідні та проміжні дані, необхідні для вирішення даної задачі a, або час для вирішення цього завдання з допомогою алгоритму A. У будь-якому випадку це буде число d (A (a)) = k (a).

Властивість масовості алгоритму припускає, що алгоритм буде використовуватися для вирішення класу A подібних завдань, з різними вихідними даними. Тому більш складною оцінкою буде оцінка як функція властивості завдання. Cопоставім кожній задачі з класу задач, що розв'язуються алгоритмом, деякий вектор числових параметрів задачі N = (n1, n2, ..., nt). У цьому випадку оцінка d (A (A)) = k (N), і це вже буде функція від параметрів задачі.

Приклад. Необхідно цінувати алгоритм Прима - алгоритм виділення мінімального кістяка. У першому випадку ми розглядаємо число операторів в описі програми, що реалізує алгоритм - число порівнянь, умовних переходів і т.д. У другому випадку аналізується робота алгоритму (програми) виділення кістяка деякого заданого графа і визначається необхідний обсяг пам'яті. В останньому випадку графу припишемо параметри - число вершин у графі і число його ребер, і можна порівняти вирішення завдання функцію від цих параметрів.

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

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

Приклад. Нехай функція оцінки має вигляд як на мал.1. Необхідно вирішувати задачі з параметром n, що лежить в межах від 5 до 15. У цьому випадку необхідно вибрати для реалізації алгоритм A1. Якщо параметр змінюється від 20 до 30, краще використовувати алгоритм A2. Якщо параметр змінюється в межах від 10 до 35, то можливо або вибрати будь-який з даних алгоритмів, або побудувати новий алгоритм, який, наприклад, перевіряє кожен раз значення параметра і вибирає відповідний алгоритм.

машина тюрінг алгоритм арифметичний числення

Висновки

Під час проходження курсу з дисципліни «Теорія алгоритмів» я вчився будувати Машину Тюрінга. Переводити систему числення з двійкового в десятковий та навпаки. Основною темую курсу було дослідження роботи МТ та вцілому. Принцип роботи, знаходження комірок лічильника МТ, опис МТ. Найбільш зацікавило мене те, що при виконанні практичних робіт з дисципліни «Теорія алгоритмів» можна регулувати головку лічильника машини Тюрінга, яка виконує пошук символа на стрічці. Якщо вірно знаходить потрібний символ то машина робить перехід до наступної комірки. І таким чином вона повторюється (виконується) до тих пір поки не вийде на стоп.

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

Список використаних джерел

1. Енциклопедія кібернетики, т. 2, с. 444--446.

2. Good Math, Basics: The Turing Machine (with an interpreter!), 9 лютого 2007.

3. Henk Barendregt 1997.

4. Kluge 2005, сторінка 51.

5. Raъl Rojas, A Tutorial Introduction to the Lambda Calculus(англ.) -(PDF)

6. Wolfengagen, V.E. Combinatory logic in programming. Computations with objects through examples and exercises. - 2-nd ed. - M.: "Center JurInfoR" Ltd., 2003. -- x+337 с. ISBN 5-89158-101-9.

7. Навчальний проект з курсу "Основи програмування": Машина Тюрінга.

8. Рощин А.Г., статевої Р.М. Теорія автоматів. Частина I. Тексти лекцій - М.: МГТУ ГА, 2001. - 76 с.

9. Фалевіч Б.Я. Теорія алгоритмів. - М.: ИНФРА-М, 2006. - С.324.

10. Фаліна М.М. Машина Тьюрінга / / Інформатика. - № 26. - 2005. - С.12-15

11. Теорія алгоритмів Методичний посібник з дисципліни "Математична логіка і теорія алгоритмів» / В.П. Бітюцький, Н.В. Папуловская. Єкатеринбург: ГОУ ВПО УГТУ-УПІ, 2006, с.

Додаток

У додатку буде представлено Англомовну версію машини Тюрінга. Де буде поетапно описано усі кроки виконання дії машини Тюрінга.

Basics: The Turing Machine (with an interpreter!)

Category: Basics * Haskell * Programming * programming

Posted on: February 3, 2007 6:38 PM, by Mark C. Chu-Carroll

As long as I'm doing all of these basics posts, I thought it would be worth explaining just what a Turing machine is. I frequently talk about things being Turing equivalent, and about effective computing systems, and similar things, which all assume you have some clue of what a Turing machine is. And as a bonus, I'm also going to give you a nifty little piece of Haskell source code that's a very basic Turing machine interpreter. (It's for a future entry in the Haskell posts, and it's not entirely finished, but it does work!)

The Turing machine is a very simple kind of theoretical computing device. In fact, it's almost downright trivial. But according to everything that we know and understand about computation, this trivial device is capable of any computation that can be performed by any other computing device.

The basic idea of the Turing machine is very simple. It's a machine that runs on top of a tape, which is made up of a long series of little cells, each of which has a single character written on it. The machine is a read/write head that moves over the tape, and which can store a little bit of information. Each step, the machine looks at the symbol on the cell under the tape head, and based on what it sees there, and whatever little bit of information it has stored, it decides what to do. The things that it can do are change the information it has store, write a new symbol onto the current tape cell, and move one cell left or right.

That's really it. People who like to make computing sound impressive often have very complicated explanations of it - but really, that's all there is to it. The point of it was to be simple - and simple it certainly is. And yet, it can do anything that's computable.

To really understand how that trivial machine can do computations, it helps to be a bit formal. In formal terms, we talk about a turing machine as a tuple: (S, s0, A, T), where:

S is a finite list of possible states that the machine can be in. The state is the information that the machine can store in the head to make decisions. It's a very limited amount of information; you can think of it as either a specific list of states, or a small set of small numbers. For most Turing machines, we'll use it as a specific list of states. (You'll see what I mean in a minute.)

s0 Ѓё S is the initial state - the state that the machine will be in when it starts a computation.

A is the machine's alphabet, which is the set of symbols which can appear on the machine's tape.

T is the machines transition function. This is the real heart of the machine, where the computation is defined. It's a function from the machine state and the alphabet character on the current tape cell to the action that the machine should take. The action is a triple consisting of a new value for the machine's state, a character to write onto the current tape cell, and a direction to move the tape head - either left or right.

So, for example, let's look at a simple machine. This is one of the classic examples: a Turing machine that does subtraction using unary numbers. A unary number "N" is written as a series of N 1s. For the program, we'll give the machine an input in the format "N-M=" written onto the tape; after running the machine, the tape will contain the value of M subtracted from N. So, for example, we could use "1111-11=" as an input; the output would be "11".

The alphabet is the characters "1", " " (blank space), "-" (minus sign), and "=" (equal sign). The machine has four states: {"scanright", "eraseone", "subone", "skip"}. It starts in the state "scanright". It's transition function is given by the following table:

FromState Symbol ToState WriteChar Dir

scanright space scanright space right

scanright 1 scanright 1 right

scanright minus scanright minus right

scanright equal eraseone space left

eraseone 1 subone equal left

eraseone minus HALT space n/a

subone 1 subone 1 left

subone minus skip minus left

skip space skip space left

skip 1 scanright space right

What this machine does is move to the right until it sees the equal sign; it erases the equal sign and moves to the left, erases one digit off of the second number, and replaces it with the equal sign (so the second number is reduced by one, and the equal sign is moved over one position). Then it scans back to the minus sign (which separates the two numbers), and erases one digit of the first number, and then switches back to scanning to the right for the equal. So one at a time, it erases one digit from each of the two numbers. When it reaches the equal sign, and starts going back to erase a digit from the second number, and hits the "-" before it finds a digit, that means its done, so it stops. Let's look at a simple execution trace. In the trace, I'll write the machine state, followed by a colon, followed by the tape contents surrounded by "[]", with the current tape cell surrounded by "{}".

scanright: [ {1}1111111-111= ]"

scanright: [ 1{1}111111-111= ]"

scanright: [ 11{1}11111-111= ]"

scanright: [ 111{1}1111-111= ]"

scanright: [ 1111{1}111-111= ]"

scanright: [ 11111{1}11-111= ]"

scanright: [ 111111{1}1-111= ]"

scanright: [ 1111111{1}-111= ]"

scanright: [ 11111111{-}111= ]"

scanright: [ 11111111-{1}11= ]"

scanright: [ 11111111-1{1}1= ]"

scanright: [ 11111111-11{1}= ]"

scanright: [ 11111111-111{=} ]"

eraseone : [ 11111111-11{1} ]"

subone : [ 11111111-1{1}= ]"

subone : [ 11111111-{1}1= ]"

subone : [ 11111111{-}11= ]"

skip : [ 1111111{1}-11= ]"

scanright: [ 1111111 {-}11= ]"

scanright: [ 1111111 -{1}1= ]"

scanright: [ 1111111 -1{1}= ]"

scanright: [ 1111111 -11{=} ]"

eraseone : [ 1111111 -1{1} ]"

subone : [ 1111111 -{1}= ]"

subone : [ 1111111 {-}1= ]"

skip : [ 1111111{ }-1= ]"

skip : [ 111111{1} -1= ]"

scanright: [ 111111 { }-1= ]"

scanright: [ 111111 {-}1= ]"

scanright: [ 111111 -{1}= ]"

scanright: [ 111111 -1{=} ]"

eraseone : [ 111111 -{1} ]"

subone : [ 111111 {-}= ]"

skip : [ 111111 { }-= ]"

skip : [ 111111{ } -= ]"

skip : [ 11111{1} -= ]"

scanright: [ 11111 { } -= ]"

scanright: [ 11111 { }-= ]"

scanright: [ 11111 {-}= ]"

scanright: [ 11111 -{=} ]"

eraseone : [ 11111 {-} ]"

Halt: [ 11111 { }- ]"

See, it works!

One really important thing to understand here is that we do not have a program. What we just did was define a Turing machine that does subtraction. The machine does not take any instructions: the states and the transition function are an intrinsic part of the machine. So the only thing this machine can do is to subtract.

The real genius of Turing wasn't just defining this simple computing machine. It was realizing the concept of the program: you could design a Turing machine whose input tape contained a description of a Turing machine - that is a program - followed by an input to the program. This single machine - the Universal Turing machine - could simulate any other Turing machine; one machine which could perform any computation.

Turing machines are a lot of fun to play with. Figuring out how to do things can be fascinating. Figuring out how to define a Universal turing machine's transition function is an amazing thing to do; it's astonishing how simple the universal machine can be!

For your enjoyment, I've implemented a Turing machine programming language. You feed it a Turing machine description, and an input string, and it will give you a trace of the machines execution like the one above. Here's the specification of the subtraction machine written in my little Turing language:

states { "scanright" "eraseone" "subtractOneFromResult" "skipblanks" } initial "scanright"

alphabet { '1' ' ' '=' '-' } blank ' '

trans from "scanright" to "scanright" on (' ') write ' ' move right

trans from "scanright" to "scanright" on ('1') write '1' move right

trans from "scanright" to "scanright" on ('-') write '-' move right

trans from "scanright" to "eraseone" on ('=') write ' ' move left

trans from "eraseone" to "subtractOneFromResult" on ('1') write '=' move left

trans from "eraseone" to "Halt" on ('-') write ' ' move left

trans from "subtractOneFromResult" to "subtractOneFromResult" on ('1') write '1' move left

trans from "subtractOneFromResult" to "skipblanks" on ('-') write '-' move left

trans from "skipblanks" to "skipblanks" on (' ') write ' ' move left

trans from "skipblanks" to "scanright" on ('1') write ' ' move right

I think it's pretty clear as a syntax, but it still needs explanation.

The first line declares the possible states of the machine, and what state it starts in. This machine has four possible states - "scanright", "eraseone", "subtractOneFromResult", and "skipblanks". When the machine starts, it will be in the state "skipright".

The second line declares the set of symbols that can appear on the tape, including what symbol will initially appear on any tape cell whose value wasn't specified by the input. For this machine the symbols are the digit 1, a blank space, the equal sign, and the subtraction symbol; the blank symbol is on any tape cell whose initial value wasn't specified.

After that is a series of transition declarations. Each declaration specifies what the machine will do for a given pair of initial state and tape symbol. So, for example, if the machine is in state "scanright", and the current tape cell contains the equal-to sign, then the machine will change to state "eraseone", write a blank onto the tape cell (erasing the "=" sign), and move the tape cell one position to the left.

Finally, the code. You'll need GHCI to run it; at the moment, it won't work in Hugs (I don't have the parsing library in my version of Hugs), and I haven't worked out the linkage stuff to make it work under the GHC compiled mode.

-- A Simple Turing machine interpreter

-- Copyright 2007 by Mark C. Chu-Carroll

-- markcc@gmail.com

-- http://scienceblogs.com/goodmath

-- You can do anything you want with this code so long as you

-- leave this copyright notice intact.

module Turing where

import Text.ParserCombinators.Parsec

import qualified Text.ParserCombinators.Parsec.Token as P

import Text.ParserCombinators.Parsec.Language

import System.Environment

data Motion = MoveLeft | MoveRight deriving (Show)

data Transition = Transition String String [Char] Motion Char deriving (Show)

-- from to on move write

data TuringMachine = Machine [String] String [Char] Char [Transition] deriving (Show)

-- states initial alphabet blank transitions

data MachineState = TMState [Char] Char [Char] String deriving (Show)

-- tape-left curcell curstate

getBlankSym :: TuringMachine -> Char

getBlankSym (Machine _ _ _ bl _) = bl

findMatchingTransition :: [Transition] -> String -> Char -> Maybe Transition

findMatchingTransition [] _ _ = Nothing

findMatchingTransition translist state c =

let matches = filter (transitionMatches state c) translist

in case matches of

[] -> Nothing

t:[] -> Just t