Алан Мэтысан Цьюрынг

Алан Мэтысан Цьюрынг (англ.: Alan Mathison Turing; 23 чэрвеня 1912, Лондан — 7 чэрвеня 1954, Вілмслау) — англійскі матэматык, логік, крыптограф, які аказаў вялікі ўплыў на развіццё інфарматыкі. Прапанаваная ім у 1936 годзе абстрактная вылічальная «Машына Цьюрынга» дала магчымасць фармалізаваць паняцце алгарытма і да нашых часоў выкарыстоўваецца ў многіх тэарэтычных і практычных даследваннях. Жыццё Цьюрынга скончылася трагічна. Ён быў прызнаны адной з самых вядомых ахвяр гамафобіі ў Вялікабрытаніі.

Алан Цьюрынг
англ.: Alan Mathison Turing
Фота на пашпарт. 16 гадоў.
Дата нараджэння	23 чэрвеня 1912(1912-06-23)[…]
Месца нараджэння	Maida Vale[d], Вэстмінстэр, графства Вялікі Лондан, Вялікі Лондан, Англія, Злучанае каралеўства Вялікабрытаніі і Ірландыі
Дата смерці	7 чэрвеня 1954(1954-06-07)[…] (41 год)
Месца смерці	Уілмслаў[d], Усходні Чэшыр[d], Чэшыр, Англія, Вялікабрытанія
Месца пахавання	Woking Crematorium[d]
Грамадзянства	Вялікабрытанія
Бацька	Julius Mathison Turing[d]
Маці	Ethel Sara Stoney[d]
Род дзейнасці	спецыяліст у галіне інфарматыкі, крыптограф
Навуковая сфера	матэматыка, логіка, крыптаграфія, інфарматыка
Месца працы	Кембрыджскі ўніверсітэт Нацыянальная фізічная лабараторыя Урадавая школа кодаў і шыфраў Манчэстэрскі ўніверсітэт
Альма-матар	Каралеўскі каледж, Кембрыдж Прынстанскі ўніверсітэт
Навуковы кіраўнік	Алонза Чорч
Вядомыя вучні	Робін Гандзі
Вядомы як	вынаходнік машыны Цьюрынга, тэсты Цьюрынга
Член у	Лонданскае каралеўскае таварыства
Узнагароды	Кавалер ордэна Брытанскай імперыі, ваенны член Лонданскага каралеўскага таварыства
Сайт	turingarchive.org (англ.)
Подпіс
Цытаты ў Вікіцытатніку
Творы ў Вікікрыніцах
Медыяфайлы на Вікісховішчы

Дзяцінства і юнацтва

Бацька Алана Цьюрынга, Джуліус Мэтысан Цьюрынг, быў членам Індыйскай грамадзянскай службы. Джуліус і яго жонка Этэль Сара Стоні (1881—1976, дачка Эдуарда Уолера Стоні, галоўнага інжынера чыгункі Мадраса) жадалі, каб Алан выхоўваўся ў Англіі, таму яны вярнуліся ў Лондан, дзе Алан нарадзіўся 23 чэрвеня 1912 года. Пра гэта сведчыць меемарыяльная дошка на знешнім баку будынка, дзе ён нарадзіўся. Ён меў старэйшага брата Джона. Яго бацька па-ранейшаму актыўна працаваў у індыйскай кампаніі, і на працягу дзяцінства Алана яго бацькі падарожнічалі паміж Гастынгсам у Англіі і Індыяй, пакідаючы двух сыноў.

Алан вельмі рана паказаў здольнасці да навучання. Яго бацькі запісалі яго ў школу Святога Майкла ва ўзросце шасці гадоў. Начальніца адразу разглядзела талент малога, як і многія іншыя з наступных яго педагогаў. У 1926 годзе ва ўзросце 14 гадоў, ён пайшоў у вядомую прыватную школу Шэрбарн. Яго першы дзень супаў з усеагульнай стачкай у Вялікабрытаніі, але каб прысутнічаць у школе, ён праехаў на ровары без суправаджэння больш чым 97 кіламетраў з Саўтхэмптана, спыняючыся толькі на ноч у гатэлі.

