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

Перейти к навигации Перейти к поиску
орфография, викификатор
(орфография, викификатор)
Журнал [[Журнал «Потенциал»|Потенциал]]
 
На страницах [[w:Википедия|Википедии]] уже сейчас можно найти информацию почти по любой теме. Задавшись целью разузнать побольше про [[w:машина Тьюринга|машину Тьюринга]], мы приглашаем Вас совершить вместе с нами свободное плавание по её статьям. Посетим статьи про машину Тьюринга и её разновидности, узнаем кое-что о первых [[w:хакер|хакерхакерах]]ах Алане Тьюринге и Алонзо Чёрче, заглянем в мир будущего "«молекулярных компьютеров"» и вспомним фантастических роботов [[w:Азимов, Айзек|Азимова]] и [[w:Лем, Станислав|Лема]]. Итак, вперёд!
 
== Введение ==
[[Файл:turing.jpg|Машина Тьюринга|200px|right]]
Про машину Тьюринга, пожалуй, должен знать любой школьник, мечтающий стать [[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:конечное множество|конечно]]. Конечный автомат является частным случаем [[w:абстрактный автомат|абстрактного автомата]]. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.
 
Формально конечный автомат определяется как пятёрка
<math>M = (K , \Sigma , \pi , s , F)</math>
 
Где K  — конечное множество состояний автомата, <math> s \in K</math>  — единственно допустимое начальное состояние автомата, <math>F \subset K</math>  — множество конечных состояний, причём допустимо F=Ø, и F=K, Σ  — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, <math>\pi : K \times \Sigma \rightarrow K</math>  — функция переходов.
Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов. Процесс продолжается до тех пор, пока не будет достигнуто одно из состояний F.
 
 
{{Рамка}}
 
