Алан Тюрінг

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

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

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

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

Рання біографія

Батько Алана Тюрінга — Юліус Метісон — завідував британським колоніальним відомством в Індії. Мати — Етель Сара Стоуні, була донькою головного інженера Мадраських залізниць.

Алан був другою дитиною в родині. Він народився 23 червня 1912 року в лондонській лікарні «Воррінгтон-Лодж». Дуже рідко бачив своїх батьків, які працювали в Індії. Як син аристократів навчався у Шернборнській публічній школі (en:Sherborne School), де був одним із найгірших учнів у класі з гуманітарних предметів.

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

Тоді багато математиків намагалися створити алгоритм для визначення істинності висловлювань. Геделю вдалося довести, що будь-яка корисна математична система аксіом неповна в сенсі, що в ній існує вислів, істинність якого не можна ні спростувати, ні підтвердити. Це спонукало Тюрінга довести, що немає загального методу визначення істинності і, таким чином, математика завжди буде містити недовідні висловлювання.

У 1928 році німецький математик Давид Гільберт привернув увагу світової громадськості до проблеми дозволу (Entscheidungsproblem). У своїй роботі «On Computable Numbers, with an Application to the Entscheidungsproblem» (опубліковано 12 листопада 1936 року) Тюринг переформулював теорему Геделя про неповноту, замінивши універсальну формальну арифметичну мову Геделя на прості гіпотетичні пристрої. У своїй роботі він запропонував проект простого пристрою, що має всі основні властивості сучасної інформаційної системи: програмне керування, пам'ять і покроковий спосіб дій. Ця уявна машина, що отримала назву «Машина Тюрінга», використовується в теорії автоматів або комп'ютерів. Він довів, що подібна машина була б здатна провести будь-які математичні обчислення, представленого у вигляді алгоритму, далі Тюринг показав, що не існує рішення Entscheidungsproblem, спершу довівши, що Проблема зупинки для машини Тюринга нерозв'язна: в загальному випадку неможливо алгоритмічно визначити, чи зупиниться коли-небудь дана машина Тюринга.

Хоча доказ Тюринга було оприлюднено незабаром після еквівалентного доказу Алонзо Черча, в якому використовувалися Лямбда-числення, сам Тюринг був з ним не знайомий. Підхід Алана Тюринга прийнято вважати більш доступним і інтуїтивним. Ідея «Універсальної Машини», здатної виконувати функції будь-якої іншої машини, або іншими словами, обчислити все, що можна в принципі обчислити, була вкрай оригінальною. Фон Нейман визнав, що концепція сучасного комп'ютера заснована на цій роботі Алана Тюринга. Машини Тюрінга, як і раніше є основним об'єктом дослідження теорії алгоритмів.

З вересня 1936 року по липень 1938 Тюринг працював під керівництвом Черча в Прінстоні. Крім занять математикою, вчений вивчав криптографію, а також конструював електро-механічний бінарний помножувач. У червні 1938 року Тюринг захистив докторську дисертацію «Логічні системи засновані на Ордіналах», в якій була представлена ​​ідея відомості по Тюрингу, що полягає в об'єднанні машини Тюрінга з оракулом. Це дозволяє досліджувати проблеми, які неможливо вирішити за допомогою лише машини Тьюринга.

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

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

Після війни

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

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

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

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

Смерть

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

Ходжес і Девід Левіт припускають, що Тюринг відтворив сцену з мультфільму Волта Діснея Білосніжка 1937 року — улюбленої казки вченого. За словами Левіта:

«

йому особливо подобалася сцена, в якій Зла Королева занурює яблуко в отруйне зілля.

»

Прихильником цієї ж версії є один друг Тюринга — Алан Гарнер, який у 2011 році написав про це у своїй статті для The Guardian.

Доктор Джек Копеланд після досконалого вивчення результатів розтину дійшов до іншого висновку: отруєння було викликано вдиханням випарів ціаніду, котрі виділялися апаратом для гальванопластики ложок золотом, в якому використовувався діоксид ціаніду для розщеплення золота. Також Тюринг зазвичай з'їдав яблуко перед сном і немає нічого незвичайного в тому, що він його не доїв. До того ж Тюринг ставився до гормональної терапії (яка закінчилася за рік до події) з «часткою гумору» і не виявляв ознак зневіри, навпаки, він склав список завдань, якими планував зайнятися після вихідних. Мати вченого вважала, що смерть її сина була випадковістю, викликаною неакуратним зберіганням хімікатів, однак, Ходжес, вважає, що Тюринг міг підлаштувати експеримент таким чином, щоб не засмучувати її.

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

«

З Аланом і з багатьма тисячами інших чоловіків-геїв, засуджених за гомофобним законами, обійшлися жахливо. А багато мільйонів тих, хто не були засуджені, роками жили в постійному страху бути засудженими за те, що вони такі, які вони є. Я пишаюся тим, що ті часи минули, і що за останні 12 років наш уряд зробив багато чого, щоб зробити життя справедливішим і рівним для нашої спільноти ЛГБТ. Визнання Алана однією з найвідоміших жертв гомофобії у Великобританії є ще одним кроком до забезпечення рівності. <...> Від імені британського уряду і всіх тих, хто живе на волі завдяки внеску Алана, я з усією щирістю кажу: прости нас, ти заслуговуєш набагато кращого.

»

У Тюрінга не залишилося живих родичів, тому вибачення мало символічний характер. У повідомленні Браун називає математика однією з найвідоміших жертв гомофобії у Великій Британії.

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

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

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

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

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

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

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

Блетчлі Парк

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

Turingery

У липні 1942 року Тюрінг розробив техніку, названу «Turingery» (або жартівливо «Тюрінгізмус») і покликану спростити розшифровку повідомлень машини Лоренца. У Блетчлі-парку було розроблено роторний шифрувальний пристрій для телетайпа, який називався «Tunny», Turingery, по суті це був метод підбору параметрів роторів «Tunny». Тюрінг також познайомив команду, яка працювала над «Tunny» з Томмі Фловерсом, який під керівництвом Макса Ньюмана пізніше створив «Колос» — перший у світі програмований електронний комп'ютер, чия швидкість роботи дозволила ефективно застосувати статистичні методи до дешифрування повідомлень. Деякі помилково вважають, що основні заслуги з розробки «Колоса» належать Тюрінгу. Turingery і Banburismus без сумніву зіграли свою роль у зломі машини Лоренца, але сам Тюрінг ніколи прямо не брав участь у розробці.

Шифратор мови (Delilah)

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

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

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

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

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

Тест Тюрінга

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

Морфогенез

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

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

Вікно google.com 23 червня 2012 року

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

Див. також

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

Література

• Алан Тюрінг(англ.) в проекті «Математична генеалогія».
• The Mind and the Computing Machine: Alan Turing and others // The Rutherford Journal. —.
• Hodges, Andrew (27 August 2007). «Alan Turing». У Edward N. Zalta. Stanford Encyclopedia of Philosophy (вид. Winter 2009) (Stanford University). Процитовано 10 January 2011. 
• Gray Paul Computer Scientist: Alan Turing // TIME. — (29 March 1999).
• Gleick, James, The Information: A History, a Theory, a Flood|The Information: A History, A Theory, A Flood, New York: Pantheon, 2011, ISBN 978-0-375-42372-7
• Leavitt, David, The Man Who Knew Too Much: Alan Turing and the Invention of the Computer, W. W. Norton, 2006

Посилання

• ВікіСховище має мультимедійні дані за темою: Алан Тюрінг
• Алан Тюрінг на сайті Університету Сан-Франциско, США (англ.)