Схільнасць Цьюрынга да матэматыкі і прыродазнаўчых навук не прынесла яму павагі з боку пэўных настаўнікаў у Шэрбарне, дзе большы ўпор рабіўся на класіку. Дырэктар навучальнай установы пісаў бацькам Алана: «Я спадзяюся, што ён не будзе сядзець паміж двух крэсел, калі ён хоча застацца ў школе, ён павінен імкнуцца стаць адукаваным, калі ён хоча быць толькі навуковым спецыялістам, ён губляе свой час у нашай школе». Нягледзячы на ​​гэта, Цьюрынг працягваў праяўляць дзіўную здольнасць у даследаваннях, якія ён вельмі любіў. Ён вырашаў актуальныя праблемы ў 1927 годзе, не валодаючы нават элементарнымі навыкамі вылічэння. У 1928 годзе, ва ўзросце 16 гадоў, Цьюрынг пазнаёміўся з працамі Альберта Эйнштэйна.

У школе Цьюрынг пасябраваў з Крыстаферам Моркам, які на некалькі гадоў быў старэйшы за Алана. Але ён раптоўна сканаў, як высветлілася з-за ўскладнення бычыных сухотаў, выпіўшы заражанае малако. Пасля гэтага здарэння Алан страціў веру ў Бога і стаў атэістам. Ён пераканаўся, што ўсе з'явы, у тым ліку праца чалавечага мозга, павінны быць матэрыялістычнымі, але ён усё яшчэ верыў у выжыванне душы пасля смерці.

Універсітэт і працы па вылічальнасці

Мемарыяльная статуя ў Манчэстэры

Пасля Шэрбарна, Цьюрынг пайшоў вучыцца ў Каралеўскі каледж у Кембрыджы. Там ён быў студэнтам з 1931 па 1934 гады, скончыўшы з выдатнай адзнакай у галіне матэматыкі. А ў 1935 стаў каралеўскім стыпендыянтам за добрую дысертацыю аб цэнтральнай гранічнай тэарэме.

У сваёй важнай працы «Аб вылічальных ліках, з дадаткам да праблемы вырашальнасці», Цьюрынг перафармуляваў вынікі Курта Гёдэля аб непаўнаце, замяняючы ўніверсальную арыфметычную фармальную мову Гёдэля тым, што зараз вядома як машына Цьюрынга, фармальныя і простыя элементы. Ён даказаў, што некаторыя такія машыны будуць здольныя выконваць любыя магчымыя матэматычныя вылічэнні, калі іх можна прадставіць у выглядзе алгарытму. Ён працягваў даказваць, што няма рашэння праблемы вырашальнасці, таму што праблема прыпынку для машыны Цьюрынга невырашальная, машына ніколі не спыніцца. Аднак яго доказ быў апублікаваны пасля эквівалентнага доказу Алонза Чорча, у якім выкарыстоўваліся лямбда-злічэнні, Алану не было вядома аб працы Чорча на той час.

У сваіх успамінах Цьюрынг пісаў, што ён быў расчараваны тым, што гэтай працай 1936 года зацікавіліся толькі два чалавекі. Гэта былі Генрых Шольц і Рычард Беван Брэйтвэйт.

Падыход Цьюрынга з'яўляецца значна больш даступным і інтуітыўна зразумелым. Алан заклаў новае разуменне паняцця «ўніверсальнай машыны» (машыны Цьюрынга), ідэі, што такая машына магла б выконваць задачы любой іншай машыны. Ці, іншымі словамі, гэта машына даказальна здольная на вылічэнне ўсяго, што можа быць вылічана. Машыны Цьюрынга і па сёння з'яўляюцца асноўным аб'ектам даследавання ў тэорыі вылічэнняў. У сваёй працы ён таксама ўводзіць паняцце вызначальнага ліку.

З верасня 1936 па ліпень 1938 года ён правёў большую частку свайго часу ў Інстытуце перспектыўных даследаванняў у Прынстане, Нью-Джэрсі, дзе вучыўся ў Алонса Чорча. Акрамя матэматыкі Алан вывучаў крыптаграфію, а таксама пабудаваў тры з чатырох ступеней электра-механічнага бінарнага памнажальніка. У чэрвені 1938 года ён атрымаў доктарскую ступень у Прынстане; яго дысертацыя ўводзіла паняцце звядзення паводле Цьюрынга, дзе машыны Цьюрынга былі дапоўнены так званымі аракуламі, што дало магчымасць вывучэння праблем, якія нельга вырашыць толькі машынай Цьюрынга.

