Алан Тюрінг

Алан Матісон Тюрінг
Народився	23 червня 1912 Лондон, Англія
Помер	7 червня 1954 Уілмслоу, Чешир, Англія
Місце проживання	Велика Британія
Громадянство	Велика Британія
Національність	Англія
Галузь наукових інтересів	математика, логіка, криптоаналіз, інформатика
Alma mater	Кембриджський університет, Прінстонський університет
Науковий керівник	Алонзо Черч
Відомі учні	Робін Ґанди (англ. Robin Gandy)
Відомий у зв'язку з:	Машина Тюрінга, Премія Тюрінга, Тест Тюрінга
Нагороди	Орден Британської імперії

Алан Матісон Тюрінг (англ. Alan Mathison Turing) (*23 червня 1912 — †7 червня 1954) — англійський математик, логік і криптограф. Тюрінг часто вважається батьком сучасної інформатики.

До війни навчався в британському університеті Кембридж та в американському університеті Прінстон.

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

Біографія

Син британського чиновника в Індії, Алан навчався у Франції, Англії і потім у США. Тоді багато математиків намагалися створити алгоритм для визначення істинності висловлювань. Геделю вдалося довести, що будь-яка корисна математична система аксіом неповна в сенсі, що в ній існує вислів, істинність якого не можна ні спростувати, ні підтвердити. Це спонукало Тьюрінга довести, що немає загального методу визначення істинності і, таким чином, математика завжди буде містити недовідні висловлювання. У своїй роботі Тюрінг запропонував проект простого пристрою, що має всі основні властивості сучасної інформаційної системи: програмне керування, пам'ять і покроковий спосіб дій. Ця уявна машина, що отримала назву «Машина Тюрінга», використовується в теорії автоматів або комп'ютерів.

Коли Тюрінг з США повернувся до Англії, почалася друга світова війна. Одним із найважливіших озброєнь цієї війни була ЕОМ «Колос» за проектом «Ультра», що почала в 1943 зламувати надскладні шифри німців. Робота цієї системи значно допомогла в боротьбі з Німеччиною та її союзниками.

Після війни

Після війни в 1945 Алан очолив проект створення комп'ютера «ТУЗ» (ACE, Automatic Computing Engine), а в 1948 Тьюрінг став працювати з «МАДАМ» (MADAM, Manchester Automatic DigitAl Machine), комп'ютером з найбільшою пам'яттю в світі в той час. Роботи Алана зі спорудження перших ЕОМ і розвитку методів програмування мали неоціненну важливість, давши основу більшості досліджень у галузі штучного інтелекту. Він вважав, що комп'ютери, врешті-решт, зможуть мислити як людина, і запропонував просту перевірку, відому як тест Тьюрінга, що оцінює здатність машини мислити: поговорити з ЕОМ, і нехай вона переконає вас, що вона — людина.

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

Звичайний громадянин після війни, Тюрінг якось був обкрадений своїм коханцем та ще одним зловмисником, і поскаржився до поліції. Але в той час гомосексуальність розглядалась британським правосуддям як злочин, і Алан Тюрінг був звинувачений в гомосексуалізмі в 1952 році. У 1952 р. обікрали квартиру Тьюрінга, і в ході розслідування поліція з'ясувала, що крадіжку скоїв один з його коханців. Скандал набув широкого розголосу, і 30 березня 1953 року відбувся судовий процес, на якому Тьюринг був звинувачений у гомосексуалізмі. На вибір йому було запропоновано два вироки — або ув'язнення у в'язниці, або придушення лібідо за допомогою ін'єкцій естрогену. Вчений обрав друге, по суті, це є хімічною кастрацією. Вибравши лікування, один із провідних криптографів Великої Британії перестав з'являтися на публіці, бо «лікування» привело до росту грудей та ожиріння. Атлет, який багато років їздив на велосипеді, Тюрінг став нездатний на найпростіші спортивні вправи.

Наслідки суду були катастрофічними — Алана Тьюрінга звільнили з шифроаналітичного бюро і Манчестерського університету. Пізніше йому повернули можливість викладати. Вчений до 1954 р. прожив на самоті, граючи в свою улюблену гру «Безлюдний острів», яка полягала в отриманні всіляких хімічних речовин з популярних продуктів. Через два роки помер у віці 41 року після того, як з'їв яблуко з ціанидом. За офіційною версією, смерть Тюрінга вважається самогубством.

