2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Вопрос про машину Тьюринга
Сообщение08.02.2014, 21:44 


04/02/14
69
Wikipedia писал(а):
Hopcroft and Ullman (1979, p. 148) formally defined a (one-tape) Turing machine as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where
  • $Q$ is a finite, non-empty set of ''states''
  • $\Gamma$ is a finite, non-empty set of the ''tape alphabet/symbols''
  • $b \in \Gamma$ is the ''blank symbol'' (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of ''input symbols''
  • $q_0 \in Q$ is the ''initial state''
  • $F \subseteq Q$ is the set of ''final'' or ''accepting states''.
  • $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is a partial function called the ''transition function'', where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

Исследовался ли уже вариант машины Тьюринга, когда не только одному пустому символу позволяется "to occur on the tape infinitely often at any step during the computation"?
Мне просто интересно будет ли такая машина эквивалентной обычной машине Тьюринга или это уже будут сверхтьюринговые вычисления?

На этот вопрос меня натолкнула мысль, что ведь агенты (люди, роботы, etc) могут и со средой взаимодействовать, а не только в своей конечной памяти колупаться. А среду можно рассматривать как бесконечную ленту с записанным на неё бесконечным объёмом каких-то данных.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:26 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
cscscs в сообщении #824273 писал(а):
Исследовался ли уже вариант машины Тьюринга, когда не только одному пустому символу позволяется "to occur on the tape infinitely often at any step during the computation"?
Мне просто интересно будет ли такая машина эквивалентной обычной машине Тьюринга или это уже будут сверхтьюринговые вычисления?

Мне кажется, даже машина, на которую позволено в качестве входа подавать вообще любой бесконечный набор данных, она эквивалентна МТ.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:40 


04/02/14
69
Nemiroff
Мне тоже так кажется. Но вдруг не эквивалентна?

-- 08.02.2014, 23:48 --

Все, я думаю, что понял как доказать, что она не эквивалентна МТ. Допустим, что на ленте расположены все значения колмогоровской сложности через один пустой символ. Тогда такая машина может напечатать все значения невычислимой на МТ колмогоровской сложности.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:48 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Чтобы получить результат, машина должна завершить работу за конечное число шагов. За конечное число шагов можно посмотреть только на конечное число клеток, что там дальше - неважно.

-- Сб фев 08, 2014 23:49:15 --

Да, я имею в виду машину, которая реализует частичную функцию, естественно, а не перечисляющую или какую-то еще.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:49 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
Ну там как: если машина останавливается, то результат --- это то, что машина написала. Если не останавливается, результата вообще нет.
Соответственно, если машина остановится, то она пройдет конечный участок ленты, а значит это можно считать ответом, а остальное всё равно не нужно.
А если не остановится, то она так и так не остановится.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:53 
Заслуженный участник


23/07/08
10626
Crna Gora
Вроде читал, что для варианта машины Тьюринга, которая может за один шаг перемножать два вещественных числа, существует алгоритм решения проблемы остановки. Читал давно, могу что-то путать.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 22:58 


04/02/14
69
Xaositect в сообщении #824297 писал(а):
Чтобы получить результат, машина должна завершить работу за конечное число шагов. За конечное число шагов можно посмотреть только на конечное число клеток, что там дальше - неважно.

Пусть $K:A^*\to \mathbb{N}$ - колмогоровская сложность. Допустим, что на ленте расположены все её значения и произвольное слово в алфавите $A$. Тогда эта машина сможет для этого произвольного слова выдать значение колмогоровской сложности за конечное число действий и конечное время.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 23:10 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А, в таком смысле. Я думал, что начальные данные все-таки конечны, и требуется дать ответ независимо от того, что написано на ленте дальше.

То, что у Вас, называется машина с оракулом, обычно, правда, делают отдельную ленту, на которой данные оракула записаны. Вычислительная сила ее зависит от конкретного оракула.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 23:17 


04/02/14
69
Xaositect в сообщении #824308 писал(а):
это называется машина с оракулом

Точно, я почему-то сразу не сообразил. Спасибо.

-- 09.02.2014, 00:20 --

Xaositect в сообщении #824308 писал(а):
Вычислительная сила ее зависит от конкретного оракула.

Потому что невычислимых функций несчетное количество и поэтому их все нельзя расположить на бесконечной ленте?

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 23:27 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
cscscs в сообщении #824303 писал(а):
Тогда эта машина сможет для этого произвольного слова выдать значение колмогоровской сложности за конечное число действий и конечное время.

Это нечестно. :mrgreen: Пусть на ленте записано какое-нибудь невычислимое действительное число. Тогда наша МТ пишет все его знаки.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 23:35 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Цитата:
Xaositect в сообщении #824308 писал(а):
Вычислительная сила ее зависит от конкретного оракула.

Потому что невычислимых функций несчетное количество и поэтому их все нельзя расположить на бесконечной ленте?
Да, там все так же, как в обычном случае - оракул фиксирован, есть всего счетное количество программ, а функций - несчетное.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение08.02.2014, 23:47 


04/02/14
69
Xaositect в сообщении #824332 писал(а):
оракул фиксирован

А если его расфиксировать? :-) Я имею в виду чтобы он вообще все проблемы знал как решать.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение09.02.2014, 00:09 
Заслуженный участник
Аватара пользователя


06/10/08
6422
cscscs в сообщении #824342 писал(а):
А если его расфиксировать? :-) Я имею в виду чтобы он вообще все проблемы знал как решать.
А как мы будем говорить ему, какую проблему решать? Проблем несчетное число.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение09.02.2014, 00:22 


04/02/14
69
Xaositect в сообщении #824358 писал(а):
А как мы будем говорить ему, какую проблему решать? Проблем несчетное число.

Предположим, что мы можем давать ему бесконечный кусок ленты на вход. Т.е. он может прочитать за конечное время указанный нами бесконечный кусок ленты.

 Профиль  
                  
 
 Re: Вопрос про машину Тьюринга
Сообщение09.02.2014, 00:59 
Заслуженный участник
Аватара пользователя


06/10/08
6422
cscscs в сообщении #824360 писал(а):
Предположим, что мы можем давать ему бесконечный кусок ленты на вход. Т.е. он может прочитать за конечное время указанный нами бесконечный кусок ленты.
То есть, точно так же, как в Вашем примере, выписывать все ответы? Тогда естественно можно "вычислить" все, что угодно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group