Реферат
Машина Тьюринга. Парадигма програмування
Машина Тьюринга
Алан Матісона Тьюринг (23 червня 1912 - 7 червня 1954) - англійський математик, логік, криптограф, що зробив істотний вплив на розвиток інформатики. Кавалер Ордена Британської імперії (1945). Запропонована ним в 1936 році абстрактна обчислювальна В«Машина ТьюрінгаВ» дозволила формалізувати поняття алгоритму і до цих пір використовується в безлічі теоретичних і практичних досліджень. p align="justify"> У своїй роботі Тьюринг запропонував проект простого пристрою, що має всі основні властивості сучасної інформаційної системи: програмне управління, пам'ять, і покроковий спосіб дій. Ця уявна машина, що отримала назву В«машини ТьюрінгаВ», використовується в теорії автоматів або комп'ютерів. Коли Тьюринг із США повернувся до Англії, почалася друга світова війна. Одним з найважливіших озброєнь цієї війни була ЕОМ В«КолосВ» за проектом В«УльтраВ», що почала в 1943 році зламувати надскладні шифри німців. Робота цієї системи значно допомогла у боротьбі з Німеччиною та її союзниками. p align="justify"> Після війни в 1945 році Алан очолив проект створення комп'ютера В«ТУЗВ» (ACE, Automatic Computing Engine), а в 1948 Тьюринг став працювати з В«ПАНІВ» (MADAM, Manchester Automatic DigitAl Machine), комп'ютером з найбільшою пам'яттю в світі в той час.
червня 1954 Алан Метісон Тьюринг був знайдений мертвим у своєму будинку. Смерть наступила в результаті отруєння ціанідом. Яблуко, просочене ціанідом, лежало поруч на нічному столику. Точно не відомо, чи було це самогубством або Тьюринга погубили заздрісники. p align="justify"> Машина Тьюринга (МТ) - абстрактний виконавець (абстрактна обчислювальна машина) До складу машини Тьюрінга входить нескінченна в обидві сторони стрічка (можливі машини Тьюринга, які мають кілька нескінченних стрічок), розділена на осередки, і управляючий пристрій , здатне перебувати в одному з безлічі станів. Число можливих станів керуючого пристрою звичайно і точно задано. p align="justify"> Керуючий пристрій може переміщатися вліво і вправо по стрічці, читати і записувати в осередки стрічки символи деякого кінцевого алфавіту. Виділяється особливий порожній символ, що заповнює всі клітини стрічки, крім тих з них (кінцевого числа), на яких записані вхідні дані. p align="justify"> Керуючий пристрій працює згідно з правилами переходу, які представляють алгоритм, реалізований даною машиною Тьюринга. Кожне правило переходу наказує машині, залежно від поточного стану і спостережуваного в поточній клітині символу, записати в цю клітку новий символ, перейти в новий стан і переміститися на одну клітину вліво або вправо. Деякі стану машини Тьюринга можуть бути помічені як термінальні, і перехід в будь-яке з них означає кінець роботи, зупинку алгоритму...
