Машина Тьюринга: различия между версиями

На страницах [[w:Википедия|Википедии]] уже сейчас можно найти информацию почти по любой теме. Задавшись целью разузнать побольше про [[w:машина Тьюринга|машину Тьюринга]], мы приглашаем Вас совершить вместе с нами свободное плавание по её статьям. Посетим статьи про машину Тьюринга и её разновидности, узнаем кое-что о первых [[w:хакер|хакерхакерах]]ах Алане Тьюринге и Алонзо Чёрче, заглянем в мир будущего "«молекулярных компьютеров"» и вспомним фантастических роботов [[w:Азимов, Айзек|Азимова]] и [[w:Лем, Станислав|Лема]]. Итак, вперёд!

Про машину Тьюринга, пожалуй, должен знать любой школьник, мечтающий стать [[w:программист|программистом]]. Ведь именно её считают основой основ теории [[w:алгоритм|алгоритмов]]. Конечно, это не инженерное устройство, не изобретение наподобие [[w:арифмометр|арифмометра]], а что-то вроде [[w:Демон_МаксвеллаДемон Максвелла|демона Максвелла]]: изначально абстрактное порождение мысли очень умного человека, [[w:Алан Тьюринг|Алана Тьюринга]], который, позаимствовав идею у Эмиля Поста, придумал её, как считается, в 1936 году. Несмотря на довольно сложное формальное определение, идея в принципе проста. Чтобы понять её, давайте прогуляемся по страницам Википедии.

Первым делом мы попадаем на страничку, которая, собственно, так и называется: "«[[w:машина Тьюринга|машина Тьюринга]]"».

'''Машина Тьюринга (МТ)'''  — математическая абстракция, представляющая [[w:Вычислительная машина|вычислительную машину]] общего вида. Была предложена [[W:Тьюринг, Алан Матисон|Аланом Тьюрингом]] в [[w:1936|1936]] году для формализации понятия [[w:алгоритм|алгоритмалгоритма]]а.

Машина Тьюринга является расширением модели [[w:конечный автомат|конечного автомата]] и, согласно [[w:тезис Чёрча — Тьюринга|тезису Чёрча  — Тьюринга]], способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

Управляющее устройство может перемещаться влево и вправо по ленте,

Выделяется особый ''пустой'' символ, заполняющий все клетки ленты,

Каждое правило из таблицы предписывает

Итак, машина Тьюринга  — математическая [[w:абстракция|абстракция]], умозрительное построение человеческого разума: в природе её нет. Или есть? Сразу приходит на ум, как работает живая [[w:клетка (биология)|клетка]]. Хотя бы два примера.

1. Для производства белков в клетке с помощью сложно устроенного фермента  — РНК-полимеразы  — считывается информация с ДНК, своего рода информационной ленты машины Тьюринга. Здесь, правда, не происходит перезапись ячеек самой ленты, но в остальном процесс весьма похож: РНК-полимераза садится на ДНК и двигается по ней в одном направлении, при этом она синтезирует нить [[w:РНК|РНК]]  — нуклеиновой кислоты, сходной с ДНК. Готовая РНК, отсоединяясь от фермента, несёт информацию к клеточным органеллам, в которых производятся белки.

2. Ещё более похож на машину Тьюринга процесс исправления ошибок в ДНК  — её репарация. Здесь ДНК-полимераза вместе с другими белками двигается по ленте ДНК и считывает обе её половинки (геномная ДНК, как известно, представляет собой две переплетенных нити, несущих одну и ту же информацию). Если информация в половинках не совпадает, ДНК-полимераза принимает одну из них за образец и «правит» другую.

'''Биомолекулярные вычисления''' или '''молекулярные компьютеры''' или даже [[w:ДНК|ДНК]]- или [[w:РНК|РНК]]-вычисления  — все эти термины появились на стыке таких различных наук как молекулярная генетика и вычислительная техника.

Биомолекулярные вычисления  — это собирательное название для различных техник, так или иначе связанных с ДНК или РНК. При ДНК-вычислениях данные представляются не в форме нулей и единиц, а в виде [[w:молекула|молекулярной]] структуры, построенной на основе спирали ДНК. Роль [[w:программное обеспечение|программного обеспечения]] для чтения, копирования и управления данными выполняют особые [[w:фермент|ферментферменты]]ы.

Основой всей системы хранения биологической информации, а стало быть, и ДНК-компьютеров, является способность атомов [[w:водород|водородводорода]]а, входящих в [[w:азот|азотазотистые]]истые соединения ([[w:аденин|аденин]], [[w:тимин|тимин]], [[w:цитозин|цитозин]] и [[w:гуанин|гуанин]]), при определенных условиях притягиваться друг к другу, образуя [[w:Валентность|невалентно]] связанные пары. С другой стороны, эти вещества могут валентно связываться с сочетаниями молекулы [[w:сахары|сахара]] (дезоксирибозы) и [[w:фосфаты|фосфата]], образуя так называемые [[w:нуклеотиды|нуклеотиды]]. Нуклеотиды, в свою очередь, легко образуют полимеры длиной в десятки миллионов оснований. В этих супермолекулах фосфат и дезоксирибоза играют роль поддерживающей структуры (они чередуются в цепочке), а азотистые соединения кодируют информацию.

