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

ленточного символа в таблице соответствует не более одного правила, и

''недетерминированной'' в противном случае.

 

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

 

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

 

Немножко фантастические перспективы только подогревают наше любопытство. Между тем, мы еще не всё выяснили относительно машины Тьюринга. Как вы помните, в статье из Википедии её назвали расширением конечного автомата. Что же это такое конечный автомат? На него, к счастью, даётся ссылка. Заходя по ней, узнаём, что:

 

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

 

Итак, мы выяснили, что на конечном автомате цепочка определений не прерывается. Есть еще некий абстрактный автомат. Что же говорит по его поводу Википедия?

 

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

 

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

== Алан Тьюринг ==

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

 

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

* Статья Дж. Оппи (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 г. (на английском).

 

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

 

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

 

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

 

'''Физический тезис Чёрча—Тьюринга''' гласит: ''Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга''.

 

 

 

Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е. если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct²''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в [[w:1947|1947]] г.

 

 

 

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

 

== Дальнейшее чтение ==