Вярнуўшыся ў Кембрыдж, Алан наведваў лекцыі асноў матэматыкі Людвіга Вітгенштэйна. Яны абодва спрачаліся і не згаджаліся адзін з адным; Цьюрынг абараняў фармалізм, а Вітгенштэйн сцвярджаў, што матэматыка не выяўляе ніякіх абсалютных ісцін. Акрамя таго, Цьюрынг таксама пачаў працаваць няпоўны рабочы дзень ва Урадавай школе кода і крыпталогіі.

Машына Цьюрынга

Любая інтуітыўна вылічальная функцыя з'яўляецца часткова рэкурсіўнай, або, эквівалентна, можа быць вылічана з дапамогай некаторай машыны Цьюрынга.

Алан Цьюрынг выказаў дапушчэнне (вядомае як тэзіс Чорча — Цьюрынга), што любы алгарытм у інтуітыўным сэнсе гэтага слова можа быць прадстаўлены эквівалентнай машынай Цьюрынга. Удакладненне ўяўлення аб вылічальнасці на аснове паняцця машыны Цьюрынга (і іншых эквівалентных ёй паняццяў) адкрыла магчымасці для строгага доказу алгарытмічнай невырашальнасці розных масавых праблем (гэта значыць праблем аб знаходжанні адзінага метада рашэння некаторага класа задач, умовы якіх могуць вар'іравацца ў вядомых межах). Найпрасцейшым прыкладам алгарытмічна невырашальнай масавай праблемы з'ўляецца так званая праблема дастасавальнасці алгарытму (якая завецца таксама праблемай прыпынку). Яна заключаецца ў наступным: патрабуецца знайсці агульны метад, які дазваляў бы для адвольнай машыны Цьюрынга (зададзенай праз сваю праграму) і адвольнага пачатковага стану стужкі гэтай машыны вызначыць, ці завершыцца праца машыны за канечны лік крокаў, ці будзе працягвацца неабмежавана доўга.

Крыптааналіз

Падчас Другой сусветнай вайны Цьюрынг быў актыўным удзельнікам адной з пяці груп у Блэтчлі Парку — брытанскім крыптаграфічным цэнтры, дзе займаўся ў рамках праекта «Ультра» расшыфроўкай закадзіраваных нямецкай шыфравальнай машынай «Энігма» паведамленняў крыгсмарынэ і люфтвафэ. Абапіраючыся на працы па крыптааналізу, якія праводзілі ў Польшчы Марыян Рэеўскі, Ежы Ружыцкі і Генрык Зігальскі ад Бюро шыфраў яшчэ да вайны, ён атрымаў разуменне таго, як узламаць «Энігму» і «Lorenz SZ 40/42» (тэлетайпавы шыфр пад кодавай назвай Тунец), і быў адказным за чытанне нямецкіх ваенна-марскіх сігналаў.

У 1945 годзе Цьюрынг быў узнагароджаны ордэнам Брытанскай імперыі за яго ваенныя заслугі, але яго праца засталася тайнай на працягу многіх гадоў. Працуючы ў Блэтчлі парку, Цьюрынг атрымаў рэпутацыю дзівака. Джэк Гуд, крыптааналітык, які працаваў з ім, цытуе Рональда Левіна, які сказаў пра Цьюрынга:

…у першы тыдзень чэрвеня кожнага года ў Алана бываў востры прыступ сенечнай ліхаманкі, таму ён ехаў у офіс у процівагазе. Акрамя таго, яго веласіпед меў загану: праз пэўныя прамежкі часу абрываўся ланцуг. Замест таго, каб адрамантаваць веласіпед, Алан лічыў, колькі разоў трэба націснуць на педалі, а потым прыстасоўваў ланцуг рукамі. Яшчэ адно яго дзівацтва было ў тым, што ён прывязваў свой кубак да батарэі, каб яго не скралі.

За час працы ў Блэтчлі парку, Цьюрынг стаў добрым бегуном на доўгія дыстанцыі, часам бегаючы 64 кіламетры ў Лондан, калі яму было неабходна паспець на сустрэчу на высокім узроўні.

«Бомба» Цьюрынга-Вельхмана

Поўная і рабочая копія «Бомбы» ў Нацыянальным цэнтры кода ў Блэтчлі-Парку

На працягу некалькіх тыдняў пасля прыбыцця ў Блэтчлі Парк, Цьюрынг распрацаваў электрамеханічную машыну, якая магла дапамагчы ўзламаць «Энігму» хутчэй, чым польская распрацоўка «Бомба» 1938 года. Цьюрынгава машына была таксама названа «Бомбай», у гонар арыгінальнай польскай машыны. Ёсць меркаванне, што назву машына атрымала з-за характэрнага гуку пры працы, які нагадваў ціканне гадзінніка. «Бомба», дапрацаваная амерыканскім матэматыкам Горданам Вельхманам, стала асноўным і найбольш аўтаматызаваным сродкам, які выкарыстоўваўся для расшыфроўкі абароненага трафіка «Энігмы».

Джэк Гуд так характэрызуе англійскую вылічальную машыну:

Найбольш важны ўклад у распрацоўку крыптааналітычнай машыны «Бомба», я мяркую, быў зроблены Цьюрынгам. Яго думка, што вы маглі б выкарыстоўваць, па сутнасці, тэарэмы логікі, гучыць для непадрыхтаванага вуха даволі абсурднай, але менавіта, з супярэчнасцей можна выявіць усё.

Прынцып работы «Бомбы» заключаўся ў пераборы магчымых варыянтаў ключа шыфра і спроб расшыфроўкі тэксту, калі была вядомая частка адкрытага тэксту ці структура расшыфраванага паведамлення. Перабор ключоў выконваўся за кошт вярчэння механічных барабанаў. Для кожнага магчымага значэння ключа, зададзенага становішчамі ротараў (колькасць ключоў была роўнай прыкладна 10¹⁹ для сухапутнай «Энігмы» і 10²² для шыфравальных машын, якія выкарыстоўваліся ў падводных лодках), «Бомба» выконвала зверку з вядомым адкрытым тэкстам, што выконвалася электрычна. Першая ў Блэтчлі Парке «Бомба» Цьюрынга была запушчана 18 сакавіка 1940 года. Канструкцыя «Бомбы» Цьюрынга была заснавана на дызайне аднайменнай машыны Рэеўскага.

«Бомба» магла чытаць паведамленні люфтвафэ. Праз паўгода ўдалася спроба ўзламаць і больш устойлівы шыфр крыгсмарынэ. Пазней, да 1943 года, Цьюрынг зрабіў адчувальны ўклад у стварэнне больш дасканалай дэшыфравальнай электронна-вылічальнай машыны «Калос», якая выкарыстоўвалася ў тых жа мэтах.

Першыя камп’ютары і тэст Цьюрынга

Асноўны артыкул: Тэст Цьюрынга

З 1945 па 1947 гады Алан жыў у Лондане і распрацоўваў аўтаматычны разліковы рухавік (ACE) ў Нацыянальнай фізічнай лабараторыі. 19 лютага 1946 года ён прадставіў дакумент, які апісваў прынцыпы пабудовы камп’ютараў з захоўваемымі праграмамі. Аднак нягледзячы на тое, што існавала магчымасць пабудовы ACE, праект быў адкладзены на нейкі час, бо ў пасляваенны час усё яшчэ трымалася атмасфера сакрэтнасці. Гэта вельмі расчаравала Цьюрынга. У канцы 1947 года Алан вярнуўся ў Кембрыдж. Пакуль ён там быў, Pilot ACE быў пабудаваны ў яго адсутнасць. Першы запуск рухавіка адбыўся 10 мая 1950 года, ACE выкананаў сваю першую праграму.

У 1948 годзе Цьюрынг быў прызначаны лектарам на матэматычны факультэт у Манчэстэрскі ўніверсітэт. У 1949 годзе ён стаў намеснікам дырэктара вылічальнай лабараторыі ва ўніверсітэце і працаваў над праграмным забяспячэннем для аднаго з ранніх камп’ютараў з захоўваемымі праграмамі — Манчэстэр Марк 1. У гэты час ён працягваў рабіць больш абстрактныя працы. У кастрычніку 1950 года ў часопісе Mind Алан апублікаваў артыкул «Вылічальная тэхніка і інтэлект», дзе звярнуўся да праблемы штучнага інтэлекту і прапанаваў эксперымент, які стаў вядомы як тэст Цьюрынга, спрабуючы вызначыць стандарт для машыны, каб лічыць яе разумнай. Ідэя заключалася ў тым, што адзін або некалькі людзей павінны задаваць пытанні двум патаемным суразмоўцам і на падставе адказаў вызначаць, хто з іх машына, а хто чалавек. Калі не ўдавалася раскрыць машыну, якая маскіравалася пад чалавека, меркавалася, што машына разумная. У працы Цьюрынг даў меркаванне, што замест стварэння праграмы для імітацыі розума дарослага чалавека, было б лепей імітаваць больш просты дзіцячы розум, а потым правесці курс навучання гэтай машыны. У адваротнай форме тэст Цьюрынга шырока выкарыстоўваецца ў Інтэрнэце; тэст CAPTCHA прызначаны для вызначэння, з’яўляецца карыстальнік чалавекам ці камп’ютарам.

У 1948 годзе, Цьюрынг, працуючы са сваім былым калегам, Дэвідам Чэмперноўнам, пачаў пісаць шахматныя праграмы для камп’ютараў, якія яшчэ не існавалі. У 1952 годзе, не маючы достаткова магутнага камп’ютара, каб выканаць праграму, Цьюрынг гуляў у гульню, у якой ён сам мадэляваў камп’ютар, з паўгадзіны робячы кожны ход. Гульня быля задакументавана. Праграма Цьюрынга прайграла калегу Эліку Глену, але Алан сцвярджаў, што выйграў такім чынам гульню супраць жонкі Чэмперноўна.

Тэст Цьюрынга зрабіў значны ўклад у дэбаты адносна штучнага інтэлекту, якія працягваюцца і дагэтуль. У 1948 годзе ён таксама вынайшаў метад LU раскладання, які сёння выкарыстоўваецца пры рашэнні ўраўненняў матрыцы.

Структураўтварэнне і матэматычная біялогія

Цьюрынг працаваў з 1952 года да самай сваёй смерці ў 1954 годзе над матэматычнай біялогіі, у прыватнасці, вывучаў марфагенез. Ён апублікаваў толькі адну працу на гэту тэму, якая называецца «Хімічныя асновы марфагенеза» ў 1952 годзе, высоўваючы гіпотэзы наконт структураўтварэння. Яго галоўная цікавасць была арыентавана на разуменне філатаксіса, існаванне лікаў Фібаначы ў раслінных структур. Ён выкарыстоўваў рэакцыйна-дыфузійныя ўраўненні, якія адыгрываюць цэнтральную ролю ў галіне структураўтварэння. Таксама гэтая тэма была асветлена ў неапублікаваных працах, якія былі выдадзены ў 1992 годзе пад назвай Collected Works of A.M. Turing. Яго ўклад лічыцца асноўным у гэтай галіне.

Асуджэнне за непрыстойнасць

У студзені 1952 года Цьюрынг сустрэўся з Арнольдам Мюрэем ля кінатэатра ў Манчэстэры. Пасля сумеснага абеду Цьюрынг прапанаваў Мюрэю правесці разам з ім выхадныя ў сваім доме, запрашэнне было прынята, але Мюрэй так і не з'явіўся. Яны сустрэліся зноў у Манчэстэры ў наступны панядзелак, калі Мюрэй пагадзіўся зайсці да Цьюрынга. Праз некалькі тыдняў Мюрэй наведаў дом Цьюрынга зноў, і, мабыць, правёў там ноч.

Пасля Мюрэй з дапамогай саўдзельніка ўварваўся ў дом Цьюрынга, Алан паведаміў пра злачынства ў паліцыю. Падчас следства Цьюрынг прызнаў, што меў сексуальную сувязь з Мюрэем. Гомасексуальныя дзеянні былі незаконнымі на той момант у Злучаным Каралеўстве, таму Цьюрынгу было прад'яўлена абвінавачванне ў грубай непрыстойнасці на падставе артыкула 11 папраўкі крымінальнага закона 1885 года за тое ж злачынства, па якім быў асуджаны Оскар Уайльд больш чым пяцьдзясят гадоў да гэтага.

Цьюрынгу быў дадзены выбар паміж турэмным зняволеннем і ўмоўным тэрмінам са згодай прайсці гарманальнае лячэнне, накіраванае на скарачэнне лібіда. Ён выбраў другое і быў падвергнуты хімічнай кастрацыі з дапамогай ін'екцый гармону эстрагену. Прызнанне Алана прывяло да сумненняў у яго добранадзейнасці, і яму забаранілі працягваць сваю крыптаграфічную працу з Цэнтрам урадавай сувязі.

Смерць

Мемарыяльная дошка на доме, дзе жыў Цьюрынг

8 чэрвеня 1954 года асабісты прыбіральшчык Цьюрынга знайшоў яго мёртвым, Алан памёр у папярэдні дзень. Анатаміраваннем было ўстаноўлена, што прычынай смерці было атручванне цыянідам. Каля яго цела быў знойдзены надкусаны яблык, і хоць яблык не быў правераны на цыянід, была выказана здагадка, што гэта быў сродак, з дапамогай якога смяротная доза была дастаўлена. Следства ўстанавіла, што ён пакончыў жыццё самагубствам. Цьюрынг быў крэміраваны 12 чэрвеня 1954 года. Яго маці сцвярджала, што прыём цыяніду быў выпадковасцю, выкліканай нядбайным захоўваннем яе сынам лабараторных хімічных рэчываў. Біёграф Эндру Ходжэз мяркуе, што Цьюрынг, магчыма, пакончыў з сабой такім чынам, каб не засмучаць сваёй маці.

Гл. таксама

• Паўната паводле Цьюрынга
• Машына Цьюрынга
• Тэст Цьюрынга
• Прэмія Цьюрынга
• Тэзіс Чорча — Цьюрынга

Літаратура

• Цьюрынг Алан Матысан // Беларуская энцыклапедыя: У 18 т. Т. 17: Хвінявічы — Шчытні / Рэдкал.: Г. П. Пашкоў і інш. — Мн. : БелЭн, 2003. — Т. 17. С. 159.
• Jon Agar. The government machine: a revolutionary history of the computer. — MIT Press, 2003. — ISBN 978-0-262-01202-7.
• Алан Мэтысан Цьюрынг (англ.) у праекце «Матэматычная генеалогія».
• Jack Copeland (рэд.). "The Mind and the Computing Machine: Alan Turing and others". The Rutherford Journal.
• Hodges, Andrew (27 August 2007). «Alan Turing». In Edward N. Zalta. Stanford Encyclopedia of Philosophy (Winter 2009 ed.). Stanford University. Retrieved 10 January 2011.
• Gray, Paul (29 March 1999). "Computer Scientist: Alan Turing". TIME. Архівавана з арыгінала 19 студзеня 2011. Праверана 18 студзеня 2013.
• Gleick, James, The Information: A History, A Theory, A Flood, New York: Pantheon, 2011, ISBN 978-0-375-42372-7
• David Leavitt. The man who knew too much: Alan Turing and the invention of the computer. — Phoenix. — ISBN 978-0-7538-2200-5.
• Turing, Sara, Alan M. Turing, Centenary Edition, Cambridge University Press, 2012, ISBN 978-1-107-02058-0
• Andrew Hodges. Alan Turing: the enigma. — Burnett Books, 1992. — ISBN 0-04-510060-8.
• A.P. Mahon. The History of Hut Eight 1939–1945. — UK National Archives Reference HW 25/2.
• Conel Hugh O'Donel Alexander. Cryptographic History of Work on the German Naval Enigma. — The National Archives, Kew, Reference HW 25/1, 1945.
• B. Jack Copeland. Colossus: The secrets of Bletchley Park's code-breaking computers. — Oxford University Press, 2006. — ISBN 978-0-19-284055-4.

Спасылкі

• На Вікісховішчы ёсць медыяфайлы па тэме Алан Мэтысан Цьюрынг