ТЮРИНГ, АЛЪН МАТИСЪН(Тюринг, Алън Матисън) (1912–1954), английски математик. Роден в Лондон на 23 юни 1912 г. Учи в Шерборнското училище, където показва изключителни способности по математика и химия, след това в Кралския колеж, Кеймбриджкия университет, където завършва през 1934 г. Негов пряк учител и по-късно колега е математикът (тополог ) М. Х. А. Нюман (1897–1984); Тюринг взема своя курс върху основите на математиката през 1935 г. Същата година Тюринг получава докторска стипендия от King's College. През 1936–1938 г. – в Принстънския университет в САЩ, където негов научен ръководител е американският логик А. Чърч (1903–1995). След като получава докторска степен, Тюринг отхвърля предложението на Й. фон Нойман да остане в Съединените щати и се завръща в Кеймбридж, където получава стипендия в Кралския колеж за изучаване на логика и теория на числата, като същевременно посещава семинарите на Л. Витгенщайн по философия на математиката . По същото време започва поверителното му сътрудничество с Правителственото училище за кодове и шифри в Блечли Парк, където той участва в работата по разбиването на немски шифри преди войната.
След избухването на Втората световна война Тюринг се премества на пълен работен ден, за да работи в Блечли Парк. Използвайки по-ранни полски разработки, заедно с W. Welchman, той разбива кодовете на германските военновъздушни сили, създавайки машината за дешифриране на бомби, а до края на 1939 г. той независимо разбива много по-сложен код, използван в машините за криптиране Enigma, които са оборудвани с немски подводници (виж . КРИПТОГРАФИЯ). След първия успех конфронтацията с Енигма продължи още няколко години, но от пролетта на 1943 г. целият обмен на информация на германския флот беше лесно дешифриран от съюзниците, които по това време вече използваха електронни технологии. Тюринг участва и в разработването на шифри за кореспонденцията между Чърчил и Рузвелт, прекарвайки периода от ноември 1942 г. до март 1943 г. в САЩ. Удостоен е с титлата Кавалер Командор на Ордена на Британската империя 4-ти клас.
Павел Паршин
Съвременните математици, програмисти и компютърни инженери са запознати с името Алън Тюринг от студентските си дни: всички те трябваше да изучават „машината на Тюринг“ - „основата на основите“ на теорията на алгоритмите. Нито един сериозен учебник по математическа логика и теория на изчислимостта не може да мине без „машина на Тюринг“.
Зад почти всяко изключително научно откритие стои невероятна история. Зад „машината на Тюринг“ стои историята на един научен гений – гений, получил достойно признание само много години след трагичната си смърт.
Ролята на А. Тюринг в историята на компютърните науки по никакъв начин не се ограничава до изобретяването на „машината на Тюринг“, както понякога може да изглежда поради относително малкото публикувана (на руски) информация за него.
Алън Тюринг може да бъде причислен към плеядата от най-великите математически и философски умове, които съставляват гордостта на човечеството, като R. Descartes, G.W. Лайбниц, Б. Ръсел, Д. Гилбърт, А. Витгенщайн. Учудващо е колко жестока шега изигра на Тюринг неговото пълно безразличие към борбата за приоритет в научните открития: доскоро мястото му в историята на развитието на научните и инженерни идеи беше представено много непълно, ако не и едностранчиво (и не на последно място благодарение на някои американски историци на науката, които внимателно се погрижиха за абсолютизирането на своя национален приоритет в създаването на компютри, а може би и в създаването на цялата компютърна наука).
Между другото, Алън Тюринг за първи път пусна в обращение термина „компютър“ в съвременния смисъл. Преди това това беше името, дадено на онези, които участваха в изчисления, например банкови служители, които работеха на сумираща машина.
Табела, монтирана на стената на хотел в Лондон гласи:
„Алън Тюринг (1912 – 1954), разбивач на кодове и пионер в компютърните науки, е роден тук.“ Всъщност сега (но в никакъв случай по време на живота си!) Тюринг е признат за един от основателите на компютърните науки и теорията за изкуствения интелект; смятан е за първия теоретик на съвременното програмиране и накрая за първия хакер в света. (Между другото, неговите „хакерски дейности“ допринесоха значително за победата на съюзническите сили над германския флот по време на Втората световна война и един от колегите на Тюринг веднъж каза: „Не смея да кажа, че спечелихме войната благодарение на Тюринг. Но без него бихме могли. Иска ми се да я загубя.")
Бъдещите родители на Алън Тюринг, Джулиъс Матесън Тюринг и Етел Сара Стоуни, се запознаха и се ожениха в Индия. Тюринг е служил в английската колониална служба, а Етел Сара е дъщеря на главния инженер на железниците в Мадрас. Това беше уважавано английско аристократично семейство, принадлежащо към така наречената „горна средна класа“ и живеещо в съответствие със строгите традиции на империята.
Най-доброто от деня
Година след раждането майката на Тюринг се завръща в Индия, оставяйки Алън на грижите на приятел на семейството, пенсиониран полковник. По-късно момчето е изпратено в частно училище-интернат.
Малкият Алън имаше много любознателен ум. След като се научи да чете самостоятелно на шестгодишна възраст, той поиска от учителите си разрешение да чете научно-популярни книги. На 11-годишна възраст той извършва доста компетентни химически експерименти, опитвайки се да извлече йод от водорасли. Всичко това предизвика силно безпокойство у майка му, която се страхуваше, че хобитата на сина й, които противоречат на традиционното възпитание, ще му попречат да се запише в Public School (английско затворено частно учебно заведение за момчета, обучението в което е задължително за децата на аристократи). Но страховете й бяха напразни: Алън успя да влезе в престижното държавно училище Sherborne. Скоро обаче тя трябваше да се страхува дали талантливият й син ще успее да завърши това училище...
Списанието на класа красноречиво свидетелства за училищните успехи на Алън -
младият Алън Тюринг не правеше нищо в клас, а в свободното си време изучаваше „извънкласни“ науки. Като петнадесетгодишен тийнейджър той самостоятелно изучава теорията на относителността: бележките му в дневника биха направили чест на младши ученик в наше време.
Средата и стилът на обучение в класическото британско училище, обучаващо уважавани и надеждни поданици на империята, не са благоприятни за по-нататъшното разрастване на подобни интереси, които освен това Тюринг няма с кого да сподели с него. Преподаваните предмети го оставят напълно безразличен, едва успява и накрая се изправя пред реалната перспектива да му откажат свидетелство за училище, което за пореден път ужасява майка му.
Младежката жажда за знания бързо сближава Тюринг и Морком и те стават неразделни приятели. Сега те вече се прозяваха заедно на уроци по френски или играеха тик-так, докато едновременно обсъждаха астрономия и математика. След като напуснаха училище, и двамата планираха да влязат в университета в Кеймбридж и Алън, след като се отърва от много години самота, може би беше почти щастлив...
Първият опит на Алън да премине предварителните изпити в Кеймбридж, където отидоха заедно, беше неуспешен. Но той не беше много разстроен, защото искрено се радваше за Кристофър, който успешно премина тестовете и получи стипендия. Алън се надяваше да влезе от втория си опит, за да може да учи с приятеля си. На 13 февруари 1930 г. неговият Крис внезапно почина. Внезапната смърт на най-добрия му приятел шокира седемнадесетгодишния Тюринг, потапяйки го в дълбока и продължителна депресия. Въпреки това, той, преди най-лошият ученик в класа си, намери сили да влезе в Кеймбридж. Той беше подкрепен от твърдото убеждение за дълга си да постигне в науката това, което Кристофър вече не можеше да направи... Тюринг нямаше да се възстанови скоро от шока: още като студент в Кеймбридж, в продължение на няколко години той пише писма до майката на Морком, пропити с душевна болка. В тези писма той непрекъснато се връща към размисъл за това как човешкият ум - и по-специално умът на Кристофър - се намира вътре в материалната обвивка и как се освобождава от нея в момента на физическата смърт на тялото.
През 1932 г., по време на едно от посещенията си при семейство Морком, той съставя документ в дома им, наречен "Природата на духа" - манифест на вярата му в съществуването на човешкия дух след смъртта. Основната точка на тази работа е, че детерминизмът на традиционната физическа картина на света и очевидното й противоречие с идеята за свободната воля са опровергани от новата наука - квантовата физика.
Въпросът за структурата на човешкия ум ще го тревожи през целия му живот.
През 1939 г. британското военно министерство възлага на Тюринг да разкрие тайната на Енигма, специално устройство, използвано за криптиране на радио съобщения в германския флот и Луфтвафе. Британското разузнаване се сдоби с това устройство, но не беше възможно да дешифрира прихванатите германски радиограми.
Тюринг получи свобода на действие. Той покани няколко приятели, които играят шах, в своя отдел на Британското училище за кодове и шифри. За него например работеше Хари Голомбек, който по-късно стана известен съдия на ФИДЕ и ръководи финалния мач за световната титла между Фишер и Спаски.
27-годишният Тюринг и колегите му бяха обзети от истинска спортна страст. Германците смятаха Енигма за непревземаема. Трудността при дешифрирането се утежнява от факта, че кодираната дума съдържа повече букви от оригинала. Въпреки това, в рамките на шест месеца Тюринг разработи устройство, което той нарече „Бомбата“, което направи възможно четенето на почти всички съобщения от Luftwaffe. И година по-късно по-сложна версия на Enigma, използвана от нацистките подводничари, беше „хакната“. Това до голяма степен предопределя успеха на британския флот.
Заслугите на Алън Тюринг бяха оценени подобаващо: след поражението на Германия той получи орден и беше включен в научната група, участваща в създаването на британски електронен компютър. През 1951 г. в Манчестър започва работа един от първите компютри в света. Тюринг разработи софтуер за него. Тогава написва първата шахматна програма за компютър. Това беше само алгоритъм, тъй като компютър, способен да приложи тази програма, все още не съществуваше.
Шахът не беше единственото хоби на този човек. Занимавал се е с бягане и крос. През 1947 г. той заема почетно пето място на All England Marathon. В допълнение към работата си в университета, Тюринг продължи да си сътрудничи с кодовия отдел. Едва сега фокусът на вниманието му вече беше върху кодовете на съветската станция в Англия. През 1951 г. е избран за сътрудник на Кралското научно дружество.
Всичко рухна буквално за един ден. През 1952 г. апартаментът на Тюринг е ограбен. По време на разследването се оказа, че това е направено от един от приятелите на сексуалния му партньор. Ученият като цяло никога не е крил своята „нетрадиционна сексуална ориентация“, но също така не се е държал предизвикателно. Скандалът с кражбата обаче получи широка публичност и в резултат на това срещу самия Тюринг бяха повдигнати обвинения в „непристойно поведение“. На 31 март 1953 г. се провежда процесът. Присъдата предполагаше избор: или лишаване от свобода, или инжекции на женския хормон естроген (метод на химическа кастрация). Той избра второто.
Той беше уволнен от отдела за кодове. Отказано разрешение за сигурност. Вярно, екипът от преподаватели в университета в Манчестър арестува Тюринг, но той почти никога не се появяваше в университета. На 8 юни 1954 г. Алън Матисън Тюринг е намерен мъртъв в дома си. Той се самоуби, като се отрови с цианид калий.
Тюринг инжектира цианидния разтвор в ябълката. След като го ухапа, той умря. Казват, че именно този плод, намерен след това на нощната масичка на Алън, се превърна в емблема на известната компютърна компания Apple. Ябълката обаче е и библейски символ на знанието и греха.
В раздела „Иконите на епохата“ говорим за художници, дизайнери, режисьори, музиканти и други творчески професионалисти, които успяха да създадат разпознаваем стил и да повлияят на съвременната култура. Нашият герой тази седмица е пионерът в компютърните науки, математикът и криптографът Алън Тюринг, който беше посмъртно помилван на 24 декември от кралицата на Великобритания.
Алън Матисън
Тюринг
(Алън Матисън Тюринг)
1912-1954, Великобритания
математик, логик, криптограф
Ранни години и академичен успех
Историята на съвременните компютри може да бъде разказана по различни начини: в Уикипедия, например, тя започва с изобретяването на броенето в древен Вавилон преди около 6000 години. Но най-значимият скок, довел до появата на компютрите, се случи през първата половина на 20 век, когато бяха изобретени първите компютри. Една от тях беше „машината на Тюринг“, хипотетично устройство, изобретено през 1936 г. от Алън Тюринг, учен, смятан за един от основателите на компютърните науки.
Изобретателят на компютъра беше само на 24 години - бъдещият математик и учен показа нетипични способности от детството си и бързо достигна висоти в математиката. Постъпва на училище на 6 години и още тогава учителите му забелязват, че е талантливо дете. На 13-годишна възраст Тюринг започва да учи в известното независимо училище за момчета Sherborne School в Дорсет, което съществува от 16 век: там той постига голям успех по математика, но учителите му не одобряват това, защото смятат хуманитарните науки по-важно.
През 1928 г. Тюринг се запознава с Кристофър Морк, талантливо момче, което също се интересува от математика и нови технологии. Две години по-късно Морком умира от говежда туберкулоза. Тюринг имаше предчувствие за смъртта на близък приятел и беше изумен, че науката не може да обясни подобни усещания. Смъртта на Морком силно повлия на учения, неговите философски възгледи и идеи за смъртта. През целия си живот той се опитва да намери рационално обяснение за подобни събития и мислите му по тази тема са в основата на статията „За изчислимите числа, приложени към проблема с разделителната способност“.
"Машина на Тюринг" и декриптиране на съобщения "Енигма".
През 1931 г. бъдещият учен постъпва в Кеймбридж, където негов учител е известният математик Годфри Харолд Харди, който изучава теорията на числата и теорията на функциите. След като завършва колеж през 1934 г., Тюринг започва да посещава лекции на учения Макс Нюман, където научава за проблема на Гилбърт с „разрешимостта“. Размишлявайки върху този проблем, Тюринг излезе с устройство, което може да изпълнява функциите на всяка друга машина, тоест да изчислява всичко, което може да се изчисли. Тази концепция беше наречена "машина на Тюринг". Освен това в статията си Тюринг доказа, че проблемът със спирането на такава машина е неразрешим, опровергавайки теорията на Гилбърт. Това е доказано и от математика и логиката Алонзо Чърч, с когото Тюринг работи през 1936-1938 г. в Принстънския университет.
"Бомба"
В края на 30-те години Тюринг започва работа в Блечли Парк, имение в Милтън Кейнс (град близо до Лондон), където по това време се помещава основното звено за криптиране на Обединеното кралство, сега наречено Център за правителствени комуникации (GCHQ). Там Тюринг, заедно с други учени, се опитва да дешифрира Енигма, преносима машина за криптиране на съобщения, използвана от германската армия. Въз основа на криптографския анализ на Тюринг на алгоритъма Enigma, машината за дешифриране на Bomb е създадена през 1940 г. Тя дешифрира много германски съобщения: благодарение на нея британците научиха за плановете за нахлуване в СССР и за дейността на германските подводници по време на операция „Битката за Атлантическия океан“.
Блечли Парк
Последните години и посмъртно признание
Хомосексуализмът се счита за престъпление във Великобритания от края на 16 век: първоначално според Закона за содомията хомосексуалистите са били екзекутирани, но през 19 век това наказание е заменено със затвор. През 1885 г. е приета „Поправката на Лабушер“, по която е осъден Оскар Уайлд – тя е в сила до 1967 г. и в съответствие с нея е съден Тюринг. Никога не е крил ориентацията си - всичките му приятели и колеги знаеха за това, включително и тези, които работиха с него по време на войната.
През 1952 г. обаче Тюринг е осъден за връзка с 19-годишния Арнолд Мъри. Млад мъж ограбил къщата на учен, Тюринг съобщил на полицията и трябвало да разкаже на полицията за връзката си с Мъри. Ученият беше осъден: той трябваше да избира между лишаване от свобода и химическа кастрация. Той избра второто. Освен това му е забранено да работи в GCHQ и това се превръща в трагедия за Тюринг - той се самоубива през 1954 г.
През следващите десетилетия, когато поправката на Лабушер беше отменена, Тюринг беше признат за един от 100-те най-велики британци в историята, а на 24 декември 2013 г. беше посмъртно помилван от кралицата на Великобритания. Освен това Тюринг се превърна в икона на британската куиър общност и идол на много математици - 100 години след рождението му, през 2012 г. във Великобритания и други страни беше отбелязана „Годината на Алън Тюринг“, в рамките на която се провеждаха научни конференции, изложби и други събития бяха организирани.
Хронология
Среща Кристофър Морк
Постъпва в Кралския колеж, Кеймбридж
Изобретява „машината на Тюринг“, пише статия
„Върху изчислимите числа, приложени към проблема с разрешаването“ и започва работа в Принстънския университет
Започва работа в GCHQ
Изпратен в САЩ да построи "Бомбата" във Вашингтон
Награден с Ордена на Британската империя за военна служба; те не могат да го получат.
Формирането на информатиката като наука
Тюринг се счита за един от основателите на компютърните науки. В своите статии той формализира понятието „алгоритъм“, което е важно за тази наука. Освен това ученият всъщност изобретил прототипното устройство за IBM и всички съвременни компютри - „машината на Тюринг“. Преди него е имало само механична изчислителна машина от Чарлз Бабидж, който я е построил в началото на 19 век.
През първата половина на 20 век, когато са изобретени първите компютри. Но заедно с физически осезаемите машини се появиха и концептуални машини. Една от тях беше „машината на Тюринг“ - абстрактно изчислително устройство, изобретено през 1936 г. от Алън Тюринг, учен, смятан за един от основателите на компютърните науки.
Неговите хоризонти се простираха от квантовата теория и принципа на относителността до психологията и неврологията. И като начин за познаване и предаване на знанията си, Тюринг използва апарата на математиката и логиката. Той намери решения на привидно неразрешими проблеми, но беше най-страстен по идеята за „Универсална машина“, способна да изчисли всичко, което по принцип е изчислимо.
Детство, образование, хобита
Родителите на Алън живееха в индийския град Чатрапур. Баща - Джулиус Матесън Тюринг, представител на старо шотландско аристократично семейство, работил в императорската държавна служба. Майка - Сара Етел (по баща Стони), беше от Ирландия, от протестантско семейство на англо-ирландското благородство. Когато тя очакваше дете, двойката реши да се премести в Англия, за да може то да расте и да бъде отгледано в Лондон.Алън Тюринг е роден там на 23 юни 1912 г. Имаше по-голям брат Джон. Правителствената служба на Юлиус Тюринг продължи и родителите на Алън трябваше да пътуват често между Хейстингс и Индия, оставяйки двамата си сина на грижите на пенсионирана двойка от армията. Тюринг показа признаци на гениалност от ранно детство.
Като деца Алън и по-големият му брат Джон рядко виждат родителите си - баща им служи в Индия до 1926 г.; децата остават в Англия и живеят под грижите на частни домове, получавайки строго английско възпитание, съответстващо на позицията им в социалната стълбица. Като част от такова образование всъщност не е предвидено изучаването на основите на естествените науки.
Малкият Алън имаше много любознателен ум. След като се научи да чете на 6-годишна възраст, той поиска от учителите си разрешение да чете научно-популярни книги.
На 11-годишна възраст той извършва доста компетентни химически експерименти, опитвайки се да извлече йод от водорасли. Всичко това предизвика силно безпокойство у майка му, която се страхуваше, че хобитата на сина й, които противоречат на традиционното възпитание, ще му попречат да се запише в Public School (английско затворено частно учебно заведение за момчета, обучението в което е задължително за децата на аристократи). Но страховете й бяха напразни: Алън успя да влезе в престижното държавно училище Sherborne.
На шестгодишна възраст Алън Тюринг отиде в училището "Св. Майкъл" в Хейстингс, където директорът веднага отбеляза таланта му. През 1926 г., на 13-годишна възраст, Тюринг посещава прочутото частно училище Шерборн в Шерборн, Дорсет. Първият му ден в училище съвпада с общата стачка през 1926 г. Затова Тюринг трябваше да измине разстоянието от около 100 км от Саутхемптън до Шерборн с велосипед, като по пътя пренощува в хотел.
Страстта на Тюринг към математиката не намира голяма подкрепа сред учителите в Шерборнското училище, където обръщат повече внимание на хуманитарните науки. Директорът на училището пише на родителите: „Надявам се, че няма да се опитва да седи на два стола едновременно. Ако възнамерява да остане в частно училище, тогава той трябва да се стреми да получи "образование". Ако той ще бъде изключително „научен специалист“, тогава частното училище за него е загуба на време.
Училищният успех на Алън е красноречиво доказателство от класното списание, в което можете да намерите например следното
Мога да си затварям очите за писанията му, въпреки че никога не съм виждал нещо по-ужасно в живота си, опитвам се да толерирам непоклатимата му небрежност и неприлично старание; но все още не мога да понеса зашеметяващата глупост на неговите изказвания по време на една напълно здравословна дискусия върху Новия завет.
Въпреки това, в областите, които го интересуват, Тюринг показва изключителни способности.
През 1928 г., на 16-годишна възраст, Тюринг се запознава с работата на Айнщайн, която разбира до такава степен, че успява да се досети от текста за съмненията на Айнщайн относно осъществимостта на законите на Нютон, които не са изрично заявени в статията .
университет
Поради неприязънта си към хуманитарните науки, Тюринг не получи добър резултат на изпита и затова след училище влезе в King's College Cambridge, въпреки че възнамеряваше да отиде в Trinity College. Тюринг учи в Кралския колеж от 1931 до 1934 г. под ръководството на известния математик Годфри Харолд Харди.Университетът в Кеймбридж, който имаше специални привилегии, предоставени от английските монарси, отдавна е известен със своите либерални традиции и духът на свободомислието винаги е царувал в стените му. Тук Тюринг намира - може би за първи път - своя истински дом, където може да се посвети изцяло на науката.
Основно място в живота му заема ентусиазираното изучаване на науките, които толкова го интересуват - математика и квантова физика. Тези години са период на бързо развитие на квантовата физика и Тюринг се запознава с най-новите разработки в тази област през студентските си години. Той е силно впечатлен от книгата на Джон фон Нойман „Математически основи на квантовата механика“, в която намира отговори на много въпроси, които отдавна го интересуват.
Тогава Тюринг вероятно не е имал представа, че няколко години по-късно фон Нойман ще му предложи място в Принстън, един от най-известните университети в Съединените щати. Дори по-късно фон Нойман, подобно на Тюринг, ще бъде наречен „бащата на компютърните науки“. Но тогава, в началото на 30-те години на ХХ век, научните интереси и на двамата бъдещи изключителни учени бяха далеч от компютрите - както Тюринг, така и фон Нойман се занимаваха главно с проблеми на „чистата“ математика.
Тюринг произлиза от аристократично семейство, но никога не е бил „естет“: политическите и литературните среди на Кеймбридж са му чужди. Той предпочиташе да учи любимата си математика, а в свободното си време да провежда химически експерименти и да решава шахматни пъзели.
Докато извършва химически експерименти, той играе специална игра „Пустинен остров“, измислена от самия него. Целта на играта беше да се получат различни „полезни“ химикали от „импровизирани материали“ - прах за пране, препарат за миене на съдове, мастило и подобни „домакински химикали“.
Той също намира релакс в интензивни спортове като гребане и бягане. Маратонското бягане ще остане негово страстно хоби до края на живота му.
Тюринг блестящо завършва своя четиригодишен курс на обучение. Една от неговите работи, посветена на теорията на вероятностите, беше удостоена със специална награда и той беше избран в научното общество на Кралския колеж. През 1935 г. Тюринг публикува „Еквивалентността на лявата и дясната почти периодичност“, в която той опростява идеята на фон Нойман в теорията на непрекъснатите групи, фундаментална област на съвременната математика. Изглеждаше, че ще има успешна кариера като леко ексцентричен преподавател в Кеймбридж, работещ в областта на „чистата“ математика.
Тюринг обаче никога не е бил държан в някаква "рамка". Никой не можеше да предвиди какъв екзотичен проблем внезапно ще го плени и какъв математически необикновен начин ще може да измисли, за да го реши.
Освен това Алън посещава лекции на Лудвиг Витенщайн в Кеймбридж. Витенщайн изложи теория за непоследователността на математиката. Според него математиката не търси истината, а сама я създава. Алън не беше съгласен с това и много спореше с Лудвиг. Тюринг се застъпва за „формализъм“ – математическо философско движение, което не изисква точен превод на думите и е ограничено до приблизително значение. А Лудвиг търсеше абсолютна точност.
Докато е в колежа, Алън Тюринг изучава основите на криптографията - тоест дешифрирането на данни. Това беше полезно по време на Втората световна война, когато ученият работи върху дешифрирането на немски съобщения.
Машина на Тюринг
През 1928 г. немският математик Дейвид Хилберт привлича вниманието на световната общественост към проблема за естествознанието (Entscheidungsproblem). В своята работа „За изчислимите числа, с приложение към Entscheidungsproblem“, публикувана на 12 ноември 1936 г. Тюринг преформулира теоремата за непълнотата на Гьодел, заменяйки универсалния формален аритметичен език на Гьодел с прости хипотетични устройства, които по-късно стават известни като машини на Тюринг.Той доказа, че такава машина би била в състояние да извърши всяко математическо изчисление, което може да бъде представено под формата на алгоритъм. Тюринг продължи, за да покаже, че няма решение на проблема Entscheidungs, като първо докаже, че проблемът със спирането е неразрешим за машина на Тюринг: като цяло е невъзможно да се определи алгоритмично дали дадена машина на Тюринг някога ще спре.
Въпреки че доказателството на Тюринг е публикувано малко след еквивалентното доказателство на Алонзо Чърч, което използва ламбда смятане, самият Тюринг не е бил запознат с него. Подходът на Алън Тюринг се смята за по-достъпен и интуитивен. Идеята за „Универсална машина“, способна да изпълнява функциите на всяка друга машина, или с други думи, да изчислява всичко, което по принцип може да бъде изчислено, беше изключително оригинална. Фон Нойман призна, че концепцията за съвременния компютър се основава на тази работа на Алън Тюринг. Машините на Тюринг все още са основният обект на изследване в теорията на алгоритмите.
На въпроса: „Какво е машина на Тюринг и какво общо има тя с програмирането?“ Един потребител на Toster отговори:
На първо място, това е формална дефиниция на алгоритъма. Един проблем се счита за алгоритмично разрешим, ако и само ако неговото решение може да бъде програмирано с помощта на машина на Тюринг (или някакъв друг еквивалентен метод). Тази дефиниция позволява например да се представят алгоритмично неразрешими проблеми. Позволява ви да въведете концепцията за „пълен по Тюринг“ език - ако машина на Тюринг може да бъде реализирана на език, тогава всеки алгоритъм може да бъде написан на него (препроцесорът на езика C не е такъв, но C# е).Като цяло MT е начин за дефиниране на определен клас алгоритми:
Някои проблеми могат да бъдат решени от краен автомат;
- някои ще изискват държавна машина със стекова памет;
- за други е достатъчна машина на Тюринг;
- за останалото е необходимо божествено откровение или други неалгоритмични методи.
От септември 1936 г. до юли 1938 г. Тюринг работи под ръководството на Чърч в Принстън. В допълнение към изучаването на математика, ученият изучава криптография и също така проектира електромеханичен двоичен умножител.
През юни 1938 г. Тюринг защитава докторската си дисертация „Логически системи, базирани на ординали“, която въвежда идеята за редукция на Тюринг, която включва комбиниране на машина на Тюринг с оракул. Това ни позволява да изследваме проблеми, които не могат да бъдат решени само с помощта на машина на Тюринг.
Криптоанализ
По време на Втората световна война Алън Тюринг участва активно в разбиването на немски кодове в Блечли Парк. Историкът и ветеран от Блечли Парк Аса Бригс веднъж каза:„Блечли Парк имаше нужда от изключителен талант, изключителен гений, а геният на Тюринг беше точно това.“
От септември 1938 г. Тюринг работи на непълен работен ден за GCHQ, британска организация, специализирана в разбиване на кодове. Заедно с Дили Нокс той се занимава с криптоанализ на Enigma. Малко след среща във Варшава през юли 1939 г., на която Полското бюро за шифри предоставя на Великобритания и Франция подробности за връзките в роторите на Енигма и метода за дешифриране на съобщения, Тюринг и Нокс започват работата си върху по-задълбочен начин за решаване на проблем.
Полският метод се основава на недостатъци в индикаторната процедура, които германците коригират до май 1940 г. Подходът на Тюринг беше по-общ и се основаваше на метода за изброяване на последователности от изходния текст, за който той разработи първоначалната функционална спецификация на Bombe.
Машина, изградена от тази спецификация, потърси възможните настройки, използвани за шифроване на съобщения (ред на ротора, позиция на ротора, връзки на пач панела) въз основа на известен обикновен текст. За всяка възможна настройка на ротора (която имаше 10^19 състояния или 10^22 във версията, използвана на подводници), машината направи серия от логически предположения, базирани на обикновения текст (неговото съдържание и структура).
След това машината определи противоречието, отхвърли набора от параметри и премина към следващия. Така повечето от възможните комплекти бяха елиминирани и останаха само няколко варианта за задълбочен анализ.
Първата машина е пусната в експлоатация на 18 март 1940 г. Търсенето на ключове се извършваше чрез въртящи се механични барабани, придружени от звук, подобен на тиктакането на часовник.
Спецификацията за бомбата беше само първото от петте големи постижения на Тюринг в областта на военния криптоанализ.
Ученият също така определи индикаторната процедура на германския флот; разработи по-ефективен начин за използване на Bombe, базиран на статистически анализ и наречен "Banburismus"; метод за определяне на параметрите на колелата на машина на Лоренц, наречен „Thuringerie”; Към края на войната Тюринг разработва преносимия говорен скрамблер Delilah.
Статистическият подход за оптимизиране на изследването на различни вероятности в процеса на решаване на шифри, който Тюринг използва, беше нова дума в науката. Тюринг написа две статии: „Документ за приложимостта на вероятностния подход към криптоанализа“ и „Документ за статистиката и повторението“, които бяха от такава стойност за GCCS и по-късно за GCHQ (Щаб за правителствени комуникации), че не бяха публикувани в Националния архив до април 2012 г., малко преди честването на стогодишнината от рождението на учения. Един служител на GCHQ каза, че този факт показва безпрецедентната важност на тази работа.
Тюринг участва и в разработването на шифри за кореспонденцията между Чърчил и Рузвелт, като прекарва периода от ноември 1942 г. до март 1943 г. в Съединените щати.
През 1945 г. Тюринг е награден с OBE от крал Джордж VI за военната си служба, но този факт остава в тайна дълги години.
Следвоенни години
След като фон Нойман в Съединените щати предложи план за създаване на компютъра EDVAC, подобна работа започна във Великобритания в Националната физическа лаборатория, където Тюринг работи от 1945 г. Ученият предложи много амбициозен проект ACE (Automatic Computing Engine), който обаче така и не беше реализиран.Въпреки че изграждането на ACE беше осъществимо, тайната около Blatchley Park доведе до забавяне на началото на работата, което разочарова Тюринг.
Тюринг прекарва академичната 1947–1948 г. в Кеймбридж. Докато Алън Тюринг беше в Кеймбридж, Pilot ACE беше построен в негово отсъствие.
Франклин ACE 1200
Той завършва първата си програма на 10 май 1950 г. Въпреки че пълната версия на ACE никога не е създадена, някои компютри имаха много прилики с него, като DEUCE и Bendix G-15.
През май 1948 г. той получава предложение да заеме поста учител и заместник-директор на компютърната лаборатория в университета в Манчестър, който по това време заема водеща позиция в развитието на компютърните технологии в Обединеното кралство.
През 1948 г. Алън, заедно с бившия си колега, започват да пишат програма за шах за компютър, който все още не съществува.
Същата година Тюринг изобретява метода на LU декомпозиция, който се използва за решаване на системи от линейни уравнения, обръщане на матрици и изчисляване на детерминантата.
Тест на Тюринг
През 1948 г. Алън Тюринг е повишен в четец в катедрата по математика в университета в Манчестър. Там през 1949 г. той става директор на компютърната лаборатория, където е съсредоточена работата по програмирането на Manchester Mark I.В същото време Тюринг продължава да работи върху по-абстрактни математически проблеми и в работата си „Компютърни машини и интелигентност“ (списание Mind, октомври 1950 г.) той разглежда проблема с изкуствения интелект и предлага експеримент, който по-късно става известен като Тюринг тест.
Неговата идея беше, че компютърът може да се счита за „мислещ“, ако човекът, който взаимодейства с него, не може да различи компютъра от друг човек по време на комуникационния процес. В тази работа Тюринг предполага, че вместо да се опитвате да създадете програма, която симулира ума на възрастен, би било много по-лесно да започнете с ума на дете и след това да го тренирате. CAPTCHA, базирана на обратния тест на Тюринг, се използва широко в Интернет.
През 1951 г. Тюринг е избран за член на Лондонското кралско общество.
В първоначалната си формулировка „тестът на Тюринг“ предполага ситуация, в която двама души, мъж и жена, комуникират по някакъв канал, който изключва възприемането на глас с трето лице, отделено от тях със стена, което се опитва да определи пола на всеки от събеседниците им чрез непреки въпроси; в този случай мъжът се опитва да обърка питащия, а жената помага на питащия да разбере истината.
Въпросът е дали една машина може да участва също толкова успешно в тази „игра на имитация“ вместо човек (дали питащият ще греши също толкова често в заключенията си). Впоследствие широко разпространение получи опростена форма на теста, при която се определя дали човек, общуващ в подобна ситуация с определен събеседник, може да определи дали общува с друг човек или с изкуствено устройство.
Този мисловен експеримент имаше редица фундаментални последици. Първо, той предложи някакъв оперативен критерий за отговор на въпроса „Може ли една машина да мисли?“
Второ, този критерий се оказа лингвистичен: зададеният въпрос беше изрично заменен с въпроса дали машината може адекватно да комуникира с човек на естествен език. Тюринг пише директно за промяната във формулировката и в същото време изразява увереност, че „методът на въпросите и отговорите е подходящ за покриване на почти всяка област на човешка дейност, която искаме да въведем под внимание“.
Последствието от това беше решаващата роля, която изследванията върху моделирането на разбирането и производството на естествен език изиграха в по-нататъшното развитие на изкуствения интелект, поне до 80-те години. През 1977 г. тогавашният директор на лабораторията за изкуствен интелект в Масачузетския технологичен институт П. Уинстън пише, че обучението на компютъра да разбира естествения език е същото като постигането на интелект като цяло.
С развитието на компютърните технологии интересът към личността на Алън Тюринг се увеличи. Кой беше този човек? Каква следа оставихте в историята на компютърните науки и математиката? Защо това име беше забравено за дълго време?
Кой е Алън Тюринг, какви са неговите заслуги за науката? Днес има много хора, които могат уверено да отговорят на този въпрос. И още повече в тесни професионални кръгове - нито един съвременен учебник по математическа логика не може без „машина на Тюринг“. Ученият е добре познат и на специалистите в областта на компютърните науки. Вярно, за някои това знание е малко едностранчиво. „Тюринг е първият хакер“ е всичко, което знаят за този брилянтен човек.
Въпреки факта, че Алън Тюринг може да бъде поставен наравно с най-известните математици, например Декарт или Лайбниц, признанието му дойде много години след смъртта му. Самият Тюринг обаче приживе е направил всичко възможно откритията му да не получат достойно признание от съвременниците му. Безразличието на учения към собствените му постижения работи срещу него.
Личността на Алън Тюринг е много противоречива. И неговият жизнен път не може да се нарече гладък. За да разберем този човек, трябва да се обърнем към безпристрастните факти от неговата биография.
Детство
Какво според вас е необходимо, за да се роди гений? От биологична гледна точка гените на родителите му трябва да бъдат смесени по уникален начин. И не само родители, а всички предци до n-то коляно. Природата се подготвя за появата на гений много преди датата на неговото раждане.
И тогава през 1912 г., на 23 юни, се ражда малкият Алън. Това се случи в Англия в една от лондонските болници. Алън Матисън беше второто дете на родителите си. Между другото, бащата и майката на учения се срещнаха не в Лондон, а в далечна Индия (друга чудесна случайност, която доведе до появата на гений). Баща ми е служил в тази страна дълго време - до 1926 г. Братята Алън и Джон останаха под грижите на семейни приятели, а след това в частен пансион в Лондон, където получиха истинско английско образование.
От ранна детска възраст момчето се интересуваше от науки като математика, физика и химия. След като се научи да чете на шестгодишна възраст, Алън започна да изучава не приказки като всички деца, а научно-популярна литература. Той дори сам провежда доста сериозни химически експерименти: например получава йод от водорасли. Родителите му се страхуваха, че тези хобита ще му попречат да влезе в престижно английско училище. Въпреки че тези страхове бяха напълно неоснователни.
На 13-годишна възраст по-малкият Тюринг влезе в известното училище в Шерборн. Това училище, за съжаление, имаше хуманитарни пристрастия, които не съответстваха на хобитата на Алън Матесън. Затова през годините на обучение той беше известен като лош ученик, което, както виждате, отново не е необичайно за гении. С поведението си той доведе до стрес учители по хуманитарни специалности. Но как, да попитам, едно дете ще се държи в часовете, които са му напълно безинтересни? След училище, вместо да си пише домашните, Тюринг изучава теорията на относителността.
Въпреки това дори в това училище имаше учители, които успяха да забележат изключителния талант на момчето. Един от записите в класния регистър гласи, че такива ученици се раждат само веднъж на два века и той си губи времето в Шерборнското училище. Тюринг обаче е изправен пред сериозна заплаха да остане без сертификат.
Така че би трябвало да прекара последните си учебни години в униние и разочарование, ако не се беше случила чудесна среща: Алън стана приятел с Кристофър Морком. За Тюринг това приятелство се превърна в истинско спасение. Съучениците му бяха уплашени от ексцентричния му външен вид, необичайни прически и начин на говорене. И той и Крис се оказаха сродни души: те се излежаваха заедно в клас, учеха заедно астрономия и математика, мечтаеха за Кеймбридж заедно. Внезапната смърт на Крис беше първият удар върху живота на Тюринг. Още повече вярваше в безсмъртието на човешкия Дух. С течение на времето това вярване беше силно разклатено, но Тюринг се интересуваше от човешкия ум през целия си живот.
Първи стъпки в науката
През 1931 г. Алън Матисън, най-лошият ученик в училище, постъпва в Кингс Колидж, Кеймбридж. Тук той успя да се занимава истински с любимата си наука. Той беше особено очарован от математиката и квантовата физика. Тези дисциплини отговориха на много от въпросите, които го интересуваха. Ексцентричното поведение на Тюринг продължава да отблъсква „правилните“ ученици. Алън обаче завършва училище с отличие четири години по-късно. И от 1936 г., в продължение на около две години, той работи в Принстън под ръководството на А. Чърч. През 1938 г., след като защитава докторската си дисертация, Тюринг се завръща в Англия, където продължава да учи теория на числата и логика. В същото време посещава семинари по философия на математиката на Л. Витгенщайн, с когото влиза в спорове на различни позиции.
Машина на Тюринг
През 1934 г. Тюринг слуша лекции на известния М. Нюман. Там за първи път се сблъсква с проблема с алгоритмите. Преди това този проблем беше повдигнат от Д. Гилбърт през 1900 г. Наричаше се „десетият проблем на Хилберт“. Възможно ли е да се реши математическа задача с помощта на алгоритми? Тогава понятието „алгоритъм“ просто не съществуваше. Тюринг предполага съществуването на определена машина, която може сама да изучава света около себе си. Тази машина не е физически обект, а абстрактен обект. Много години по-късно обаче идеите са приложени на практика.
Разбивач на кодове
Още преди избухването на Втората световна война Тюринг се интересува от криптография и започва работа в Блечли Парк. Още тогава участва в разгадаването на немски кодове. И с избухването на войната Тюринг напълно се прехвърли в тази организация. Bletchley Park се нуждаеше от брилянтен служител и го получиха.
През 1939 г. британското военно министерство възлага на учения да разсекрети Enigma, криптиращо устройство. Немските радиограми не реагираха на нито един декодер. Всички смятаха Енигма за перфектна. Сложността на шифъра беше, че той съдържаше повече букви от оригиналния текст. Тюринг, заедно със своите колеги шахматисти, измисли достоен отговор на Енигма - Бомбата. Това беше истинска бомба за германците: устройството незабавно дешифрира радиосъобщенията. Впоследствие приятелите подобриха своята „Бомба“ с подобрението на „Енигма“.
Тюринг кодира и кореспонденцията между Рузвелт и Чърчил. За постиженията си е награден с Ордена на Британската империя.
Тест на Тюринг
След войната Тюринг се занимава с различни дейности, включително криптология. Той също не се отказа от страстта си към спорта: шах и бягане. Много хора не знаят, че Тюринг имаше световни резултати в кроса. В едно от състезанията той показа време по-добро от сребърния медалист от Олимпиадата през 1948 г. Между другото, Тюринг разработи и първата компютърна програма за шах. Нищо чудно, че казват, че талантливият човек е талантлив във всичко!
Но ученият показа по-значителни постижения в следвоенния период в областта на създаването на изкуствен интелект. Тюринг е натоварен със задачата да разработи софтуера за първата "мислеща машина". Ученият беше много заинтересован от въпроса за възможността човек да бъде заменен с машина. Известният тест беше предложен в списание Mind. Същността на този експеримент е да се създаде ситуация, в която се оценява способността на машината да мисли. Ще може ли човек да разпознае кой е събеседникът му - изкуствено устройство или друг човек? И днес тази тема е обект на разгорещени дебати в науката.
Въпреки успеха в научната дейност, личният живот на Тюринг претърпява серия от провали. Пътуването до Гърция и контактите с чужбина създават проблем със службата за сигурност. В живота на Тюринг започва тъмна ивица, причиняваща тежка депресия. На 8 юни 1954 г. най-големият гений на своето време Алън Матисън Тюринг е намерен мъртъв в собствения си дом. Той е бил отровен с цианид калий. Младежката страст към химията изигра фатална роля. Самият Тюринг се сдобива с отровното вещество и го инжектира в ябълката. Много години по-късно ябълката става символ на известната компютърна корпорация Apple. Гениалният учен е живял само 41 години.
За специални постижения в областта на компютърните науки ежегодно се присъжда награда на името на Тюринг. А през 2002 г. е обявен за един от 100-те най-велики хора на Великобритания.