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

[svv]

1eonard в сообщении #1506116 писал(а):

По-моему, число алгоритмов заданной длины конечно только в том случае, если алфавит представляет собой конечное множество. Если алфавит счетный, то это уже неверно.

Тогда так. Если алфавит счётный, можно считать, что его символы перенумерованы.
Этап 1. Перечисляем все алгоритмы длиной не более $1$, в которых используются символы с номерами не больше $1$.
Этап 2. Перечисляем все не перечисленные ранее алгоритмы длиной не более $2$, в которых используются символы с номерами не больше $2$.
Этап 3. Перечисляем все не перечисленные ранее алгоритмы длиной не более $3$, в которых используются символы с номерами не больше $3$.
И т.д.

На каждом этапе перечисляется конечное число алгоритмов. Любой алгоритм $A$ будет перечислен на этапе номер $n$ (= максимальное из двух чисел: длина $A$, максимальный номер символа алфавита, встречающегося в $A$).

[1eonard]

svv в сообщении #1506471 писал(а):

1eonard в сообщении #1506116 писал(а):

По-моему, число алгоритмов заданной длины конечно только в том случае, если алфавит представляет собой конечное множество. Если алфавит счетный, то это уже неверно.

Тогда так. Если алфавит счётный, можно считать, что его символы перенумерованы.
Этап 1. Перечисляем все алгоритмы длиной не более $1$, в которых используются символы с номерами не больше $1$.
Этап 2. Перечисляем все не перечисленные ранее алгоритмы длиной не более $2$, в которых используются символы с номерами не больше $2$.
Этап 3. Перечисляем все не перечисленные ранее алгоритмы длиной не более $3$, в которых используются символы с номерами не больше $3$.
И т.д.

На каждом этапе перечисляется конечное число алгоритмов. Любой алгоритм $A$ будет перечислен на этапе номер $n$ (= максимальное из двух чисел: длина $A$, максимальный номер символа алфавита, встречающегося в $A$).

Огромное Вам спасибо!

[Legioner93]

Таким образом показано, что машина Тьюринга со счётным алфавитом не более выразительна, чем с конечным, а значит не нужна

[arseniiv]

1eonard в сообщении #1506436 писал(а):

Ну да, так как количество состояний равномощно множеству всех подмножеств ленты.

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

[mihaild]

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

[1eonard]

arseniiv в сообщении #1506583 писал(а):

1eonard в сообщении #1506436 писал(а):

Ну да, так как количество состояний равномощно множеству всех подмножеств ленты.

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

Да, Вы абсолютно правы. Из-за этой ошибки у меня и возникло ложное представление о том, что множество всех алгоритмов несчетно.
Спасибо Вам!

mihaild в сообщении #1506585 писал(а):

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

Алфавит бесконечный и таблица переходов бесконечная, но так как алгоритм конечен мы все равно будем использовать только конечное количество переходов из таблицы (это то, о чем сказал arseniiv), а значит то, что количество таких таблиц более чем счетно, не повлияет на мощность множества всех алгоритмов.

[mihaild]

1eonard в сообщении #1506717 писал(а):

Алфавит бесконечный и таблица переходов бесконечная, но так как алгоритм конечен

Что это значит?
Алгоритм - это и есть таблица переходов (ну и еще 4 элемента кортежа, но они неинтересны).

[1eonard]

mihaild в сообщении #1506718 писал(а):

1eonard в сообщении #1506717 писал(а):

Алфавит бесконечный и таблица переходов бесконечная, но так как алгоритм конечен

Что это значит?
Алгоритм - это и есть таблица переходов (ну и еще 4 элемента кортежа, но они неинтересны).

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