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

м
clean up, removed: Категория:Информатика с помощью AWB
(Отмена неверного отката. Отмена правки 126801, сделанной участником Iniquity (обс.))
м (clean up, removed: Категория:Информатика с помощью AWB)
[[Файл:turing.jpg|Машина Тьюринга|200px|right]]
Про машину Тьюринга, пожалуй, должен знать любой школьник, мечтающий стать [[w:программист|программистом]]. Ведь именно её считают основой основ теории [[w:алгоритм|алгоритмов]]. Конечно, это не инженерное устройство, не изобретение наподобие [[w:арифмометр|арифмометра]], а что-то вроде [[w:Демон_Максвелла|демона Максвелла]]: изначально абстрактное порождение мысли очень умного человека, [[w:Алан Тьюринг|Алана Тьюринга]], который придумал её, как считается, в 1936 году. Несмотря на довольно сложное формальное определение, идея в принципе проста. Чтобы понять её, давайте прогуляемся по страницам Википедии.
 
 
 
Первым делом мы попадаем на страничку, которая, собственно, так и называется: "[[w:машина Тьюринга|машина Тьюринга]]".
читать и записывать в ячейки символы некоторого конечного алфавита.
Выделяется особый ''пустой'' символ, заполняющий все клетки ленты,
кроме тех из них (конечного числа), на которых записаны входные данные.
 
В управляющем устройстве содержится ''таблица переходов'', которая представляет алгоритм, ''реализуемый'' данной Машиной Тьюринга.
 
== Конечный автомат ==
'''Конечный автомат''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], позволяющая описывать пути изменения [[w:состояние|состояния]] объекта в зависимости от его текущего состояния и [[w:входные данные|входных данных]], при условии что общее возможное количество состояний [[w:конечное множество|конечно]]. Конечный автомат является частным случаем [[w:абстрактный автомат|абстрактного автомата]]. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.
 
Формально конечный автомат определяется как пятёрка
{{Акмар}}
 
В самой статье больше про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над "проблемой зависания" (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код "Энигмы" во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искуственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.
 
Несмотря на свою старомодность, тест Тьюринга всплыл неожиданным образом в современном мире общения по интернету. К примеру, можно встретить текст диалога двух пользователей ICQ, один из которых является "ботом", и задача — определить, какой именно. Или к Вам может постучаться незнакомый пользователь, возможно, ICQ-робот. Узнаете ли вы его? Изучая теорию, Вы, возможно, сумеете вовремя применить тест Тьюринга и не останетесь обмануты. Начать изучение можно с соответствующей статьи в Википедии, а затем пройтись по ссылкам, приводимым в конце статьи:
== Тест Тьюринга ==
 
'''Тест Тьюринга''' — тест, предложенный Аланом Тьюрингом в 1950 г. в статье «Вычислительные машины и разум» (Computing machinery and intelligence) для проверки, является ли компьютер разумным в человеческом смысле слова.
 
Судья (человек) переписывается на естественном языке с двумя собеседниками, один из которых — человек, другой — компьютер. Если судья не может надёжно определить, кто есть кто, компьютер прошёл тест. Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. С целью сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями.
Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос «может ли машина мыслить?» на более определённый.
 
Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году, компьютер с памятью 1 миллиард бит (около 119 Мб) в ходе 5-минутного теста сможет обмануть судей в 30% случаев. Это предсказание не сбылось. (Правда, на первом конкурсе Лебнера компьютерная программа "PC Therapist" на IBM PC 386 смогла ввести в заблуждение 5 судей из 10, но ей не засчитали результат, а в 1994 году конкурс усложнили.) Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться [[w:оксюморон|оксюмороном]], а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).
 
Пока что ни одна программа и близко не подошла к прохождению теста. Такие программы, как Элиза ([[w:ELIZA|ELIZA]]), иногда заставляли людей верить, что они говорят с человеком, как, например, в неформальном эксперименте, названном AOLiza. Но такие «успехи» не являются прохождением теста Тьюринга. Во-первых, человек в таких беседах не имел никаких оснований считать, что он говорит с программой, в то время как в настоящем тесте Тьюринга человек активно пытается определить, с кем он беседует. Во-вторых, документированые случаи обычно относятся к таким чатам, как [[w:IRC|IRC]], где многие беседы отрывочны и бессмысленны. В-третьих, многие пользователи IRC используют английский как второй или третий язык, и бессмысленный ответ программы, вероятно, спишется ими на языковый барьер. В-четвертых, многие пользователи ничего не знают об Элизе и ей подобных программах и не могут распознать совершенно нечеловеческие ошибки, которые эти программы допускают.
'''Те́зис Чёрча—Тью́ринга''' — фундаментальное утверждение для многих областей науки, таких, как [[w:Теория вычислимости|теория вычислимости]], [[w:Информатика|информатика]], теоретическая кибернетика и др. Это утверждение было высказано [[w:Чёрч, Алонзо|Алонзо Чёрчем]] и [[w:Тьюринг, Алан|Аланом Тьюрингом]] в середине [[w:1930-е|1930-х]] годов.
 
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является [[w:частично вычислимая функция|частично вычислимой]], или, эквивалентно, может быть вычислена с помощью некоторой [[w:Машина Тьюринга|машины Тьюринга]].
 
Тезис Чёрча—Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием [[w:частично вычислимая функция|частично вычислимой функции]] и неформальным понятием «интуитивно вычислимой функции».
'''Физический тезис Чёрча—Тьюринга''' гласит: ''Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга''.
{{Акмар}}
 
 
С этого перекрёстка можно двинуться в сторону, к примеру, теории вычислимости. А можно попытаться выяснить, кто такой этот загадочный Чёрч, вместе с которым Алан Тьюринг выдвинул свой тезис.
{{Рамка}}
 
 
== Универсальная машина Тьюринга ==
Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е. если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct<sup>2</sup>''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в 1936-37 г.
{{Акмар}}
 
 
{{Рамка}}
 
Обобщение [[w:машина Тьюринга|детерминированной машины Тьюринга]], в которой, при каждом переходе,
можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).
 
Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
 
Недетерминированная машина Тьюринга выдаст ответ '''1''', если ''существует хотя бы один'' путь
* [http://kleron.ucoz.ru/load/24-1-0-52 Программная реализация на Delphi]
 
[[Категория:Алгоритмы]]
[[Категория:Информатика]]
{{Готовность|75%}}
 
[[Категория:{{Темы|Информатика]]}}
 
[[Категория:Алгоритмы]]
531

правка