Требование конечности исходных данных для машины Тьюринга

[Munin]

Профессор Снэйп
Получается, у вас вычислимость с остановом не совпадают?

[Профессор Снэйп]

На $\omega$-слова даже конечные автоматы напускают, не то что машины Тьюринга

-- Вт сен 04, 2012 02:05:26 --

Munin в сообщении #614471 писал(а):

Профессор Снэйп
Получается, у вас вычислимость с остановом не совпадают?

Нет, конечно! Какой уж тут останов, если надо бесконечное слово целиком просмотреть

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

-- Вт сен 04, 2012 02:12:24 --

longstreet в сообщении #614451 писал(а):

Странно. Это же важный поинт. Почему тогда не удаётся найти его в явной форме?

Ну а насколько он действительно "важен"? Учебник, где это бы рассматривалось, мне ни разу не встречался. А статей в MathReview - вагон и маленькая тележка! Я никогда этими темами профессионально не занимался, так что лучшие тексты с наиболее простым изложением выбрать не могу. Но как-нибудь могу поспрашивать на работе насчёт хорошей литературы.

[bin]

Предложу такую задачу.
Дано: бесконечная лента с числами.
Найти: 10 чисел "2012", остановиться и вывести кол-во чисел, которые пришлось прочитать. М.б. останов будет на десятом числе, а м.б. его вообще не будет - мы не знаем какие даны числа на ленте (может там одни единицы - бесконечно много единиц)

[Профессор Снэйп]

bin в сообщении #614486 писал(а):

Предложу такую задачу.
Дано: бесконечная лента с числами.
Найти: 10 чисел "2012", остановиться и вывести кол-во чисел, которые пришлось прочитать. М.б. останов будет на десятом числе, а м.б. его вообще не будет - мы не знаем какие даны числа на ленте (может там одни единицы - бесконечно много единиц)

А в чём проблема-то? Движемся вправо, пока не встретим 10 вхождений "2012", если встретим - ставим маркер и поддсчитываем количество ячеек слева от маркера. Записываем результат и останавливаемся.

-- Вт сен 04, 2012 02:44:06 --

Вот, похоже, нормальная статья. Судя по абстракту - то, что надо. К сожалению, доступа к тексту у меня из дома нет, надо в институт ехать

[_hum_]

Профессор Снэйп в сообщении #614469 писал(а):

А насчёт методичек для первокурсников... Знаете ли, в школьных учебниках, например, пишут, что числа можно возводить только в натуральную степень. Потом, по мере углубления в анализ, начинают возводить числа в действительные и даже в комплексные степени... И что теперь? Если не получается осилить комплексный анализ и аналитические продолжения функций, тыкать пальцем в школьный учебник и заявлять, что числа только в натуральную степень возводятся? Как-то это несерьёзно

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

Зачем же глумиться над теми, кто в такие дебри вычислимости не влазил, а знает ее не более рамок университетских курсов? Тем более раздел форума называется не "Дискуссионные проблемы", а "Помогите решить/разобраться".

И, получается, что все же это (МТ на $\omega$-последовательностях) не классическое (университетское) определение модели вычислений по Тьюрингу, о чем я все пытался толковать.

[bin]

Профессор Снэйп в сообщении #614488 писал(а):

bin в сообщении #614486 писал(а):

Предложу такую задачу.
Дано: бесконечная лента с числами.
Найти: 10 чисел "2012", остановиться и вывести кол-во чисел, которые пришлось прочитать. М.б. останов будет на десятом числе, а м.б. его вообще не будет - мы не знаем какие даны числа на ленте (может там одни единицы - бесконечно много единиц)

А в чём проблема-то? Движемся вправо, пока не встретим 10 вхождений "2012", если встретим - ставим маркер и поддсчитываем количество ячеек слева от маркера. Записываем результат и останавливаемся.

-- Вт сен 04, 2012 02:44:06 --

Вот, похоже, нормальная статья. Судя по абстракту - то, что надо. К сожалению, доступа к тексту у меня из дома нет, надо в институт ехать

Ok! Просто ранее было сказано:

Профессор Снэйп в сообщении #614472 писал(а):

Нет, конечно! Какой уж тут останов, если надо бесконечное слово целиком просмотреть

Я и предложил задачу, в которой при бесконечной ленте м.б. останов и очень скорый (Про "бесконечное слово" в стартовом посте не говорилось!)

-- Вт сен 04, 2012 00:31:46 --

PS Я бы не ставил маркер, а подсчитывал слова сразу (все равно потом подсчитывать), с маркером две почти-бесконечности вместо одной, теоретиков, понятно, это не трогает, и я пошутил

-- Вт сен 04, 2012 00:38:41 --

_hum_ в сообщении #614504 писал(а):

Ну, так почему с самого начала не сказать, мол, дети, вы просто еще не знаете [...] Если будут вопросы, спрашивайте.

Так вот и спрашиваем убогие, а "небожители" нам не отвечают (только ругаются)

[longstreet]

(Оффтоп)

Профессор Снэйп в сообщении #614488 писал(а):

Вот, похоже, нормальная статья. Судя по абстракту - то, что надо. К сожалению, доступа к тексту у меня из дома нет, надо в институт ехать

