Приклади

Наведемо програму для машини Тюрінга, яка обчислює функцію x+y, де x,y - натуральні числа. Необхідно домовитися про представлення цих чисел. Стандартним для машини Тюрінга є представлення натурального числа n послідовністю з n+1 одиниць.

Ідея вирішення могла б полягати у тому, щоб замінити крайній зліва та крайній справа символи "1" на "0", а роздільник "0" - на "1". Якби були доступні відповідні команди, це можна було б зробити просто і швидко, але ми обмежені жорсткими рамками машини Тюрінга. За таких умов схема алгоритму полягає в такому: рухатися вправо до виявлення першої одиниці (початок першого числа); як тільки вона буде виявлена, замінити її на нуль і перейти в інший стан s1. Потім рухатися вправо, поки 0, який розділяє два числа, не буде замінений на 1; при цьому знову змінити стан. Далі рухатися вправо до появи першого нуля (кінця другого доданку). Після цього зсунутися вліво, замінити останню 1 на 0 та зупинитися.

Програма може мати вигляд:

0s0 → 0 s0R

1s0 → 0 s1R

1s1 → 1 s1R

0s1 → 1 s2R

1s2 → 1 s2R

0s2 → 0 s3L

1s3 → 0 s4H.

Наведений приклад показує, що машина Тюрінга є дуже незручною для програмування. Ці незручності пов'язані з тим, що:

* немає довільного доступу до пам'яті; якщо, наприклад, машина вказує на першу комірку, а потрібно перейти до десятої, машина повинна послідовно переглянути другу, третю і т.д. комірку;

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

* дуже обмежений набір команд; відсутні, наприклад, основні арифметичні операції.

Розділ 4. Структури данних

<== попередня сторінка	\|	наступна сторінка ==>
Можливості машини Тюрінга	\|	Необхідність структурування даних. Поняття Структури даних

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.