и більш високого розряду. Очевидно, що в разі зсуву вліво, керуюча головка машини може вийти на порожню клітку у випадку, у разі коли цифри більш високого розряду немає. При цьому машина вписує в порожню клітину цифру 1. При реалізації алгоритму обчислення функції f (n)=n + 1 машина може прибувати лише в двох станах і.
Таким чином, машина Тьюринга, що реалізує алгоритм переходу від n до n + 1 в десятковій системі числення буде мати вигляд:
0123456789 1н 1н 2н 3н 4н 5н 6н 7н 8н 9н 0 ^
Приклад 2. Алгоритм складання натуральних чисел.
Нехай на стрічку подається два числа, заданих наборами паличок; наприклад, 2 і 3. Потрібно скласти ці числа.
Будемо позначати символ складання зірочкою. Таким чином, на стрічці машини буде записано слово
|| * |||. (1)
Потрібно запропонувати функціональну схему, яка будучи застосованою до слова (1), давала б в результаті суму чисел 2 і 3, тобто слово
|||||. (2)
Опишемо процес роботи машини для вирішення завдання. Нехай в початковий момент обозревается найлівіша паличка. Її потрібно зрушити вправо, минаючи всі палички і зірочку до тих пір, поки не буде досягнута перша порожня клітка. У цю порожню клітину вписується першого паличка. Потім потрібно повернутися за другий паличкою і її перенести вправо так само, як це робилося з першої паличкою. Після цієї процедури потрібно повернутися до зірочці, стерти її і зупинитися. Зобразимо все такти роботи машини у вигляді відповідних конфігурацій:
1) || * ||| 11) | * |||| 21) * ||||
1) | * ||| 12) | * |||| 22) * |||||
3) | * ||| 13) 23)
4) | * ||| 14) | * |||| 24) * |||||
5) | * ||| 15) | * |||| 25) * |||||
6) | * ||| 16) * |||| 26 ) * |||||
7) | * ||| 17) * |||| 27 ) * |||||
8) | * |||| 18) * |||| 28) * |||||
9) | * |||| 19) * |||| 29) * |||||
10) | * |||| 20) * |||| 30) |||||
Цей процес дозволяє записати алгоритм у вигляді двовимірної таблиці:
* | н п | н * п | п п * ^ | ^
Таким чином, тут використаний зовнішній алфавіт і стану машини,,,.
Висновок
Таким чином, машина Тьюринга являє собою найпростішу обчислювальну машину з лінійної пам'яттю, яка згідно формальними правилами перетворює вхідні дані за допомогою послідовності елементарних дій. З математичної точки зору машина Тьюринга - просто певний алгоритм для переробки слів. Незважаючи на простоту машини Тьюринга, на ній можна обчислити все, що можна обчислити на будь-який інший машині, що здійснює обчислення за допомогою послідовності елементарних дій. Машина Тьюринга може виконувати всі можливі перетворення слів, реалізуючи тим самим всі можливі алгоритми.
Один з природних способів докази того, що алгоритми обчислення, які можна реалізувати на одній машині, можна реалізувати і на інший, - це імітація першої машини на другий. На машині Тьюринга можна імітувати машину Посту, нормальні алгоритми Маркова і будь-яку програму для звичайних комп'ютерів, перетворюючу вхідні дані у вихідні по якомусь алгоритмом. У свою чергу, на різних абстрактних виконавцях можна імітувати Машину Тьюринга. Виконавці, для яких це, можливо, називаються повними по Тьюрингу.
Багатство можливостей машини Тьюринга проявляється в тому, що якщо якісь алгоритми реалізуються машинами Тьюринга, то можна побудувати машини Тьюринга, реалізують різні композиції цих алгоритмів. Очевидно, що такі композиції також є алгоритмами, тому їх реалізація за допомогою машини Тьюринга підтверджує, що конструкція Тьюринга є універсальним виконавцем. На машинах Тьюринга виявилося можливим здійснити або імітувати всі алгоритмічні процеси, які коли-небудь описувалися математиками.
Список використаної літератури
1.Е...
