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