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

[_hum_]

Всю жизнь считал, что формализация алгоритма с помощью машины Тьюринга (МТ) предполагает конечность исходных данных (конечность последовательностей символов (отличных от пробела), помещаемых на ленту перед запуском).
Обоснование естественное: МТ есть формализация алгоритма. Алгоритм работает только с конструктивными объектами в качестве исходных данных. Конструктивные объекты - суть те объекты, которые можно эффективно представить в виде конечной цепочки символов из конченого алфавита. Значит, МТ должна работать только с конечными цепочками символов из конечного алфавита.
Подтверждение этому нахожу и в википедии:
wiki/Turing_machine

Цитата:

The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on.

И просто по ссылкам в гугле, например, тут 1 Definition of a Turing machine
И даже в том же Роджерсе в параграфе 1.5 Формализация, п. Формализация Тьюринга тоже нахожу, что вначале на ленту помещается конечное число единиц (унарная запись натурального числа).


Но Профессор Снэйп ставит под сомнение мое представление о МТ. Авторитетов в науке меня учили не признавать (или, по крайней мере, одинаково критически относиться к их словам), так что прошу помочь остальных внести ясность в этот вопрос.

[epros]

_hum_Эта тема — беспредметна. Вам ранее уже объяснили две вещи:
1) Никакие реальные компьютеры не имеют дел с бесконечными потоками входных и выходных данных.
2) А вот для МТ как раз безразлично, конечны её «входные и выходные потоки данных» или нет.

Тем не менее, Вы почему-то продолжаете упорно путать (1) и (2).

[_hum_]

Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Ч. 3. Вычислимые функции.
Раздел 9.2 Машина Тьюринга: определение

Цитата:

Остается договориться, как мы подаем информацию на вход машины, и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь вправо (пока не появится символ, отличный от 0 и 1).

И это цитата из учебника, который является "книгой, написанной по материалам лекций и семинаров, проводившихся авторами для младших курсов мехмата МГУ".
Поэтому, Профессор Снэйп, прошу подтвердить ссылкой правоту ваших слов относительно возможности бесконечных данных для обычной ("классической", "той, что изучают в университетах в стандартных курсах теории алгоритмов", безо всяких обобщений) МТ, либо придется считать, что все-таки вы погорячились.

[epros]

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

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

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

_hum_, я начинаю сомневаться в Вашей вменяемости.

А я уже давно диагноз поставил

[_hum_]

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

Вам ранее уже объяснили две вещи:
1) Никакие реальные компьютеры не имеют дел с бесконечными потоками входных и выходных данных.

Вы невнимательно читаете. Как раз-таки подтвердилось (по крайней мере никто обоснованно не смог опровергнуть), что реальные компьютеры могут работать с бесконечными потоками данных.

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

А вот для МТ как раз безразлично, конечны её «входные и выходные потоки данных» или нет.

Для самой машины - да, а для формального понятия вычислимости по Тьюрингу - принципиально.

[longstreet]

Профессор Снэйп, ну серьёзно. Это же не должно быть сложно $-$ приведите, пожалуйста, ссылку на материал, в котором говориться о том, что машина Тьюринга может иметь дело с бесконечными потоками.

(я ни разу не специалист в этом, но интересно)

[_hum_]

Профессор Снэйп, очень красиво с вашей стороны. Смеяться и "ставить диагнозы тем", кто хочет в теме разобраться. Хотя, похоже, вы тут исключительно для того, чтобы потешить свое самолюбие.

[epros]

(Оффтоп)

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

Профессор Снэйп, очень красиво с вашей стороны. Смеяться и "ставить диагнозы тем", кто хочет в теме разобраться. Хотя, похоже, вы тут исключительно для того, чтобы потешить свое самолюбие.

Да бросьте, ни в чём Вы не хотите разобраться. Вам давно всё объяснили, и не раз, а Вы упорно повторяете одну и ту же чушь.

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

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

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

post42519.html#p42519

[longstreet]

По ссылке косвенное указание (а именно: в первых пяти ссылках гугла упоминания о необходимости конечности нет).
А хотелось бы, чтобы прямо было в тексте сказано.

-- 03.09.2012, 22:35 --

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

[_hum_]

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

_hum_, я начинаю сомневаться в Вашей вменяемости.

Последняя попытка объяснить вам проблему.
Вы путаете механическую машину (ленту с головкой, бегающей по ней в соответствие с определенными правилами), и модель вычислений по Тьюрингу - МТ как формальное определение алгоритма. А последнее, помимо механической машины, предполагает еще и схему работы с этой машиной, а именно,
1) что подается в качестве исходных данных алгоритма (и каким образом),
2) что является промежуточными результатами, и
3) что является конечным результатом алгоритма (как он извлекается).

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

Ваше "ну какая разница- ну запустите машину на ленте, на которой изначально записана не конечная, а бесконечная последовательность, и будет вам счастье", конечно, имеет право на жизнь. Но! Замечу - это уже не классическая (та, что в универе проходят) модель вычислений по Тьюрингу.
Чтобы более наглядно это продемонстрировать, можно указать, что такой модели будут соответствовать уже не только рекурсивные функции на $\mathbb{N}^*$, а некие функции на $\mathbb{N}^*\cup \mathbb{N}^\infty$, определение которых приводилось мною ранее в выдержке из статьи Успенского.

-- Пн сен 03, 2012 23:46:12 --

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

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

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

post42519.html#p42519

сообщение #42517

[epros]

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

Но модель вычислений по Тьюрингу - еще как зависит.

Нет, не зависит. Моя «последняя попытка объяснить» уже была, большое повторяться не вижу смысла.

P.S. То, что в реальности якобы бывают бесконечные потоки данных, это вообще феерический бред.

[_hum_]

epros

(Оффтоп)

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

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

Но модель вычислений по Тьюрингу - еще как зависит.

Нет, не зависит. Моя «последняя попытка объяснить» уже была, большое повторяться не вижу смысла.

P.S. То, что в реальности якобы бывают бесконечные потоки данных, это вообще феерический бред.

Ок. Ваша позиция понятна, и по возможности бесконечных потоков в том числе. Спасибо.

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

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

А хотелось бы, чтобы прямо было в тексте сказано.

http://www.google.ru/search?sourceid=na ... 20&bih=854

Дальше кликайте сами. Там страниц 10, серьёзные публикации начинаются где-то с 1970 года...

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

Ясно, что ленту машины можно заполнить произвольной последовательностью символов, в частности, и такой последовательностью, в которой бесконечное число символов, отличных от символа пустой ячейки. И потом напустить на эту ленту машину. И она будет по ней ползать и что-то делать. Дальше уже давайте определения сами. Например, такое определение возможно: функция $f$ из $\Sigma^\omega$ в $\Sigma^\omega$ вычислима на МТ, если существует программа, которая преобразует ленту с произвольным входом $w$ и для любой позиции $i$ ленты существует шаг программы, после которого символ в этой позиции становится равным $(f(w))_i$ и в дальнейшем не меняется. Можно и другие определения придумывать...

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