Алан Ц'юрынг. Аракул прадказвае з хаосу

Алан Ц'юрынг марыў стварыць "аракула", здольнага адказаць на любое пытанне. Ні ён, ні хто іншы не пабудаваў такой машыны. Аднак кампутарную мадэль, якую прыдумаў у 1936 году геніяльны матэматык, можна лічыць матрыцай кампутарнага стагоддзя – ад простых калькулятараў да магутных суперкампутараў.

Машына, пабудаваная Цьюрынгам, уяўляе сабою простую алгарытмічную прыладу, нават прымітыўнае ў параўнанні з сённяшнімі кампутарамі і мовамі праграмавання. І ўсё ж ён дастаткова моцны, каб дазволіць выконваць нават самыя складаныя алгарытмы.

Алан Т'юрынг

У класічным азначэнні машына Цьюрынга апісваецца як абстрактная мадэль кампутара, выкарыстоўваная для выканання алгарытмаў, якая складаецца з бясконца доўгай стужкі, падзеленай на палі, у якіх запісваюцца дадзеныя. Стужка можа быць бясконцай з аднаго боку або з абодвух бакоў. Кожнае поле можа знаходзіцца ў адным з N станаў. Машына заўсёды размешчана над адным з палёў і знаходзіцца ў адным з М-станаў. У залежнасці ад камбінацыі стану машыны і палі машына запісвае новае значэнне ў поле, мяняе стан і затым можа перамясціць адно поле направа або налева. Такая аперацыя называецца замовай. Машына Цьюрынга кіруецца спісам, які змяшчае любую колькасць такіх каманд. Лікі N і M могуць быць любымі, абы яны былі канчатковымі. Спіс інструкцый для машыны Цьюрынга можна разглядаць як яе праграму.

Базавая мадэль мае ўваходную стужку, падзеленую на вочкі (квадраты), і галоўку стужкі, якая можа назіраць толькі адну вочка ў любы момант часу. Кожная ячэйка можа змяшчаць адзін сімвал з канчатковага алфавіту сімвалаў. Умоўна лічыцца, што паслядоўнасць уваходных знакаў размяшчаецца на стужцы, пачынальна злева, астатнія вочкі (справа ад уваходных знакаў) запаўняюцца адмысловым сімвалам стужкі.

Такім чынам, машына Цьюрынга складаецца з наступных элементаў:

• рухомая галоўка чытання/запісы, якая можа перамяшчацца па стужцы, перамяшчаючыся па адным квадраце за раз;
• канчатковае мноства станаў;
• канчатковы алфавіт сімвалаў;
• бясконцая паласа з адзначанымі квадратамі, кожны з якіх можа змяшчаць адзін сімвал;
• дыяграма пераходу станаў з інструкцыямі, якія выклікаюць змены пры кожным прыпынку.

Гіперкампутары

Машына Цьюрынга даказвае, што любы кампутар, які мы створым, будзе мець непазбежныя абмежаванні. Напрыклад, звязаныя са знакамітай тэарэмай Гёдэля аб непаўнаце. Англійская матэматык даказаў, што ёсць праблемы, якія кампутар не можа вырашыць, нават калі мы задзейнічаем для гэтай мэты ўсе вылічальныя петафлопсы свету. Напрыклад, вы ніколі не можаце сказаць, ці трапіць праграма ў бясконца паўтаральны лагічны цыкл або ці зможа яна завяршыцца – не паспрабаваўшы спачатку праграму, якая рызыкуе патрапіць у цыкл і т. д. (т. н. завецца стоп-праблемай). Эфект гэтых немагчымасцяў у прыладах, пабудаваных пасля стварэння машыны Цьюрынга, сярод іншага, знаёмы карыстачам кампутараў "сіні экран смерці".

Вокладка кнігі пра Алана Цьюрынга

Праблема сплаву, як паказала праца Явы Зігельмана, апублікаваная ў 1993 году, можа быць вырашана кампутарам на аснове нейронавай сеткі, якая складаецца з працэсараў, злучаных сябар з сябрам спосабам, якія імітуюць структуру мозгу, з вылічальным вынікам ад аднаго, ідучага на «ўваход» да іншаму. З'явілася канцэпцыя «гіперкампутараў», якія выкарыстоўваюць фундаментальныя механізмы Сусвету для выканання вылічэнняў. Гэта былі б - як бы экзатычна гэта ні гучала - машыны, якія выконваюць бясконцую колькасць аперацый за канчатковы час. Майк Стэнэт з брытанскага Шэфілдскага ўніверсітэта прапанаваў, напрыклад, выкарыстанне электрона ў атаме вадароду, які ў тэорыі можа існаваць у бясконцым ліку станаў. Нават квантавыя кампутары цьмянеюць перад адвагай гэтых канцэпцый.

У апошнія гады навукоўцы вяртаюцца да мары аб "аракуле", які сам Ц'юрынг ніколі не будаваў і нават не спрабаваў. Эмет Рэд і Стывен Янгер, спецыялісты Універсітэта штата Місуры, лічаць, што можна стварыць «супермашыну Цьюрынга». Яны ідуць па тым жа шляху, па якім пайшла вышэйзгаданая Хава Зігельман, будуючы нейронавыя сеткі, у якіх на ўваходзе-выхадзе замест значэнняў нуль-адзінка прысутнічае цэлы спектр станаў – ад сігналу "цалкам уключаны" да "цалкам выключаны". Як тлумачыць Рэд у ліпеньскім выпуску NewScientist за 2015 год, "паміж 0 і 1 ляжыць бясконцасць".

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

Да канца 2015 года дзякуючы працы Зігельмана, Рэдда і Янгера павінны быць пабудаваны два прататыпы кампутараў, заснаваных на хаосе. Адзін з іх уяўляе сабой нейронавую сетку, якая складаецца з трох звычайных электронных кампанентаў, злучаных адзінаццаццю сінаптычнымі сувязямі. Другое - гэта фатоннае прылада, якое выкарыстоўвае святло, люстэркі і лінзы для аднаўлення адзінаццаці нейронаў і 3600 сінапсаў.

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

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