Молекула получается направленной: начинается с фосфатной группы и заканчивается дезоксирибозой. Длинные цепочки ДНК называют нитями, короткие  — олигонуклеотидами. Каждой молекуле ДНК соответствует еще одна ДНК  — так называемое [[w:дополнение Ватсона — Крика|дополнение Ватсона  — Крика]]. Она имеет противоположную направленность, нежели оригинальная молекула. В результате притяжения аденина к тимину и цитозина к гуанину получается знаменитая двойная спираль, обеспечивающая возможность удвоения ДНК при размножении клетки. Задача удвоения решается с помощью специального белка-[[w:Энзима|энзимы]]  — полимеразы. Синтез начинается только если с ДНК прикреплен кусочек ее дополнения, Данное свойство активно используется в молекулярной биологии и молекулярных вычислениях. По сути своей ДНК + полимераза  — это реализация [[w:Машина Тьюринга|машины Тьюринга]], состоящая из двух лент и программируемого пульта управления. Пульт считывает данные с одной ленты, обрабатывает их по некоторому алгоритму и записывает на другую ленту. Полимераза также последовательно считывает исходные данные с одной ленты (ДНК) и на их основе формирует ленту как бы с результатами вычислений (дополнение Ватсона  — Крика).

'''Конечный автомат''' (в [[w:теория алгоритмов|теории алгоритмов]])  — [[w:математика|математическая]] [[w:абстракция|абстракция]], позволяющая описывать пути изменения [[w:состояние|состояния]] объекта в зависимости от его текущего состояния и [[w:входные данные|входных данных]], при условии что общее возможное количество состояний [[w:конечное множество|конечно]]. Конечный автомат является частным случаем [[w:абстрактный автомат|абстрактного автомата]]. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.

Где K  — конечное множество состояний автомата, <math> s \in K</math>  — единственно допустимое начальное состояние автомата, <math>F \subset K</math>  — множество конечных состояний, причём допустимо F=Ø, и F=K, Σ  — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, <math>\pi : K \times \Sigma \rightarrow K</math>  — функция переходов.

