Машина Тьюринга: біля витоків інформатики та криптографії

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

Машина Тьюринга не тільки стала чіткою відповіддю на конкретну обчислювальну задачу, а й стала теоретичною основою алгоритмів і науковою базою програмування. Крім того, сам принцип вирішення складних математичних задач методом конструювання різних абстрактних механізмів і побудови алгоритмів, що виконуються електронними пристроями, ліг в основу зародження нової сфери інтелектуальної діяльності - інформаційних технологій.

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

Машина Тьюринга влаштована надзвичайно просто, проте вона дозволяє виконувати практично будь-які програми, побудовані на чітких алгоритмах. Для виконання різних обчислювальних операцій існує спеціальна таблиця, в якій записані певні правила, що представляють собою набір універсальних інструкцій для машини. Керуючись цією таблицею, в якій зафіксований порядок дій для тієї чи іншої комбінації різних станів і символів, пристрій визначає, яку обчислювальну операцію слід здійснити в кожній конкретній ситуації. По суті, універсальна машина Тьюринга є першим прототипом сучасних комп`ютерів.

Геніальний винахід Алана Тьюринга успішно застосовувалося британським криптоаналітичних бюро під час Другої світової для злому німецьких секретних кодів. Часто розшифровка секретних повідомлень підводних стерв`ятників Деніца лягала на стіл Черчілля раніше, ніж потрапляла в рейхсканцелярию. На відміну від німецьких криптографов, які практикували суто інтуїтивний підхід і ставилися до криптографії, як до мистецтва, методика Алана Тьюринга передбачала алгоритмічні способи вирішення найскладніших завдань з розшифровки секретних кодів, що виявилося незрівнянно ефективніше.

Недетермінована машина Тюрінга дала можливість зламувати шифри противника не лише геніальним криптографії, але й звичайним співробітникам бюро, перетворивши інтуїтивні дії в планомірне цілеспрямований рух до мети. Отримані за допомогою машини Тьюринга дані в чималому ступені вплинули на результат битви за Англію.