А почему не юзаете http://sci-hub.org/ ?

[Профессор Снэйп]

bin в сообщении #614507 писал(а):

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

Предложили бы уж тогда вычислить тождественную функцию $f(w) = w$ или контанту $f(w) = 0$

А вообще то, на что Вы намекали - это, в точности, класс функций, вычислимых с оракулом. На ленту (оракульную) подаём произвольную бесконечную запись, машина воспринимает всю эту ленту целиком как аргумент, что-то считает и если значение функции (являющееся числом) определено, то останавливается через конечное число шагов, выдавая это число на рабочей ленте, а если не определено, то работает бесконечно. Это то, что называют тьюринговым функционалом из $\Sigma^\omega$ в $\mathbb{N}$; номер программы равен номеру функционала Вещь суперпупермегаизвестная

Я думал, Вас интересуют вычислимые на МТ функции не только с бесконечными входами, но и с бесконечными выходами...

-- Вт сен 04, 2012 04:44:00 --

longstreet в сообщении #614512 писал(а):

А почему не юзаете http://sci-hub.org/ ?

Так всё равно за нужную статью денежку придётся платить. Разве нет?

[longstreet]

(Оффтоп)

Профессор Снэйп в сообщении #614535 писал(а):

Так всё равно за нужную статью денежку придётся платить. Разве нет?

Нет. Там всё бесплатно (это пиратский ресурс ), насколько я понимаю они перенаправляют запрос на машину с доступом. Почти-почти все статьи оттуда можно скачать. В том числе указанную Вами.
Открываете http://sci-hub.org/, вставляете в единственную строку адрес статьи в научном журнале, и открываете. Если не открылась статья с первого раза $-$ жмёте "Поменять прокси" и пытаетесь второй раз. Открывается статья, нажимаете дискетку и грузите её себе.

[bin]

Профессор Снэйп в сообщении #614535 писал(а):

Я думал, Вас интересуют вычислимые на МТ функции не только с бесконечными входами, но и с бесконечными выходами...

А чего интересного в бесконечном выходе? Набрать в гугле любой запрос - для человека выход будет почти бесконечен - хорошо если на первые 10 страниц хватит

[Профессор Снэйп]

bin в сообщении #614538 писал(а):

А чего интересного в бесконечном выходе?

Тогда обычный тьюрингов функционал Берём машину с оракулом и воспринимаем оракул как переменную (для множества или функции).

А вообще вот в Вики целая статья нашлась

[bin]

Профессор Снэйп в сообщении #614544 писал(а):

А вообще вот в Вики целая статья нашлась

Да, иногда и в Вики интересное можно найти

[epros]

Munin в сообщении #614471 писал(а):

Профессор Снэйп
Получается, у вас вычислимость с остановом не совпадают?

Смотреть «частично рекурсивная функция». Кто вообще сказал, что МТ обязана останавливаться? «Не остановится» — это тоже результат вычислений.

-- Вт сен 04, 2012 10:13:57 --

_hum_ в сообщении #614504 писал(а):

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

Это не расширение, а всё то же стандартное понятие вычислимости. Расширение — это когда оракулы добавляются. Но и без оракулов МТ либо остановится (через конечное количество шагов, а значит обработав только конечное подмножество данных), либо не остановится. Что бы там ни было изначально на той части ленты, куда головка добраться не успела, это ничего существенно не изменит.

Профессор Снэйп здесь где-то хорошо сказал про «ходит на двух ногах».

[Профессор Снэйп]

epros в сообщении #614575 писал(а):

Смотреть «частично рекурсивная функция». Кто вообще сказал, что МТ обязана останавливаться? «Не остановится» — это тоже результат вычислений.

Ну не придирайтесь уж. Понятно, что Munin имел в виду определённый результат вычислений

Кстати, Munin, вот совсем простое упражнение:

Показать, что $\varphi(x)$ вычислима на МТ с оракулом для проблемы остановки тогда и только тогда, когда найдётся работающая без всяких оракулов МТ, генерирующая в ответ на вход $x$ бесконечную последовательность $y_0(x), y_1(x), \ldots$ со свойством $\varphi(x) = \lim_{t \to \infty} y_t(x)$.

Короче, вычислимость с оракулом проблемы остановки равносильна тому, что по входным данным можно без всяких оракулов сгенерировать бесконечную последовательность "аппроксимаций" результата, причём если результат определён, то начиная с некоторого момента эти аппроксимации будут точны. Ну а если не определён, аппроксимации меняются бесконечно часто и их предела не существует.

-- Вт сен 04, 2012 12:29:27 --

bin в сообщении #614507 писал(а):

Я бы не ставил маркер, а подсчитывал слова сразу (все равно потом подсчитывать), с маркером две почти-бесконечности вместо одной

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

[epros]

Профессор Снэйп в сообщении #614584 писал(а):

Ну не придирайтесь уж. Понятно, что Munin имел в виду определённый результат вычислений

Хорошо, больше не буду. Но Вы, по-моему, тоже зря сейчас задачки с оракулами задаете. Народ тут никак с МТ без оракулов разобраться не может.