8 червня 1954 Алан Метісон Тьюринг був знайдений мертвим у своєму будинку. Смерть наступила в результаті отруєння ціанідом. Яблуко, просочене ціанідом, лежало поруч на нічному столику. Точно не відомо, чи було це самогубством або Тьюрінга погубили заздрісники. Його мати вважала, що він отруївся випадково, так як завжди недбало працював з хімікатами.

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

Наукові досягнення та відкриття

Проблема зупинки

Було виявлено, що комп'ютери все-таки можуть вирішити не будь-яку математичну задачу. Алан Тьюринг довів у 1936 , що загальний алгоритм для вирішення проблеми зупинки для будь-яких можливих вхідних даних не може існувати.

Розшифровка коду «Енігми»

Дешифрувальна машина «Бомба»

Під час Другої світової війни Тьюринг працював в Блетчлі-парку — британському криптографічному центрі, де очолював одну з п'яти груп, Hut 8, що займалися в рамках проекту «Ультра» розшифровкою закодованих німецькою шифрувальної машиною «Енігма» повідомлень крігсмаріне і люфтваффе. Внесок Тьюринга в роботи з криптографічного аналізу алгоритму, реалізованого в «Енігма», ґрунтувався на більш ранньому криптоаналізі попередніх версій шифрувальної машини, виконаних у 1938 польським криптоаналітиком Маріаном Реєвським.

На початку 1940 він розробив дешифровальну машину «Бомба», яка дозволяла читати повідомлення люфтваффе. Принцип роботи «Бомби» полягав у переборі можливих варіантів ключа шифру і спроб розшифровки тексту, якщо була відома частина відкритого тексту або структура розшифровуваного повідомлення. Перебір ключів виконувався за рахунок обертання механічних барабанів, що супроводжувався звуком, схожим на цокання годинника, через що «Бомба» і отримала свою назву. Для кожного можливого значення ключа, заданого положеннями роторів (кількість ключів дорівнювало приблизно 10 19 для сухопутної «Енігми» і 10 22 для шифрувальних машин, що використовуються в підводних човнах), «Бомба» виконувала звірку з відомим відкритим текстом. Перша в Блетчлі «Бомба» Тьюрінга була запущена 18 березня 1940. Дизайн «Бомб» Тьюрінга так само був заснований на дизайні однойменної машини Рєєвського.

Блечлі Парк

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

Машина Тюринга

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

Теорія штучного інтелекту

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

Тест Тюрінга

Тест Тюринга — тест, запропонований Аланом Тюрінгом в 1950 у статті «Обчислювальні машини і розум» (англ. Computing Machinery and Intelligence) для перевірки, чи є комп'ютер розумним у людському сенсі слова. У цьому тесті один або кілька людей повинні задавати питання двом таємним співрозмовникам і на підставі відповідей визначати, хто з них машина, а хто людина. Якщо не вдавалося розкрити машину, що маскувалася під людину, передбачалося, що машина розумна.

Морфогенез

У 1952 Тьюринг опублікував роботу під назвою «Хімічні основи морфогенезу» (The chemical basis of morphogenesis), де вперше математично описується процес самоорганізації матерії.

Пам'ять про Алана Тьюрінга

• Одна з щорічних нагород Асоціації обчислювальної техніки називається Премія Тюрінга.
• Алан Тьюринг згадується в історичному романі «Кріптономікон» Ніла Стівенсона і фігурує в романі Роберта Харріса «Енігма».
• Відомий письменник-фантаст Гаррі Гаррісон у співавторстві з американським ученим в галузі штучного інтелекту Марвіном Мінскі написав роман «Вибір за Тьюрінгом» («The Turing Option», 1992).
• У романі Вільяма Гібсона «Нейромант» фігурує «поліція Тьюрінга» («регістр Тьюрінга»), яка займається контролем і стежить за розвитком існуючих штучних інтелектів.

Див. також

• Тест Тюринга
• Машина Тюринга
• Енігма — німецька шифрувальна машина
• Премія Тюрінга (від англ. Turing Award) за особливий вклад у розвиток комп'ютерних наук

Джерела

• Алан Тюрінг на сайті Університету Сан-Франциско, США (англ.)