Простыми словами
Недетерминированная Машина Тьюринга
Рассматривая детерминированную машину Тьюринга, мы коснулись и недетерминированной тоже.
Еще раз приведу определение:
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует не более одного правила, и недетерминированной в противном случае.
С тем, что означает "существует не более одного правила", мы разобрались в прошлый раз. А что же значит "в противном случае"?
читать дальшеНапомню принцип действия машины Тьюринга.
Вдоль бесконечной ленты движется каретка, которая называется устройством управления (УУ). Каретка умеет читать символы на ленте и записывать туда другие символы алфавита. УУ может находиться в одном из нескольких состояний, которые описаны заранее. Его (УУ) действие для каждой конкретной ячейки определяются двумя факторами: 1) символом, записанным в эту ячейку, и 2) текущим состоянием.
Так вот, если это самое действие определено однозначно, то такая машина будет детерминированной.
А если нет? Тогда, предположим, что УУ в некотором состоянии перешло в ячейку, в которой оказался некоторый символ. УУ сверяется со своими правилами перехода и видит, что когда оно в данном состоянии встретило данный символ, оно может совершить не четко определенную одну вещь, а сразу несколько разных. И ничто не возбраняет ему (УУ) совершить любую из этих вещей.
Проще говоря, машина оказывается на развилке нескольких дорог, и никто кроме нее не может решить, куда же ей податься. И никто не знает заранее, что же она выберет. Именно поэтому она и называется недетерминированной. Ее поведение становится неопределенным.
И здесь есть несколько интересных моментов, на которые я хотела бы обратить внимание.
1. Как такая машина Тьюринга выбирает, куда ей двинуться на каждой развилке? Ответ на этот вопрос: да никак! Случайным образом. Самое печальное, когда путей у нас много, а правильный из них только один. Но и это печальное не так печально. Сейчас мы с этим разберемся.
2. Про "много путей, из которых правильный только один", я сказала не зря! Для классов задач, решаемых такими машинами (а чуть позже окажется, что недетерминированная машина Тьюринга в частности как раз и решает класс NP) из всех путей по всем развилкам результативным часто оказывается только один.
Если представить это наглядно, то можно вообразить себе детерминированную машину Тьюринга (ДМТ) в виде единственной дорожки, представляющей собой «путь вычислений». Недетерминированная машина Тьюринга (НМТ) в таком случае представляет собой сад расходящихся тропок. Говорят, что она имеет «дерево вычислений». В общем случае у этой машины число путей, по которым может развиваться вычисление, растет экспоненциально.
Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает.
То есть другими словами, если хотя бы один из всех возможных путей приведет к решению задачи, то такая машина пригодна для ее решения. Если же ни один из путей нас не устраивает, то, соответственно, и вся машина нам не подходит.
Говорят еще, что "ДА" и "НЕТ" здесь несимметричны. Думаю, теперь понятно, почему: для "ДА" нам достаточно одного подходящего пути из любого (пусть и очень большого) числа неподходящих; для "НЕТ" нужно, чтобы все пути не подходили одновременно.
3. На вид недетерминированная машина Тьюринга (НМТ) гораздо мощнее, чем детерминированная (ДМТ). И гораздо сложнее. Однако, оказывается, что они эквивалентны! Любую НМТ можно представить в виде ДМТ! Легче лёгкого! Доходя до каждой развилки мы начинаем клонировать машины. То есть недетерминированная машина делится на копии, каждая из которых развивает свою веточку дерева. И так на каждой новой развилке.
Википедия сравнивает этот процесс в многозадачной операционной системой. И в чем-то она права. Разве что вряд ли в операционной системе количество задач растет по экспоненте.
Конечно же, представление НМТ с помощью ДМТ требует значительно больше времени. Насколько больше — неизвестно. И если бы было известно, то задача, которую я и взялась рассматривать: «P = (?) NP» была бы решена!
Класс NP
Вот определение из Википедии:
Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.
Но определение это неполно! Всё так, да не совсем так.
Формальное определение дам в следующий раз. А сейчас просто расскажу, что это такое за класс.
Представьте, что у нас есть недетерминированная машина Тьюринга. Все веточки дерева дают нам 0, то есть не ведут никуда, и только одна дает нам 1, то есть, правильный ответ, — за полиномиальное время. "Полиномиальное время", как мы помним, — это количество шагов, не большее Const*NC, где N — длина входных данных.
Если мы начнем перебирать все цепочки подряд и ходить по всем веточкам, вытягивая их в один линейный и очень длинный путь, мы увязнем, и всё это будет очень долго.
Но представьте, что у нас есть подсказка! На развилке она нам говорит, куда пойти, чтобы сразу добраться до результата!
Мы идем на полиномиальную веточку, которая ведет к ответу, и решаем задачу быстро!
Иногда эту подсказку, как правило, в виде готового решения, которое нужно только проверить, называют свидетелем. Иногда же рассматривают машину Тьюринга с оракулом. То есть, достигая развилки, машина Тьюринга обращается к оракулу — внешнему устройству, выдающему правильные ответы на некоторый круг вопросов.
На практике, однако, поиск свидетелей и построение оракулов — задача не из легких.
Вот, очень простой пример, который можно встретить в литературе в той или иной интерпретации.
Задача. Дано число: 15256677987889881453. Проверить, является оно простым или составным. (Честно скажу, я не проверяла, делится ли сумма цифр на три, не проверяла и другие, менее очевидные признаки делимости, но будем считать, что они не выполняются).
Если мы начнем действовать перебором и подбирать на роль кандидатов в делители все простые числа до квадратного корня из этого числа, мы потратим уйму времени!
Если же мы возьмем себе в помощь "свидетеля": число 123567898761 (которое я специально умножила на другое число, чтобы получить данное), то достаточно просто разделить одно на другое и убедиться, что мы поделили нацело. То есть, со свидетелем эта задача из разряда "нечего делать"; без свидетеля она становится весьма сложной.
Теперь отвлечемся от поиска делителей и/или доказательства простоты. Этот лишь пример, который весьма показателен, но сама задача проверки делится ли число на другое заданное число, конечно, же не относится к классу Р.
А вот если со свидетелем наша задача имеет алгоритмическую сложность Р, то стоит этого свидетеля лишиться, в общем виде получается задача класса NP. Эти задачи легко решить, зная, по какой веточке недетерминированной машины Тьюринга надо пойти, и трудно в противном случае.
На словах это выглядит не слишком убедительно, но давайте посмотрим на картинки.
Вот недетерминированная машина Тьюринга, вернее, конечно, не она сама — она выглядит совсем не так. Это дерево возможных решений. (Конечно, вовсе не обязательно, чтобы из каждого набора символ+состояние выходило три альтернативы. Ветвиться дерево может как угодно. Это просто для "быстроты рисования": исходя из удобства Ctrl+С Ctrl+V))). Я нарисовала только первые семь ходов, да и то опустила около половины веток. Представляете, что мы получим для реальной задачи?
Зато если у нас есть путеводная звезда в виде свидетеля или путеводная нить в виде оракула, то пройти по этому лабиринту нам не составит труда. Например, вот так:
Если красная веточка заканчивается за полиномиальное время, а все другие — не обязательно (они могут даже вообще никогда не заканчиваться), то перед нами графическая иллюстрация НМТ для задачи класса NP.
Рассматривая детерминированную машину Тьюринга, мы коснулись и недетерминированной тоже.
Еще раз приведу определение:
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует не более одного правила, и недетерминированной в противном случае.
С тем, что означает "существует не более одного правила", мы разобрались в прошлый раз. А что же значит "в противном случае"?
читать дальшеНапомню принцип действия машины Тьюринга.
Вдоль бесконечной ленты движется каретка, которая называется устройством управления (УУ). Каретка умеет читать символы на ленте и записывать туда другие символы алфавита. УУ может находиться в одном из нескольких состояний, которые описаны заранее. Его (УУ) действие для каждой конкретной ячейки определяются двумя факторами: 1) символом, записанным в эту ячейку, и 2) текущим состоянием.
Так вот, если это самое действие определено однозначно, то такая машина будет детерминированной.
А если нет? Тогда, предположим, что УУ в некотором состоянии перешло в ячейку, в которой оказался некоторый символ. УУ сверяется со своими правилами перехода и видит, что когда оно в данном состоянии встретило данный символ, оно может совершить не четко определенную одну вещь, а сразу несколько разных. И ничто не возбраняет ему (УУ) совершить любую из этих вещей.
Проще говоря, машина оказывается на развилке нескольких дорог, и никто кроме нее не может решить, куда же ей податься. И никто не знает заранее, что же она выберет. Именно поэтому она и называется недетерминированной. Ее поведение становится неопределенным.
И здесь есть несколько интересных моментов, на которые я хотела бы обратить внимание.
1. Как такая машина Тьюринга выбирает, куда ей двинуться на каждой развилке? Ответ на этот вопрос: да никак! Случайным образом. Самое печальное, когда путей у нас много, а правильный из них только один. Но и это печальное не так печально. Сейчас мы с этим разберемся.
2. Про "много путей, из которых правильный только один", я сказала не зря! Для классов задач, решаемых такими машинами (а чуть позже окажется, что недетерминированная машина Тьюринга в частности как раз и решает класс NP) из всех путей по всем развилкам результативным часто оказывается только один.
Если представить это наглядно, то можно вообразить себе детерминированную машину Тьюринга (ДМТ) в виде единственной дорожки, представляющей собой «путь вычислений». Недетерминированная машина Тьюринга (НМТ) в таком случае представляет собой сад расходящихся тропок. Говорят, что она имеет «дерево вычислений». В общем случае у этой машины число путей, по которым может развиваться вычисление, растет экспоненциально.
Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает.
То есть другими словами, если хотя бы один из всех возможных путей приведет к решению задачи, то такая машина пригодна для ее решения. Если же ни один из путей нас не устраивает, то, соответственно, и вся машина нам не подходит.
Говорят еще, что "ДА" и "НЕТ" здесь несимметричны. Думаю, теперь понятно, почему: для "ДА" нам достаточно одного подходящего пути из любого (пусть и очень большого) числа неподходящих; для "НЕТ" нужно, чтобы все пути не подходили одновременно.
3. На вид недетерминированная машина Тьюринга (НМТ) гораздо мощнее, чем детерминированная (ДМТ). И гораздо сложнее. Однако, оказывается, что они эквивалентны! Любую НМТ можно представить в виде ДМТ! Легче лёгкого! Доходя до каждой развилки мы начинаем клонировать машины. То есть недетерминированная машина делится на копии, каждая из которых развивает свою веточку дерева. И так на каждой новой развилке.
Википедия сравнивает этот процесс в многозадачной операционной системой. И в чем-то она права. Разве что вряд ли в операционной системе количество задач растет по экспоненте.
Конечно же, представление НМТ с помощью ДМТ требует значительно больше времени. Насколько больше — неизвестно. И если бы было известно, то задача, которую я и взялась рассматривать: «P = (?) NP» была бы решена!
Класс NP
Вот определение из Википедии:
Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.
Но определение это неполно! Всё так, да не совсем так.
Формальное определение дам в следующий раз. А сейчас просто расскажу, что это такое за класс.
Представьте, что у нас есть недетерминированная машина Тьюринга. Все веточки дерева дают нам 0, то есть не ведут никуда, и только одна дает нам 1, то есть, правильный ответ, — за полиномиальное время. "Полиномиальное время", как мы помним, — это количество шагов, не большее Const*NC, где N — длина входных данных.
Если мы начнем перебирать все цепочки подряд и ходить по всем веточкам, вытягивая их в один линейный и очень длинный путь, мы увязнем, и всё это будет очень долго.
Но представьте, что у нас есть подсказка! На развилке она нам говорит, куда пойти, чтобы сразу добраться до результата!
Мы идем на полиномиальную веточку, которая ведет к ответу, и решаем задачу быстро!
Иногда эту подсказку, как правило, в виде готового решения, которое нужно только проверить, называют свидетелем. Иногда же рассматривают машину Тьюринга с оракулом. То есть, достигая развилки, машина Тьюринга обращается к оракулу — внешнему устройству, выдающему правильные ответы на некоторый круг вопросов.
На практике, однако, поиск свидетелей и построение оракулов — задача не из легких.
Вот, очень простой пример, который можно встретить в литературе в той или иной интерпретации.
Задача. Дано число: 15256677987889881453. Проверить, является оно простым или составным. (Честно скажу, я не проверяла, делится ли сумма цифр на три, не проверяла и другие, менее очевидные признаки делимости, но будем считать, что они не выполняются).
Если мы начнем действовать перебором и подбирать на роль кандидатов в делители все простые числа до квадратного корня из этого числа, мы потратим уйму времени!
Если же мы возьмем себе в помощь "свидетеля": число 123567898761 (которое я специально умножила на другое число, чтобы получить данное), то достаточно просто разделить одно на другое и убедиться, что мы поделили нацело. То есть, со свидетелем эта задача из разряда "нечего делать"; без свидетеля она становится весьма сложной.
Теперь отвлечемся от поиска делителей и/или доказательства простоты. Этот лишь пример, который весьма показателен, но сама задача проверки делится ли число на другое заданное число, конечно, же не относится к классу Р.
А вот если со свидетелем наша задача имеет алгоритмическую сложность Р, то стоит этого свидетеля лишиться, в общем виде получается задача класса NP. Эти задачи легко решить, зная, по какой веточке недетерминированной машины Тьюринга надо пойти, и трудно в противном случае.
На словах это выглядит не слишком убедительно, но давайте посмотрим на картинки.
Вот недетерминированная машина Тьюринга, вернее, конечно, не она сама — она выглядит совсем не так. Это дерево возможных решений. (Конечно, вовсе не обязательно, чтобы из каждого набора символ+состояние выходило три альтернативы. Ветвиться дерево может как угодно. Это просто для "быстроты рисования": исходя из удобства Ctrl+С Ctrl+V))). Я нарисовала только первые семь ходов, да и то опустила около половины веток. Представляете, что мы получим для реальной задачи?
Зато если у нас есть путеводная звезда в виде свидетеля или путеводная нить в виде оракула, то пройти по этому лабиринту нам не составит труда. Например, вот так:
Если красная веточка заканчивается за полиномиальное время, а все другие — не обязательно (они могут даже вообще никогда не заканчиваться), то перед нами графическая иллюстрация НМТ для задачи класса NP.
@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato
-
-
04.07.2008 в 18:45-
-
04.07.2008 в 21:07это спервоначалу!
На самом деле, оказывается, что любая недетерминированная сводится к детерминированной, но очень медленной. А вот человек быстр и всё так же непредсказуем ))))))
-
-
04.07.2008 в 21:20Просто у машины Тьюринга ограниченное число вариантов перебора, а у человека - неограниченное. Или нет?
(а вообще что-то меня на божественное потянуло=) Какие-то аналогии сразу возникли)
-
-
04.07.2008 в 21:22-
-
04.07.2008 в 21:34(а вообще что-то меня на божественное потянуло=) Какие-то аналогии сразу возникли)
И не зря )))
Об этом очень хорошо написано у Пеноруза.
У него толстенная книжка "Тени разума" посвящена как раз этой проблеме. То есть он ставит один единственный вопрос: вычислимо ли сознание. "Вычислимо" в его трактовке означает: "алгоритмизируемо". Т.е. можно ли запрограммировать человеческое мышление любой, сколь угодно сложной, машиной Тьюринга?
Хоть с оракулом, хоть с оракулом в квадрате (это когда первый оракул советуется со вторым), хоть с оракулом в любой степени...
Пенроуз говорит, что нет. Что в сознании существует неалгоритмизируемая составляющая.
И это даже не "свободная воля". Ее он не берет в расчет. Он рассматривает только математическое мышление. Чем пользуется математик при решении задачи.
Ну, он там на теорему Гёделя опирается и всячески противопоставляет Гёделя Тьюрингу...
А ответ, как он предполагает, надо искать на квантовом уровне.
Кстати, непредсказуемость можно интерпретировать как неожиданный выбор веточки (вопреки оракулу или свидетелю)
По идее и оракул и свидетель — это железно! Они говорят, что решение есть, и даже показывают на него пальцем. Это вот если мы не знаем, есть ли решение... Но тогда свидетеля нет, а оракул тоже не в курсе... ))))))
-
-
04.07.2008 в 23:44Вот так живешь-живешь на свете и не знаешь...
А почему ответ надо искать именно на квантовом уровне? (хотелось бы все это получить на уровне математическом)
-
-
04.07.2008 в 23:51там книжка страниц на 500-600 )))
попробую тебе кратко изложить )))) но наверное уже завтра ))
На уровне математическом сознание и мышление не формализуются. В этом-то вся фишка!
-
-
07.07.2008 в 01:16А еще там же на www.infanata.org есть
Пенроуз Новый ум короля: О компьютерах, мышлении и законах физики.Издательство: УРСС
Год: 2003
Страниц:385
Формат: djvu
Размер:4,40 Mb (rar+3%recovery)
Монография известного физика и математика Роджера Пенроуза посвящена изучению проблемы искусственного интеллекта на основе всестороннего анализа достижений современных наук. Возможно ли моделирование разума? Чтобы найти ответ на этот вопрос, Пенроуз обсуждает широчайший круг явлений: алгоритмизацию математического мышления, машины Тьюринга, теорию сложности, теорему Геделя, телепортацию материи, парадоксы квантовой физики, энтропию, рождение Вселенной, черные дыры, строение мозга и многое другое.
СОДЕРЖАНИЕ
Глава 1.Может ли компьютер обладать разумом.
Глава 2.Алгоритмы и машины Тьюринга.
Глава 3.Математика и действительность.
Глава 4.Истина доказательство и интуиция.
Глава 5.Классический мир.
Глава 6.Квантовая магия и квантовое таинство.
Глава 7.Космология и стрела времени.
Глава 8.В поисках квантовой теории гравитации.
Глава 9.Реальный мозг и модели мозга.
Глава 10.Где находится физика ума?
natahaus.ifolder.ru/1971589
-
-
07.07.2008 в 11:04Спасибо)))
У меня она есть твердая )))
По идее в хронологическом порядке надо сначала читать "Новый ум короля", а потом уже "Тени разума".
Но я начала со второй (потому что купила ее первую))), а он там Новый ум короля если не пересказывает весь, то повторяет большими кусками. поэтому мне его было уже не слишком интересно читать. Хотя... Вот сейчас взялась перелистывать — всё же он большой молодец! ))))))
-
-
07.07.2008 в 13:34Кстати, очень рекомендую! Почитай! Я думаю, ты не пожалеешь! И Хофштадтера и Пенроуза! Пенроуз — вообще математик! И это говорит само за себя! )))))
-
-
07.07.2008 в 21:55Почитаю обязательно. Может быть, даже стоит выложить в сообществе ~eek ссылки как на Хофштадтера, так и на Пенроуза.
-
-
07.07.2008 в 22:11ээээ.... погоди, не горячись! Ты сначала сама почитай, прежде чем ссылки выкладывать. Это чтиво (по-моему) довольно специфическое. Я-то читаю, потому что занимаюсь этими вещами. И оно мне нравится, и более того, я всячески рекомендую! Но одно большое "но": это только для своего удовольствия. Образовательной ценности тут очень мало, хотя "познавательная" ценность, конечно, велика!
Хотя... Большинству оно, понятно, не сильно надо, но даже если один-два человека заинтересуются, — будет очень хорошо.
-
-
07.07.2008 в 22:39Слушаю и повинуюсь
Если мне понравится, то выложу с какими-нибудь цитатами. Я думаю, что Ренессансу должно понравиться. Хотя предвижу, что он напишет
-
-
07.07.2008 в 22:46Насчет "должно понравиться" не знаю... А вот что "напишет" — даже и не сомневаюсь )))
(Я тебе письмо послала)