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

[1eonard]

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

[пианист]

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

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

Наверное, стоит уточнить, что Вы называете алгоритмом, исполнимым на машине Тьюринга. Или счетностью; так то оно, вроде бы, счётно.

[1eonard]

пианист в сообщении #1505950 писал(а):

Наверное, стоит уточнить, что Вы называете алгоритмом, исполнимым на машине Тьюринга. Или счетностью

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

пианист в сообщении #1505950 писал(а):

так то оно, вроде бы, счётно.

Разве это так?

[Xaositect]

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

Алгоритм, исполнимый на машине Тьюринга, - это последовательность вида конфигурация-переход-конфигурация-переход-...-конфигурация

Переход здесь любой или только соответствующий программе машины?

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

[1eonard]

Xaositect в сообщении #1505954 писал(а):

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

Алгоритм, исполнимый на машине Тьюринга, - это последовательность вида конфигурация-переход-конфигурация-переход-...-конфигурация

Переход здесь любой или только соответствующий программе машины?

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

Извините, я действительно ошибся.

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

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

[Xaositect]

А как определялась алгоритмическая команда?

[ozheredov]

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

Разве это так?

Так, поскольку элементы бесконечной вниз и вправо матрицы можно перечислить "змейкой"

[1eonard]

ozheredov в сообщении #1505990 писал(а):

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

Разве это так?

Так, поскольку элементы бесконечной вниз и вправо матрицы можно перечислить "змейкой"

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

[svv]

Длина любого алгоритма конечна, и число алгоритмов любой заданной длины $n$ конечно. Поэтому можно перечислить сначала все алгоритмы длины 1, потом все алгоритмы длины 2 и так далее. Любой алгоритм, таким образом, будет перечислен.

[ozheredov]

svv
Алгоритм длины $m$ может выплюнуть результат длины $n$, поэтому наверное ближе к практике (к машине Тьюринга это отношение не имеет) доказать все же перечислимость пар.

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

Не совсем понимаю откуда берется эта аналогия

Забудьте )

[1eonard]

ozheredov в сообщении #1506099 писал(а):

Забудьте )

Забыть ваше сообщение или что?

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

Длина любого алгоритма конечна, и число алгоритмов любой заданной длины $n$ конечно. Поэтому можно перечислить сначала все алгоритмы длины 1, потом все алгоритмы длины 2 и так далее. Любой алгоритм, таким образом, будет перечислен.

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

[Null]

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

Если алфавит счетный, то это уже неверно.

В обычной машине Тьюринга он конечный. Если он бесконечный это надо оговаривать.

[1eonard]

Null в сообщении #1506117 писал(а):

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

Если алфавит счетный, то это уже неверно.

В обычной машине Тьюринга он конечный. Если он бесконечный это надо оговаривать.

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

[Null]

А состояний сколько? Тоже счетное множество? Хотя что для конечного, что для счетного множества состояний будет континуум таблиц перехода.

[1eonard]

Null в сообщении #1506129 писал(а):

А состояний сколько? Тоже счетное множество? Хотя что для конечного, что для счетного множества состояний будет континуум таблиц перехода.

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