2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Антимашина Тьюринга
Сообщение21.02.2025, 17:49 
Аватара пользователя
Согласен: парадокс.

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

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

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

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

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

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

 
 
 
 Re: Антимашина Тьюринга
Сообщение21.02.2025, 17:50 
Если у вас есть бесконечное число состояний, можно и вовсе без ленты обойтись.

 
 
 
 Re: Антимашина Тьюринга
Сообщение21.02.2025, 17:55 
Аватара пользователя
Sender в сообщении #1675854 писал(а):
Если у вас есть бесконечное число состояний, можно и вовсе без ленты обойтись.

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

 
 
 
 Re: Антимашина Тьюринга
Сообщение21.02.2025, 18:01 
Можете глянуть на машины Тьюринга типа 2.

 
 
 
 Re: Антимашина Тьюринга
Сообщение21.02.2025, 18:08 
Аватара пользователя
Аналогия : память в компах может так работать - записывать данные по одному каналу, считывать по другому.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group