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

Question

Попытка учиться для финала и настолько запуталась в счетности.

Я понимаю, что любая машина для turing может быть описана как строка. Мы имеем конечное число входов (Σ). Мы можем рассчитать комбинации строк для каждой длины.

Скажем, имеется 256 различных символов ввода.

Для длины строки 1: 256 комбинаций.

Для длины строки 2: у нас есть 256^2 комбинации.

Для длины строки k имеем 256^k комбинаций.

Затем мы подсчитываем все эти комбинации.

1, 2 ... 256, 257, 258 ... 256 + 256^2 ...

Поскольку натуральные числа счетно, есть взаимно однозначное отображение. Таким образом, совокупность всех машин для turing является счетной.

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

Большое спасибо!

Answer 1

Похоже, вы спрашиваете о диагонали Аргумента Кантора. Учитывая набор бесконечных последовательностей, вы можете создать последовательность, которая не входит в набор.

Это очень похоже на аргумент, что вы не можете рассчитывать иррациональные числа. Вы всегда сможете создать число, которое не входит в набор, учитывая, что набор состоит из чисел/строк/и т. Д. которые имеют бесконечную длину.

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