'''Абстра́ктный автома́т''' (в [[w:теория алгоритмов|теории алгоритмов]])  — [[w:математика|математическая]] [[w:абстракция|абстракция]], [[w:модель|модель]] [[w:дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[w:состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[w:символ|символсимволы]]ы одного [[w:язык|языкязыка]]а, на выходе оно выдаёт символы (в общем случае) другого языка.

Где S  — конечное множество состояний автомата, X, Y  — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, <math>\delta : S \times X \rightarrow S</math>  — функция переходов, <math>\lambda : S \times X \rightarrow Y</math>  — функция выходов.

[[w:Модель|Модель]] абстрактного автомата широко используется, как базовая, для построения дискретных моделей распознающих, порождающих и преобразующих последовательности [[w:символ|символсимволов]]ов.

С каждым определением мы всё больше вторгаемся в область чистой математики. Язык становится строже, появляются формальные определения, состоящие из математических символов. Если двигаться дальше, мы придём к теории алгоритмов и теории вычислимости. Путешествовать по страницам Википедии можно долго, но лучше запастись водой и едой, на случай забредания в пустыни аксиом и определений, или хотя бы надёжными ссылками на учебники по математике, например http://www.mccme.ru/free-books/, или статьи журнала "«Потенциал"» ;)

Итак, как мы уже упоминали, Алан Тьюринг поведал миру о своей машине в 1937 году в так называемом Тезисе Чёрча-Тьюринга. Про Алана Тьюринга  — первого хакера и пионера информатики, как написано на мемориальной доске гостиницы, где он родился, поведает нам статья "«Алан Тьюринг"». Текст статьи полностью приводить здесь не будем, но она и сама по себе не очень подробная.

'''Тьюринг, Алан Матисон''' (23 июня 1912  — 7 июня 1954)  — английский математик, логик, криптограф, изобретатель Машины Тьюринга.

В самой статье больше про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над "«проблемой зависания"» (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код "«Энигмы"» во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искуственногоискусственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.

Несмотря на свою старомодность, тест Тьюринга всплыл неожиданным образом в современном мире общения по интернету. К примеру, можно встретить текст диалога двух пользователей ICQ, один из которых является "«ботом"», и задача  — определить, какой именно. Или к Вам может постучаться незнакомый пользователь, возможно, ICQ-робот. Узнаете ли вы его? Изучая теорию, Вы, возможно, сумеете вовремя применить тест Тьюринга и не останетесь обмануты. Начать изучение можно с соответствующей статьи в Википедии, а затем пройтись по ссылкам, приводимым в конце статьи:

Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году, компьютер с памятью 1 миллиард бит (около 119 Мб) в ходе 5-минутного теста сможет обмануть судей в 30 % случаев. Это предсказание не сбылось. (Правда, на первом конкурсе Лебнера компьютерная программа "«PC Therapist"» на IBM PC 386 смогла ввести в заблуждение 5 судей из 10, но ей не засчитали результат, а в 1994 году конкурс усложнили.) Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться [[w:оксюморон|оксюмороном]], а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).

Пока что ни одна программа и близко не подошла к прохождению теста. Такие программы, как Элиза ([[w:ELIZA|ELIZA]]), иногда заставляли людей верить, что они говорят с человеком, как, например, в неформальном эксперименте, названном AOLiza. Но такие «успехи» не являются прохождением теста Тьюринга. Во-первых, человек в таких беседах не имел никаких оснований считать, что он говорит с программой, в то время как в настоящем тесте Тьюринга человек активно пытается определить, с кем он беседует. Во-вторых, документированые случаи обычно относятся к таким чатам, как [[w:IRC|IRC]], где многие беседы отрывочны и бессмысленны. В-третьих, многие пользователи IRC используют английский как второй или третий язык, и бессмысленный ответ программы, вероятно, спишется ими на языковый барьер. В-четвертых, многие пользователи ничего не знают об Элизе и ей подобных программах и не могут распознать совершенно нечеловеческие ошибки, которые эти программы допускают.

Ежегодно производится соревнование между разговаривающими программами, и наиболее человекоподобной, по мнению судей, присуждается приз Лебнера (Loebner). Есть дополнительный приз для программы, которая, по мнению судей, пройдёт тест Тьюринга. Этот приз ещё не присуждался.

* Тьюринг А.  М.  Вычислительные машины и разум. // В сб.: Хофштадер Д., Деннет Д. Глаз разума.  — Самара: Бахрах-М, 2003.  — С. 47-59.

* Книга на английском: Roger Penrose "«The Emperor'sEmperor’s New Mind"».

** Alan Turing, "«Computing Machinery and Intelligence"», Mind, vol. LIX, no. 236, October 1950, pp. 433-460433—460.

*** http://xn--80agpkhko7a.xn--p1ai/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0.html браузерный эмулятор машины Тьюринга

* Статья Дж. Оппи (G. Oppy) и [http://www.csse.monash.edu.au/~dld Д. Дави (D. Dowe)] о [http://plato.stanford.edu/entries/turing-test тесте Тьюринга] из [http://plato.stanford.edu Стэнфордской Философской Энциклопедии] (на английском)

* [http://crl.ucsd.edu/~saygin/papers/MMTT.pdf "«Turing Test: 50 Years Later"»] обзор 50-летней работы над тестом Тьюринга, с точки зрения 2000  г. (на английском).

Возвращаемся опять к машине Тьюринга. В выдержке из статьи про Алана Тьюринга утверждается, что впервые понятие машины Тьюринга было предложено в составе т. н. тезиса Чёрча-Тьюринга:

== Выдержка из статьи Википедии "«Алан Тьюринг"» ==

Алан Тьюринг высказал предположение (известное как Тезис Чёрча-Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (т.е.то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

В статье под названием "«Те́зис Чёрча—Тью́ринга"» про него пишут так:

'''Те́зис Чёрча—Тью́ринга'''  — фундаментальное утверждение для многих областей науки, таких, как [[w:Теория вычислимости|теория вычислимости]], [[w:Информатика|информатика]], теоретическая кибернетика и др. Это утверждение было высказано [[w:Чёрч, Алонзо|Алонзо Чёрчем]] и [[w:Тьюринг, Алан|Аланом Тьюрингом]] в середине [[w:1930-е|1930-х]] годов.

С этого перекрёстка можно двинуться в сторону, к примеру, теории вычислимости. А можно попытаться выяснить, кто такой этот загадочный Чёрч, вместе с которым Алан Тьюринг выдвинул свой тезис.

развития вычисления, на котором выдается ответ '''1''', и '''0'''  — в противном

Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется [[w:класс_BPPкласс BPP|классом BPP]].

:* [[w:Машина Тьюринга|Машина Тьюринга]]

:* [[w:Универсальная машина Тьюринга |Универсальная машина Тьюринга]]

:* [[w:Недетерминированная машина Тьюринга|Недетерминированная машина Тьюринга]]

:* [[w:Вероятностная машина Тьюринга|Вероятностная машина Тьюринга]]

:* [[w:Теория алгоритмов|Теория алгоритмов]]

:* [[w:Алан Тьюринг|Статья об Алане Тьюринге]]

* [http://kleron.ucoz.ru/load/24-1-0-52 Программная реализация на Delphi]