== Абстрактный автомат ==
'''Абстра́ктный автома́т''' (в [[w:теория алгоритмов|теории алгоритмов]])  — [[w:математика|математическая]] [[w:абстракция|абстракция]], [[w:модель|модель]] [[w:дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[w:состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[w:символ|символсимволы]]ы одного [[w:язык|языкязыка]]а, на выходе оно выдаёт символы (в общем случае) другого языка.
 
Формально абстрактный автомат определяется как пятёрка
<math>~A = (S, X , Y, \delta , \lambda)</math>
 
Где S  — конечное множество состояний автомата, X, Y  — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, <math>\delta : S \times X \rightarrow S</math>  — функция переходов, <math>\lambda : S \times X \rightarrow Y</math>  — функция выходов.
Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом абстрактный автомат определяет семейство инициальных автоматов
 
Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента [[w:Машина Тьюринга|машин Тьюринга]], [[w:автомат с магазинной памятью|автоматов с магазинной памятью]], [[w:конечный автомат|конечных автоматов]] и других преобразователей информации.
 
[[w:Модель|Модель]] абстрактного автомата широко используется, как базовая, для построения дискретных моделей распознающих, порождающих и преобразующих последовательности [[w:символ|символсимволов]]ов.
{{Акмар}}
 
С каждым определением мы всё больше вторгаемся в область чистой математики. Язык становится строже, появляются формальные определения, состоящие из математических символов. Если двигаться дальше, мы придём к теории алгоритмов и теории вычислимости. Путешествовать по страницам Википедии можно долго, но лучше запастись водой и едой, на случай забредания в пустыни аксиом и определений, или хотя бы надёжными ссылками на учебники по математике, например http://www.mccme.ru/free-books/, или статьи журнала "«Потенциал"» ;)
 
Надеюсь, после этого объяснения вам стало немного яснее, что же такое машина Тьюринга?
Давайте вернёмся к истории этого термина.
 
Итак, как мы уже упоминали, Алан Тьюринг поведал миру о своей машине в 1937 году в так называемом Тезисе Чёрча-Тьюринга. Про Алана Тьюринга  — первого хакера и пионера информатики, как написано на мемориальной доске гостиницы, где он родился, поведает нам статья "«Алан Тьюринг"». Текст статьи полностью приводить здесь не будем, но она и сама по себе не очень подробная.
 
{{Рамка}}
 
== Алан Тьюринг ==
'''Тьюринг, Алан Матисон''' (23 июня 1912  — 7 июня 1954)  — английский математик, логик, криптограф, изобретатель Машины Тьюринга.
{{Акмар}}
 
В самой статье больше про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над "«проблемой зависания"» (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код "«Энигмы"» во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искуственногоискусственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.
 
Несмотря на свою старомодность, тест Тьюринга всплыл неожиданным образом в современном мире общения по интернету. К примеру, можно встретить текст диалога двух пользователей ICQ, один из которых является "«ботом"», и задача  — определить, какой именно. Или к Вам может постучаться незнакомый пользователь, возможно, ICQ-робот. Узнаете ли вы его? Изучая теорию, Вы, возможно, сумеете вовремя применить тест Тьюринга и не останетесь обмануты. Начать изучение можно с соответствующей статьи в Википедии, а затем пройтись по ссылкам, приводимым в конце статьи:
 
{{Рамка}}
 
== Тест Тьюринга ==
'''Тест Тьюринга'''  — тест, предложенный Аланом Тьюрингом в 1950  г. в статье «Вычислительные машины и разум» (Computing machinery and intelligence) для проверки, является ли компьютер разумным в человеческом смысле слова.
 
Судья (человек) переписывается на естественном языке с двумя собеседниками, один из которых  — человек, другой  — компьютер. Если судья не может надёжно определить, кто есть кто, компьютер прошёл тест. Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. С целью сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями.
'''Тест Тьюринга''' — тест, предложенный Аланом Тьюрингом в 1950 г. в статье «Вычислительные машины и разум» (Computing machinery and intelligence) для проверки, является ли компьютер разумным в человеческом смысле слова.
 
Переписка должна производиться через контролируемые промежутки времени, чтобы судья не мог делать заключения исходя из скорости ответов. (Во времена Тьюринга компьютеры реагировали медленнее человека. Сейчас это правило необходимо, потому что они реагируют гораздо быстрее, чем человек).
Судья (человек) переписывается на естественном языке с двумя собеседниками, один из которых — человек, другой — компьютер. Если судья не может надёжно определить, кто есть кто, компьютер прошёл тест. Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. С целью сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями.
 
Тест был инспирирован салонной игрой, в ходе которой гости пытались угадать пол человека, находящегося в другой комнате, путём написания вопросов и чтения ответов. В оригинальной формулировке Тьюринга, человек должен был притворяться человеком противоположного пола, а тест длился 5 минут. Сейчас эти правила не считаются необходимыми и не входят в спецификацию теста.
Переписка должна производиться через контролируемые промежутки времени, чтобы судья не мог делать заключения исходя из скорости ответов. (Во времена Тьюринга компьютеры реагировали медленнее человека. Сейчас это правило необходимо, потому что они реагируют гораздо быстрее, чем человек).
 
Тест был инспирирован салонной игрой, в ходе которой гости пытались угадать пол человека, находящегося в другой комнате, путём написания вопросов и чтения ответов. В оригинальной формулировке Тьюринга, человек должен был притворяться человеком противоположного пола, а тест длился 5 минут. Сейчас эти правила не считаются необходимыми и не входят в спецификацию теста.
 
Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос «может ли машина мыслить?» на более определённый.
 
Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году, компьютер с памятью 1 миллиард бит (около 119 Мб) в ходе 5-минутного теста сможет обмануть судей в 30 % случаев. Это предсказание не сбылось. (Правда, на первом конкурсе Лебнера компьютерная программа "«PC Therapist"» на IBM PC 386 смогла ввести в заблуждение 5 судей из 10, но ей не засчитали результат, а в 1994 году конкурс усложнили.) Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться [[w:оксюморон|оксюмороном]], а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).
 
Пока что ни одна программа и близко не подошла к прохождению теста. Такие программы, как Элиза ([[w:ELIZA|ELIZA]]), иногда заставляли людей верить, что они говорят с человеком, как, например, в неформальном эксперименте, названном AOLiza. Но такие «успехи» не являются прохождением теста Тьюринга. Во-первых, человек в таких беседах не имел никаких оснований считать, что он говорит с программой, в то время как в настоящем тесте Тьюринга человек активно пытается определить, с кем он беседует. Во-вторых, документированые случаи обычно относятся к таким чатам, как [[w:IRC|IRC]], где многие беседы отрывочны и бессмысленны. В-третьих, многие пользователи IRC используют английский как второй или третий язык, и бессмысленный ответ программы, вероятно, спишется ими на языковый барьер. В-четвертых, многие пользователи ничего не знают об Элизе и ей подобных программах и не могут распознать совершенно нечеловеческие ошибки, которые эти программы допускают.
 
Ежегодно производится соревнование между разговаривающими программами, и наиболее человекоподобной, по мнению судей, присуждается приз Лебнера (Loebner). Есть дополнительный приз для программы, которая, по мнению судей, пройдёт тест Тьюринга. Этот приз ещё не присуждался.
 
Самый лучший результат в тесте Тьюринга показала программа [http://www.alicebot.org/ A.L.I.C.E.] выиграв тест 3 раза (в 2000, 2001 и 2004).
 
=== Ссылки ===
* Тьюринг А.  М.  Вычислительные машины и разум. // В сб.: Хофштадер Д., Деннет Д. Глаз разума.  — Самара: Бахрах-М, 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 браузерный эмулятор машины Тьюринга
*** http://www.loebner.net/Prizef/TuringArticle.html
* [http://www.loebner.net/Prizef/loebner-prize.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-х]] годов.
 
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является [[w:частично вычислимая функция|частично вычислимой]], или, эквивалентно, может быть вычислена с помощью некоторой [[w:Машина Тьюринга|машины Тьюринга]].
{{Акмар}}
 
С этого перекрёстка можно двинуться в сторону, к примеру, теории вычислимости. А можно попытаться выяснить, кто такой этот загадочный Чёрч, вместе с которым Алан Тьюринг выдвинул свой тезис.
{{Рамка}}
 
== Универсальная машина Тьюринга ==
 
'''Универсальной машиной Тью́ринга''' называют [[w:машина Тьюринга|машину Тьюринга]], которая может заменить собой любую машину Тьюринга. Получив на вход программу и входные данные, она вычисляет ответ, который вычислила бы по входным данным машина Тьюринга, чья программа была дана на вход.
 
=== Формальное определение ===
Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и  т. п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с алфавитом <math>\Sigma_2</math> и ''k'' входными лентами называется машина Тьюринга с ''k+1'' входной лентой и алфавитом <math>\Sigma_1 \cup \Sigma_2</math> такая, что если подать на первые ''k'' лент входное значение, а на ''k+1''  — правильно записанный код некоторой машины Тьюринга <math>M_1</math>, то ''U'' выдаст тот же ответ, какой выдала бы на этих входных данных <math>M_1</math>, или будет работать бесконечно долго, если <math>M_1</math> на этих данных не остановится.
 
Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е.то есть если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct<sup>2</sup>''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в 1936-37 г.
Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т.п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с алфавитом <math>\Sigma_2</math> и ''k'' входными лентами называется машина Тьюринга с ''k+1'' входной лентой и алфавитом <math>\Sigma_1 \cup \Sigma_2</math> такая, что если подать на первые ''k'' лент входное значение, а на ''k+1'' — правильно записанный код некоторой машины Тьюринга <math>M_1</math>, то ''U'' выдаст тот же ответ, какой выдала бы на этих входных данных <math>M_1</math>, или будет работать бесконечно долго, если <math>M_1</math> на этих данных не остановится.
 
Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е. если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct<sup>2</sup>''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в 1936-37 г.
{{Акмар}}
 
 
== Недетерминированная машина Тьюринга ==
Обобщение [[w:машина Тьюринга|детерминированной машины Тьюринга]], в которой, при каждом переходе,
можно выполнять переход одновременно в несколько (константа) состояний  — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).
 
Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае  — экспоненциальное число) путей, по которым может развиваться вычисление.
Обобщение [[w:машина Тьюринга|детерминированной машины Тьюринга]], в которой, при каждом переходе,
можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).
 
Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
 
Недетерминированная машина Тьюринга выдаст ответ '''1''', если ''существует хотя бы один'' путь
развития вычисления, на котором выдается ответ '''1''', и '''0'''  — в противном
случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).
 
 
== Вероятностная машина Тьюринга ==
Обобщение детерминированной машины Тьюринга, в которой из любого состояния и значений на ленте машина может совершить один из нескольких (можно считать, без ограничения общности  — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
 
Обобщение детерминированной машины Тьюринга, в которой из любого состояния и значений на ленте машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
 
Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью.
Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом.
 
Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется [[w:класс_BPPкласс BPP|классом BPP]].
{{Акмар}}
 
== Дальнейшее чтение ==
 
* В Википедии
:* [[w:Машина Тьюринга|Машина Тьюринга]]
:* [[w:Универсальная машина Тьюринга |Универсальная машина Тьюринга]]
:* [[w:Недетерминированная машина Тьюринга|Недетерминированная машина Тьюринга]]
:* [[w:Вероятностная машина Тьюринга|Вероятностная машина Тьюринга]]
:* [[w:Теория алгоритмов|Теория алгоритмов]]
:* [[w:Алан Тьюринг|Статья об Алане Тьюринге]]
* В Викиучебнике
:* [[Чего не могут вычислительные машины]]
* [http://lib.custis.ru/index.php/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 Определения и примеры машин Тьюринга]
* [http://www.loonies.narod.ru/tmr.htm Программная система моделирования работы машины Тьюринга]
* [http://kleron.ucoz.ru/load/24-1-0-52 Программная реализация на Delphi]
 
{{Готовность|75%}}
129

правок

Навигация