Полнота по Тьюрингу

[Sicker]

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

[arseniiv]

Sicker в сообщении #1084635 писал(а):

множеств конечного числа непустых символов на ленте машины Тьюринга

Вы хотели сказать, множеств лент, содержащих конечное число непустых символов?

[slavav]

Да, есть невычислимое отображение конечных лент в конечные ленты - проблема остановки.
Что касается бесконечных лент, то вам надо будет заново определить что такое алгоритм/вычислимая функция. Классическое определение алгоритма требует конечного числа шагов для вычисления результата. За конечное число шагов вы не сможете проанализировать бесконечную ленту и/или напечатать бесконечный результат.