Алана Тюринга

Алан Матісон Тюрінг (англ. Alan Mathison Turing) (*23 червня 1912 — †7 червня 1954) — англійський математик, логік і криптограф. Тюрінг часто вважається батьком сучасної інформатики. До війни навчався в британському університеті Кембридж та в американському університеті Прінстон. Під час війни працював над зламуванням шифрів німецького командування разом з американськими вченими та військовими в англійському секретному інституті Блетчлі Парк. Згідно з історичною літературою, що лише зараз виходить після багаторічного засекречення подробиць, ця робота, хоча й не завжди успішна, допомогла виграти деякі військові кампанії та зберегти тисячі людей.

Машина Тюринга Будь-яка інтуїтивно обчислювана функція є частково рекурсивною, або, еквівалентно, може бути обчислена за допомогою деякої машини Тюринга. Алан Тюринг висловив припущення (відоме як теза Черча — Тюринга), що будь-який алгоритм в інтуїтивному розумінні цього слова може бути представлений еквівалентною машиною Тюрінга. Уточнення уявлення про обчислюваність на основі поняття машини Тюринга (і інших аналогічних йому понять) відкрило можливості для суворого доказу алгоритмічної нерозв'язності різних масових проблем (тобто проблем про знаходження єдиного методу рішення деякого класу задач, умови яких можуть змінюватись у відомих межах). Найпростішим прикладом алгоритмічно нерозв'язної масової проблеми є так звана проблема застосовності алгоритму (називається також проблемою зупинки). Вона полягає в наступному: потрібно знайти загальний метод, який дозволяв би для довільної машини Тюринга (заданої за допомогою своєї програми) і довільного початкового стану стрічки цієї машини визначити, чи завершиться робота машини за кінцеве число кроків, або ж буде тривати необмежено довго.

Тюринг є засновником теорії штучного інтелекту. Машина Тюринга є розширенням моделі скінченого автомату і здатна імітувати (при наявності відповідної програми) будь-яку машину, дія якої полягає в переході від одного дискретного стану до іншого.