Думка — матеріальна: Алан Тьюринг як «універсальний обчислювач»

image
Джерело: geektimes.ru

У першій половині XX століття, коли були винайдені перші обчислювальні машини. Однак поряд з фізично відчутними машинами з'являлися і машини-концепції. Однією з них була «машина Тьюрінга» — абстрактне обчислювальний пристрій, створене в 1936 році Аланом Тюрінгом — ученим, якого вважають одним з основоположників інформатики.

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

Дитинство, освіта, захоплення

Батьки Алана жили в індійському місті Чхатрапур. Батько — Юліус Метісон Тьюринг представник старого шотландського аристократичного роду, працював в Імперській державній службі. Мати — Сара Етель (уроджена Стоні), була родом з Ірландії, з протестантської родини англо-ірландського дворянства. Коли вона чекала дитину, подружжя вирішило переїхати в Англію, щоб він ріс і виховувався в Лондоні.

Там Алан Тьюринг і народився 23 червня 1912 року. У нього був старший брат Джон. Державна служба Юліуса Тюрінга тривала і батькам Алана доводилося часто подорожувати між Гастінгсом та Індією, залишаючи двох своїх синів на піклування відставний армійської пари. Ознаки геніальності проявлялися у Тюрінга з раннього дитинства.

У дитинстві Алан і його старший брат Джон досить рідко бачили своїх батьків — їх батько до 1926 року служив в Індії; діти залишалися в Англії і жили на утриманні у приватних будинках, отримуючи суворе англійське виховання, відповідне їх положення на соціальних сходах. В рамках такого виховання вивчення основ природничих наук фактично не передбачалося.

image

Маленький Алан мав дуже допитливим розумом. Самостійно навчившись читати у віці 6 років, він просив у своїх вихователів дозволу читати науково-популярні книги.

