2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Детерминированные vs недетерминированные машины Тьюринга
Сообщение06.10.2008, 13:13 
Во-первых, не нашел толкового определения недетерминированных машин Тьюринга(НМТ), в том числе и в статье в Wiki. Поэтому сформулирую вопросы, в которых отчаялся разобраться, о вероятностных машинах Тьюринга (ВМТ). Если я что-то упустил, и есть рабочее определение НМТ, прошу указать на него, дать ссылку или, если не затруднит, привести.

1. Верно ли, что существует такая ВМТ, которая не может быть в принципе симулирована с помощью ДМТ?
2. Верно ли, что существует такая ВМТ, которая не может быть эффективно симулирована с помощью ДМТ?
3. Почему отрицательный ответ на второй вопрос не может быть доказательством неравенства классов сложности P и NP?

 
 
 
 
Сообщение06.10.2008, 13:54 
Аватара пользователя
Вроде у Шеня это есть. Я точно ссылку сейчас не вспомню, поищите сами.

 
 
 
 
Сообщение07.10.2008, 04:02 
Профессор Снэйп писал(а):
Вроде у Шеня это есть. Я точно ссылку сейчас не вспомню, поищите сами.


Спасибо, посмотрел, врать не стану - ясности не особо прибавилось. Конечно, уже легче, но все же... Все равно, как и везде огульные рассуждения о том, что ДМТ может симулировать ВМТ, пусть это и будет задача экспоненциальной сложности. А если вероятности переходов в ВМТ иррациональные, тогда что? Или иррациональные вероятности в принципе не могут возникнуть при построении алгоритмов для ВМТ? А почему так? Сумбур какой-то...:(

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group