Вопрос про машину Тьюринга

[cscscs]

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) могут и со средой взаимодействовать, а не только в своей конечной памяти колупаться. А среду можно рассматривать как бесконечную ленту с записанным на неё бесконечным объёмом каких-то данных.

[Nemiroff]

cscscs в сообщении #824273 писал(а):

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

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

[cscscs]

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

-- 08.02.2014, 23:48 --

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

[Xaositect]

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

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

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

[Nemiroff]

Ну там как: если машина останавливается, то результат --- это то, что машина написала. Если не останавливается, результата вообще нет.
Соответственно, если машина остановится, то она пройдет конечный участок ленты, а значит это можно считать ответом, а остальное всё равно не нужно.
А если не остановится, то она так и так не остановится.

[svv]

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

[cscscs]

Xaositect в сообщении #824297 писал(а):

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

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

[Xaositect]

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

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

[cscscs]

Xaositect в сообщении #824308 писал(а):

это называется машина с оракулом

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

-- 09.02.2014, 00:20 --

Xaositect в сообщении #824308 писал(а):

Вычислительная сила ее зависит от конкретного оракула.

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

[Nemiroff]

cscscs в сообщении #824303 писал(а):

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

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

[Xaositect]

Цитата:

Xaositect в сообщении #824308 писал(а):

Вычислительная сила ее зависит от конкретного оракула.

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

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

[cscscs]

Xaositect в сообщении #824332 писал(а):

оракул фиксирован

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

[Xaositect]

cscscs в сообщении #824342 писал(а):

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

А как мы будем говорить ему, какую проблему решать? Проблем несчетное число.

[cscscs]

Xaositect в сообщении #824358 писал(а):

А как мы будем говорить ему, какую проблему решать? Проблем несчетное число.

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

[Xaositect]

cscscs в сообщении #824360 писал(а):

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

То есть, точно так же, как в Вашем примере, выписывать все ответы? Тогда естественно можно "вычислить" все, что угодно.