В 11 років він ставив цілком грамотні хімічні досліди, намагаючись витягти йод з водоростей. Все це приносило величезне занепокоєння його матері, яка боялася, що захоплення сина, що йдуть врозріз із традиційним вихованням, завадять йому вступити у Public School (англійське закрите приватний навчальний заклад для хлопчиків, навчання в якому була обов'язкова для дітей аристократів). Але побоювання виявилися марними: Алан зміг поступити в престижну Шербонскую школу (Sherborne Public School).

У шість років Алан Тьюринг пішов в школу святого Михайла в Гастінгсі, директор якої відразу відзначила його обдарованість. У 1926 році, у віці 13 років, Тюрінг пішов у відому приватну школу Шерборна в місті Шерборна графства Дорсет. Його перший день у школі збігся із Загальним страйком 1926 року. Тому Тьюрингу довелося подолати відстань близько 100 км від Саутгемптона до Шерборна на велосипеді, по дорозі він переночував у готелі.

Захоплення Тюрінга математикою не знайшла особливої підтримки серед вчителів Шерборнской школи, де приділяли більше уваги гуманітарних наук. Директор школи писав батькам: «Я сподіваюся, що він не буде намагатися всидіти на двох стільцях разом. Якщо він має намір залишитися в приватній школі, то він повинен прагнути до отримання «освіти». Якщо ж він збирається бути виключно «науковим спеціалістом», то приватна школа для нього — марна трата часу».

image

Про шкільні успіхи Алана красномовно свідчить класний журнал, в якому можна знайти, наприклад, наступне
Я можу дивитися крізь пальці на його твори, хоча нічого жахливішого в житті своєму не бачив, я намагаюся терпіти його непохитну недбалість і непристойне старанність; але винести приголомшливу дурість його висловлювань під час цілком здоровій дискусії з Нового Завіту я, все ж, не можу.
Тим не менш, в областях, цікавили його, Тюрінг проявляв неабиякі здібності.

У 1928 році, у віці 16 років, Тюрінг ознайомився з роботою Ейнштейна, в якій йому вдалося розібратися до такої міри, що він зміг здогадатися з тексту про сумніви Ейнштейна щодо здійсненності Законів Ньютона, які не були висловлені у статті в явному вигляді.

Університет

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

Кембриджський університет, який володів особливими привілеями, дарованими англійськими монархами, здавна славився ліберальними традиціями, і в його стінах завжди панував дух вільнодумства. Тут Тьюринг знаходить – мабуть, вперше – свій справжній дім, де він зміг повністю віддатися науці.

Головне місце в житті зайняло захоплене вивчення настільки, що його цікавлять наук – математики і квантової фізики. Ті роки були періодом бурхливого становлення квантової фізики, і Тьюринга в студентські роки знайомиться з останніми роботами в цій області. Велике враження справляє на нього книга Джона фон Неймана «Математичні основи квантової механіки», в якій він знаходить відповіді на багато давно цікавлячі його питання.

image

Тоді Тьюринг, напевно, і не припускав, що через кілька років фон Нейман запропонує йому місце в Прінстоні – одному з найвідоміших університетів США. Ще пізніше фон Нейман, так само як і Тьюринг, буде названий «батьком інформатики». Але тоді, на початку 30-х років ХХ століття, наукові інтереси обох майбутніх видатних учених були далекі від обчислювальних машин – і Тьюринг, і фон Нейман займаються в основному завданнями «чистої» математики.

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

Ставлячи хімічні досліди, він грав в особливу гру «Безлюдний острів», винайдену ним самим. Мета гри полягала в тому, щоб отримувати різні «корисні» хімічні речовини з «підручних засобів» – прального порошку, засоби для миття посуду, чорнила і тому подібної «домашньої хімії».

Він також знаходив відпочинок в інтенсивних заняттях спортом – веслуванням і бігом. Марафонський біг залишиться його воістину пристрасним захопленням до кінця життя.

image

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

Однак Тьюринг ніколи не утримувався в якихось рамках. Ніхто не міг передбачити, яка екзотична проблема несподівано захопить його, і який математично неординарний спосіб її рішення йому вдасться придумати.

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

Під час навчання в коледжі Алан Тьюринг вивчав основи криптографії – тобто розшифровки даних. Це придалося йому під час Другої Світової війни, коли вчений працював над розшифровкою німецьких послань.

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

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

Він довів, що така машина була б здатна справити будь-які математичні обчислення, представимые у вигляді алгоритму. Далі Тьюринг показав, що не існує рішення Entscheidungsproblem, спершу довівши, що Проблема зупинки для машини Тюрінга нерозв'язна: у загальному випадку неможливо алгоритмічно визначити, чи зупиниться коли-небудь ця машина Тюрінга.

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

image

запитання: «Що таке машина Тьюринга і яке відношення вона має до програмування?» з користувачів Toster відповів так:
В першу чергу — це формальне визначення алгоритму. Завдання вважається алгоритмічно вирішуваною тоді і тільки тоді, коли її рішення можна запрограмувати на машині Тюрінга (або яким-небудь іншим еквівалентним способом). Це визначення дає, наприклад, можливість пред'явити алгоритмічно нерозв'язні завдання. Дозволяє ввести поняття «Тьюринг-повного» мови — якщо на мові можна реалізувати машину Тюрінга, то на ньому можна написати будь-який алгоритм (препроцесор мови З таким не є, а C# — є).

Загалом, МТ — спосіб визначити певний клас алгоритмів:

— деякі завдання можна вирішити кінцевим автоматом;
— для деяких потрібно кінцевий автомат з стекової пам'яті;
— для інших достатньо машини Тюрінга;
— для решти потрібно божественне одкровення або інші неалгоритмизируемые методи.
З вересня 1936 року по липень 1938 Тьюринг працював під керівництвом Черча в Прінстоні. Крім занять математикою, вчений вивчав криптографію, а також конструював електромеханічний бінарний помножувач.

image

У червні 1938 року Тьюринг захистив докторську дисертацію «Логічні системи, засновані на ординалах», в якій була представлена ідея відомості по Тьюрингу, яка полягає в об'єднанні машини Тюрінга з оракулом. Це дозволяє дослідити проблеми, які неможливо вирішити лише за допомогою машини Тюрінга.

Криптоаналіз

Під час Другої світової війни Алан Тьюринг брав активну участь у зломі німецьких шифрів в Блетчлі-парку. Історик і ветеран Блетчлі-парку Эйза Брігс одного разу сказав:

«Блетчлі-парку був потрібен винятковий талант, виняткова геніальність, і геніальність Тюрінга була саме такою».

З вересня 1938 року Тьюринг працював на півставки в ЦПС — британської організації, що спеціалізувалася на зломі шифрів. Спільно з Діллі Ноксом він займався криптоанализом «Енігми». Незабаром після зустрічі у Варшаві в липні 1939 року, на якій польське Бюро шифрів надало Великобританії і Франції докладні відомості про з'єднання в роторах «Енігми» і метод розшифровки повідомлень, Тюрінг та Нокс почали свою роботу над більш ґрунтовним способом вирішення проблеми.

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

Машина, створена на основі цієї специфікації, шукала можливі настройки, використані для шифрування повідомлень (порядок роторів, положення ротора, з'єднання комутаційної панелі), спираючись на відомий відкритий текст. Для кожної можливої налаштування ротора (у якого було 10 ^ 19 станів або 10 ^ 22 у модифікації, яка використовувалася на підводних човнах) машина виробляла ряд логічних припущень, грунтуючись на відкритому тексті (його зміст і структуру).

Далі машина визначала протиріччя, відкидала набір параметрів і переходила до наступного. Таким чином, більша частина можливих наборів отсеивалась і для ретельного аналізу залишалося всього кілька варіантів.
Перша машина була запущена в експлуатацію 18 березня 1940 року. Перебір ключів виконувався за рахунок обертання механічних барабанів, що супроводжувався звуком, схожим на цокання годинника.

image

Специфікація для «Бомби» була тільки першим з п'яти найважливіших досягнень Тюрінга в області військового криптоаналізу.

Вчений також визначив індикаторну процедуру ВМФ Німеччини; розробив більш ефективний спосіб використання Bombe, заснований на статистичному аналізі і названий «Банбурисмусом»; метод визначення параметрів коліс машини Лоренца, названий «Тьюринжерией»; ближче до кінця війни Тьюрінг розробив портативний шифратор мови Delilah.

Статистичний підхід до оптимізації досліджень різних ймовірностей у процесі розгадування шифрів, який використовував Тьюринг, був новим словом у науці. Тьюринг написав дві роботи: «Доповідь про застосування імовірнісного підходу в криптоаналізу» і «Документ про статистику і повтореннях», які представляли для GCCS, а пізніше і для ЦПС (англ. Government Communications Headquarters) таку цінність, що не були надані національного архіву аж до квітня 2012 року, незадовго до святкування ста років з дня народження вченого. Один із співробітників ЦПС заявив, що цей факт говорить про безпрецедентну важливість цих робіт.

Тьюринг займався також розробкою шифрів для листування Черчілля і Рузвельта, провівши період з листопада 1942 року по березень 1943 року в США.

У 1945 році Тьюринг був нагороджений орденом Британської імперії королем Георгом VI за свою військову службу, але цей факт залишався в секреті багато років.

Повоєнні роки

Після того як фон Нейман в США запропонував план створення комп'ютера EDVAC, аналогічні роботи були розгорнуті у Великобританії в Національній фізичній лабораторії, де Тьюринг пропрацював з 1945 року. Вчений запропонував досить амбітний проект АСІ (Automatic Computing Engine – Автоматична Обчислювальна Машина), який, проте, так і не був реалізований.

Незважаючи на те, що споруда ACE була цілком здійсненна, секретність, що оточувала Блэтчли-парк, призвела до затримок у початку робіт, що розчарувало Тюрінга.

1947-1948 академічний рік Тьюринг провів у Кембриджі. Поки Алан Тьюринг перебував у Кембриджі, Pilot ACE був побудований у його відсутність.

image
Franklin ACE 1200

Він виконав свою першу програму 10 травня 1950 року. Хоча повна версія ACE ніколи не була побудована, деякі комп'ютери мали з ним багато спільного, наприклад, DEUCE і Bendix G-15.

У травні 1948 року отримав пропозицію зайняти посаду викладача та заступника директора обчислювальної лабораторії Манчестерського університету, який до цього часу лідируючі позиції в розробці обчислювальної техніки у Великобританії.

У 1948 році Алан спільно зі своїм колишнім колегою почав писати шахову програму для комп'ютера, який ще не існував.

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

Тест Тюрінга

У 1948 році Алан Тьюринг отримав звання Reader в математичному департаменті Манчестерського університету. Там у 1949 році він став директором комп'ютерної лабораторії, де була зосереджена робота по програмуванню Манчестерського Марка I.

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

Його ідея полягала в тому, що можна вважати, що комп'ютер «мислить», якщо людина, який взаємодіє з ним, не зможе в процесі спілкування відрізнити комп'ютер від іншої людини. У цій роботі Тьюринг припустив, що замість того, щоб намагатися створити програму, симулирующую розум дорослої людини, набагато простіше було б почати з розуму дитини, а потім навчати його. CAPTCHA, заснований на зворотному тест Тюрінга, широко поширений в інтернеті.

У 1951 році Тьюринг був обраний членом Лондонського королівського суспільства.

image

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

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

Цей уявний експеримент мав ряд принципових наслідків. По-перше, він запропонував деякий операціональний критерій для відповіді на питання «чи Може машина мислити?».

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

Наслідком цього стала та найважливіша роль, яку в подальшому розвитку штучного інтелекту, у всякому разі, до 1980-х років грали дослідження по моделюванню розуміння і виробництва природної мови. У 1977 році тодішній директор лабораторії штучного інтелекту Массачусетського технологічного інституту П. Уїнстон писав, що навчити комп'ютер розуміти природну мову – це все одно, що домогтися побудови інтелекту взагалі.

image
Джерело: slideshare.net

Пам'ять

• ім'ям ученого названий один з астероїдів;

• щорічна відзнака Асоціації обчислювальної техніки називається Премією Тьюринга;

• на головній площі університету Суррея (Англія) є статуя Тюрінга і одну з будівель факультету інженерних і фізичних наук названо в його честь;

• одна з аудиторій відділу інформатики при Університеті Лілль у Північній Франції названий на честь Алана М. Тюрінга;

• Манчестерський університет, Відкритий університет, Університет Оксфорд Брукс і Університет Орхус (Данія) мають корпусу імені Тюрінга та інші;

• у 2001 році в Манчестері був встановлений пам'ятник вченому.

image
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.