Антимашина Тьюринга

[semikolenov]

Гипотеза Тьюринга говорит, что вычислить можно всё имея бесконечную длину ленты.
Однако про функции анализа умалчивается: скорее всего предполагается , что машина имеет конечное их число.

Теоретически можно предположить: имея конечную длину ленты и бесконечное число функций выполнения программы - задача так же может быть исчисляемой?

[dgwuqtj]

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

[semikolenov]

Согласен: парадокс.

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

При этом заменив бесконечную ленту и конечные функции, на бесконечные функции и конечную ленту.

Вещественные числа можно формализовать до конечного представления
(например, бесконечное непериодическое вещественное число
1,41421356237... до конечного $\sqrt{2}$ )

( Как мы будем прописывать $\sqrt{2}$ на ленте: это уже другая область ).

Ранг сложности "решаемость" задачи при этом не изменится.

Однако, появляется дополнительный путь в решении.

[Sender]

Если у вас есть бесконечное число состояний, можно и вовсе без ленты обойтись.

[semikolenov]

Sender в сообщении #1675854 писал(а):

Если у вас есть бесконечное число состояний, можно и вовсе без ленты обойтись.

Согласен.
Это в пределе: один операнд и бесконечная длина функции.

[dgwuqtj]

Можете глянуть на машины Тьюринга типа 2.

[semikolenov]

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