Задача на машину Тьюринга

[Someone]

maxal писал(а):

Someone писал(а):

Но лента с бесконечным количеством записей - это действительно что-то нестандартное.

Пересмотрел в интернете несколько определений МТ - нигде не оговаривается, что входные данные являются конечной последовательностью.

http://www.math.spbu.ru/user/mbk/TUTORY/..%5CPDF%5CCh-6.pdf

Цитата:

Лента имеет крайнюю левую ячейку, но простирается в бесконечность в правую
сторону. Каждая ячейка может содержать ровно один из конечного числа сим-
волов ленты. Первоначально n крайних левых ячеек для некоторого конечного n
содержит входную цепочку, строку символов ленты, называемых входными сим-
волами. Остальные ячейки до бесконечности содержат пробел — специальный
символ ленты, который не является входным символом.

То, что здесь лента односторонняя, конечно, несущественно.

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

[maxal]

Строго говоря, определение МТ вообще не включает, что и как написано на ленте, только оговаривается, что лента содержит символы некоторого алфавита. Тем более ничего не говорится про конечность и/или бесконечность числа "непустых" ячеек, оно может быть любым.

Провел такой эксперимент: ввел в гугле "Turning Machine" и пробежался по первым 5 ссылкам, нигде не сказано про конечность входных данных:

http://en.wikipedia.org/wiki/Turing_machine
The tape is assumed to be arbitrarily extensible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation.

http://plato.stanford.edu/entries/turing-machine/
A Turing machine has an infinite one-dimensional tape divided into cells. ... Each cell is able to contain one symbol, either ‘0’ or ‘1’.
Т.е. здесь вообще не такого понятия как пустой символ.

http://mathworld.wolfram.com/TuringMachine.html
A Turing machine consists of a line of cells known as a "tape" that can be moved back and forth...

http://ironphoenix.org/tril/tm/help/basics.shtml
A Turing Machine is a theoretical computer consisting of a tape of infinite length and a read-write head which can move left and right across the tape.

http://www.mapageweb.umontreal.ca/cousi ... uring.html
a "tape", a ribbon of paper of indefinite length

P.S. И что вы подразумеваете под "конструктивностью"? И чем бесконечный вход мешает ей?

[Сомик]

Дело в том, что определения МТ бывают разные - формальные и неформальные. В неформальных (нематематических) определениях вида "МТ - это головка, бегающая над лентой ..." ничего не говорят о конечности/бесконечности символов на ленте. Но в формальном (алгебраическом) определении через понятие конфигурации МТ конечность необходима.
Да и вобще, МТ возникла всвязи с тезисом Тюринга о том, что любой алгоритм представим на МТ. А любой алгоритм имеет дело с конечными данными.
Так же МТ связаны с частично-рекурсивными функциями, в которых тоже полагается, что число аргументов - конечно.

Но с другой сороны, поведение машины на бесконечном наборе символов тоже интересно! Я честно говоря, таких работ не встречал, но думаю что это может иметь некоторый теоретический смысл, если мы будем предсталять на летне произвольные действиельные числа. А МТ уже будет некоторой фукнцией M: $\mathbb{R} \rightarrow \mathbb{R} $
И ее значением будет то слово к котрому в некотрой метрике стремится слово на ленте во время работы.

Просто такое уже сделано в теории автоматв. Классическая теория автоматов связана с регулярными языками - множеством конечных слов, распознаваемых автоматом (тоерема Клини)
Однако иногда рассматривают бесконечные вправо слова, и тогда возникает похожая теория общерегулярных языков. И там есть аналог теоремы Клини - теорема Мак-Нотона.
Более того, пошли еще дальше, и стали рассматривать двусторонее-бесконечные слова, "укладывающиеся" в автомат. Это,так называемая, символическая динамика. Интересная наука, где автоматы (конечные объекты) порождают континуальные топологические пространства (Shifts of finite type, sofic systrms...). Эти пространства, как правило, имеют фрактальную природу.

Вероятно, подобные вещи можно построить и для МТ, но пока, я такого ,честно говоря, нигде не встречал.

Прошу прощения, что это сообщение не про исходную задачу, но по-моему оно в тему дискуссии =))

[незваный гость]

http://en.wikipedia.org/wiki/Turing_machine писал(а):

Hopcroft and Ullman (1979, p. 148) formally define 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 set of states
* $\Gamma$ is a finite 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$, a subset of $\Gamma$ not including $b$ is the set of input symbols
* $\delta: Q \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.
* $q_0 \in Q$ is the initial state
* $F \subseteq Q$ is the set of final or accepting states

(Хотя Wikipedia не есть источник информации со 100% надежностью, я думаю, в переписывании определения им можно довериться.)

Мне кажется, мы ищем $M= \langle Q, \Gamma=\{b, 1\}, b, \Sigma=\{1\}, \delta, q_0, F \rangle$.

Второй ключевой момент состоит в требовании, что только $b$ повторяется неограниченно. То есть, мы имеем дело с конечным числом $1$ на входной ленте.

Но при этом у нас по-прежнему нет маркера конца входных данных. Поэтому решение Сомика по-прежнему не проходит.

[maxal]

Нашел такое: The aim of our paper is to explore those sets of infinite words accepted by deterministic Turing machines...

Büchi automaton is the extension of a finite state automaton to infinite inputs.

[Сомик]

незваный гость писал(а):

:evil:

Второй ключевой момент состоит в требовании, что только $b$ повторяется неограниченно. То есть, мы имеем дело с конечным числом $1$ на входной ленте.

Ну да. Есть такое понятие - полуразрешимый или представимый язык. Это такой язык $L \subset A^*$, что на для любого слова из этого языка, МТ останавливается в финальном состянии $q_1$, а если слово не пренадлежит языку, то ничего не требуется, тобишь машина может и зависнуть (в отличии от разрешимых языков, когда требуется, чтобы МТ останавливалась и на словах не пренадлежащих языку в некотором состоянии $q_2$)

Так вот, для любого полуразрешимого языка верно, что существует эффективная процедура, которая перечисляет все его слова. И в принципе ясно, что существует алгоритм, который перечисляет все конечные слова нашего вида. Т.е. слова вида $0...01..100..001..10..0$, где есть как минимум две одинаковые по длине последовательности единиц. Проблема в том, что мы должны каждое такое слово вправо и влево дополнить нулями. Раз эта процедура однозначная, то она в некоторм смысле алгоритмически выполнимая, т.е. конечно МТ не сможет дописать за конечное время бесконечное число нулей, но по крайне мере постепенно она будет это делать.

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

[незваный гость]

Сомик писал(а):

Есть такое понятие - полуразрешимый или представимый язык …

Согласен.

Сомик писал(а):

Я это к тому говорю, что всетаки, вся теория МТ основана на работе с конечными словами в том смысле, что мы всегда можем эффективно найти конец слова.

Не знаю, спорить не буду.

По определению МТ мы вроде договорились, хотя, по-видимому, Вы используете нотацию $b = 0$. Осталось договориться о том, что такое слово. Меня устраивает определение слова как конечной поледовательности из $\Sigma \cup \{b\}$. В этом смысле, в начальный момент на ленте находится ровно одно слово, весь остаток ленты заполнен $b$. И все конечно. И мы можем за конечное время написать любое слово. Но, как Вы верно заметили, определить границы слова нельзя.

Мне представляется, что это определение вполне конструктивно. Во многих задачах либо богаче алфавит, либо оговаривается условие конца слова (например, три пробела). В конце концов, это сводится к представлению данных в этом ($\Gamma=\{b, 1\}$) алфавите. Но в даденом нам свыше (от профессора passenger) нет ничего противозаконного.

[Someone]

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

[maxal]

Someone писал(а):

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

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

[Someone]

maxal писал(а):

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

Увеличения числа состояний чего?

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

[незваный гость]

maxal писал(а):

Маркер

Позвольте уточнить — маркеры обработанной части ленты, но не маркеры конца слова.

Но в задаче и не нужен конец слова. МТ должна неостанавливаться, если не найдено повторения.

Кстати, двунаправленность ленты создает еще один ньанс. Мы должны быть аккуратны при поиске слов. Поскольку иначе возможно, что мы уйдем в чисто поле (чистую сторону ленты) за словом, в то время как повтор находится с противоположной стороны. То есть, маркер обработанной части должет содержать единицу (плавно сдвигаемую к бесконечности).

[maxal]

Someone писал(а):

maxal писал(а):

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

Увеличения числа состояний чего?

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

Состояний ТМ, естественно.
Я ничего не предполагаю. Одним пробелом разделяются слова на обработанной (отсортированной) части ленты, т.е. мы сами располагаем их там так, чтобы между ними был ровно один пробел. Начальное же расположение слов на ленте может быть любым.

Добавлено спустя 55 секунд:

незваный гость писал(а):

Кстати, двунаправленность ленты создает еще один ньанс. Мы должны быть аккуратны при поиске слов. Поскольку иначе возможно, что мы уйдем в чисто поле (чистую сторону ленты) за словом, в то время как повтор находится с противоположной стороны. То есть, маркер обработанной части должет содержать единицу (плавно сдвигаемую к бесконечности).

Вы повторяете мои слова: http://dxdy.ru/viewtopic.php?p=42045#42045

[Someone]

maxal писал(а):

Состояний ТМ, естественно.
Я ничего не предполагаю. Одним пробелом разделяются слова на обработанной части ленты, т.е. мы сами располагаем их там так, чтобы между ними был ровно один пробел. Начальное же расположение слов на ленте может быть любым.

А как мы обнаруживаем границы уже обработанной части ленты без маркера?

Добавлено спустя 4 минуты 24 секунды:

Впрочем, кажется, понял.

[maxal]

Someone писал(а):

maxal писал(а):

Состояний ТМ, естественно.
Я ничего не предполагаю. Одним пробелом разделяются слова на обработанной части ленты, т.е. мы сами располагаем их там так, чтобы между ними был ровно один пробел. Начальное же расположение слов на ленте может быть любым.

А как мы обнаруживаем границы уже обработанной части ленты без маркера?

Во-первых, наш маркер - это два нуля (или два пробела, если хотите). Во-вторых, нам нужно лишь конечное число маркеров для работы (а точнее 2 маркера для обозначения начала и конца обработанного участка).
Если они есть на ленте - хорошо, нет - мы их создаем искусственно. См. опять же
http://dxdy.ru/viewtopic.php?p=42045#42045

[незваный гость]

maxal писал(а):

Вы повторяете мои слова: http://dxdy.ru/viewtopic.php?p=42045#42045

Виноват, читал не очень внимательно. Понимал «бежим» по-своему, а не по-Вашему. И «сразу» пропустил.

maxal писал(а):

Во-первых, наш маркер - это два нуля

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