Тьюринга.
1.8 Машини Тюрінга і сучасні електронно-обчислювальні машини
Вивчення машин Тьюринга і практика складання програм для них закладають фундамент алгоритмічного мислення, сутність якого полягає в тому, що потрібно вміти розділяти той чи інший процес обчислення або який-небудь іншої діяльності на прості складові кроки. У машині Тьюринга розчленування (аналіз) обчислювального ін?? цесса на найпростіші операції доведено до граничної можливості: розпізнавання одиничного розглянутого входження символу, переміщення точки спостереження даного ряду символів в сусідню точку і зміна наявної в пам'яті інформації. Звичайно, таке дрібне дроблення обчислювального процесу, реалізованого в машині Тьюринга, значно його подовжує. Але разом з тим логічна структура процесу, розчленованого, образно висловлюючись, до атомарного стану, значно спрощується і постає в деякому стандартному вигляді, вельми зручному для теоретичних досліджень. (Саме таке розчленовування на найпростіші складові обчислювального процесу на машині Тьюринга дає ще один непрямий аргумент на користь тези Тьюрінга, обсуждавшегося в попередньому параграфі: всяка функція, що обчислюється за допомогою якого-небудь алгоритму, може бути обчислена на машині Тьюринга, бо кожен крок даного алгоритму можна розчленувати на ще більш дрібні операції, які реалізуються в машині Тьюринга.) Таким чином, поняття машини Тьюринга є теоретичний інструмент аналізу алгоритмічного процесу, а значить, аналізу істоти алгоритмічного мислення.
У сучасних ЕОМ алгоритмічний процес розчленований не на такому дрібні складові, як в машинах Тьюринга. Навпаки, творці ЕОМ прагнуть до відомого укрупненню виконуваних машиною процедур (на цьому шляху, звичайно, є свої обмеження). Так, для виконання операції додавання на машині Тьюринга становить ціла програма, а в сучасній ЕОМ така операція є найпростішою. ??
Далі, машина Тьюринга володіє нескінченною зовнішньою пам'яттю (необмежена в обидві сторони стрічка, розбита на комірки). Але в жодній реально існуючої машині нескінченної пам'яті бути не може. Це говорить про те, що машини Тьюринга відображають потенційну можливість необмеженого збільшення обсягу пам'яті сучасних ЕОМ.
Нарешті, можна провести більш детальний порівняльний аналіз роботи сучасної ЕОМ і машини Тьюринга. У більшості ЕОМ прийнята трьохадресних система команд, обумовлена ??необхідністю виконання бінарних операцій, в яких бере участь вміст відразу трьох осередків пам'яті. Наприклад, число з комірки a множиться на число з комірки b, і результат відправляється в клітинку з. Існують ЕОМ двоадресного і одноадресні. Так, одноадресная ЕОМ працює таким чином: викликається (в суматор) число з комірки а; в суматорі відбувається, наприклад, множення цього числа на число з комірки b; результат відправляється з суматора в осередок с. Машину Тьюринга можна вважати одноадресної машиною, в якій система одноадресних команд спрощена ще більше: на кожному кроці роботи машини команда наказує заміну лише єдиної знака, що зберігається в оглядається осередку, а адреса оглядається осередку при переході до наступного такту може мінятися лише на одиницю (огляд сусідній праворуч або ліворуч осередку стрічки) або не мінятися зовсім. Це подовжує процес, але в той же час різко уніфікує його, робить стандартним.
Підводячи підсумки, можна сказати, що сучасні ЕОМ є якісь реальні фізичні моделі машин Тьюринга, огрублено з погляду теорії, але створені з метою реалізації конкретних обчислювальних процесів. У свою чергу, поняття машини Тьюринга і теорія машин є теоретичний фундамент і обґрунтування сучасних ЕОМ.
2. Реалізація алгоритмів в машині Тьюринга
Приклад 1. Реалізація в машині Тьюринга алгоритму переходу від n до n + 1 в десятковій системі числення.
Нехай дана десяткова запис натурального числа n і потрібно вказати десяткову запис числа n + 1, тобто обчислити функцію f (n)=n + 1.
Ясно, що тут зовнішній алфавіт машини повинен містити всі цифри 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 і символ порожньої клітки. Число n будемо записувати в десятковій системі на стрічці, причому цифри будуть поміщатися по одній в кожній клітині поспіль без пропусків.
Щоб вирішити поставлене завдання, машина повинна в першому такті роботи стерти останню цифру числа n, замінити її цифрою на одиницю більшою і перейти в стоп - стан, якщо остання цифра була менше цифри 9.
Якщо ж остання цифра числа n була 9, то машина повинна, стерши цифру 9, записати в звільнилася клітку цифру 0 і призвести зрушення вліво до сусіднього більш високим розрядом, залишаючись в тому ж початковому стані. Тут у другому такті роботи машина повинна додати одиницю до цифр...
