Существует ли биекция между вычислимыми числами и нат.?

[Someone]

juna, Вы действительно верите, что физическую ленту можно неограниченно увеличивать? Вы о физическом мире что-нибудь знаете? Если для изготовления ленты требуемой длины будет нужно больше материала, чем его имеется в наблюдаемой части Вселенной, это Вас не смутит? И то, что этот материал разлетается с ускорением, и, начиная с некоторого момента, количество доступного материала будет уменьшаться?

[juna]

Куда-то Вас в сторону потянуло.
Но тогда поддержу Вас следующим тезисом - а почему Вы думаете, что я смогу придумать физическую задачу с решением, для выражения которого не хватит физического материала

[Someone]

Речь ведь идёт не о физической задаче, а о машине Тьюринга.

А насчёт физической задачи думайте уж сами. Я не знаю, сможете Вы такую задачу придумать или не сможете.

[juna]

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

[Someone]

juna в сообщении #184300 писал(а):

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

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

[juna]

Какой-то странный спор. Я указал на возможность интерпретации потенциально бесконечной памяти у машины Тьюринга. После чего Вы зачем-то аппелировали к физике. Теперь ждете от меня определения "физическая в некотором приближении машина Тьюринга".
Например, этого определения можно достигнуть исходя из того, что машина Тьюринга является распознавателем свободных языков. Свободные языки вполне физически существуют, например, наш русский.
У Вас же под столом стоит, как мне кажется, линейно-ограниченный автомат - распознаватель контекстно-зависимых языков.

[Someone]

juna в сообщении #184307 писал(а):

Какой-то странный спор. Я указал на возможность интерпретации потенциально бесконечной памяти у машины Тьюринга. После чего Вы зачем-то аппелировали к физике.

К физике апеллировал не я.

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

Насколько я понимаю, утверждение о физической реализуемости оракула для задачи останова есть несколько ослабленный вариант тезиса Черча-Тьюринга. А с этим тезисом не все ясно: практически все в него верят, но достаточно полного физического обоснования, вроде бы, нет.

Я на это заметил, что в физическом мире вообще никаких машин Тьюринга нет. Ни с оракулом, ни без оного. Хотя бы потому, что машина Тьюринга требует неограниченно растущего объёма памяти и неограниченного времени для вычислений, что физически не реализуемо. В том реальном мире, в котором мы живём.

[juna]

Someone писал(а):

Вы о физическом мире что-нибудь знаете?

Someone писал(а):

Хотя бы потому, что машина Тьюринга требует неограниченно растущего объёма памяти и неограниченного времени для вычислений, что физически не реализуемо. В том реальном мире, в котором мы живём.

Получается, что Вы знаете о нем все
А как Вы распознаете русский текст?

[Xaositect]

Someone писал(а):

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

Насколько я понимаю, утверждение о физической реализуемости оракула для задачи останова есть несколько ослабленный вариант тезиса Черча-Тьюринга. А с этим тезисом не все ясно: практически все в него верят, но достаточно полного физического обоснования, вроде бы, нет.

Я на это заметил, что в физическом мире вообще никаких машин Тьюринга нет. Ни с оракулом, ни без оного. Хотя бы потому, что машина Тьюринга требует неограниченно растущего объёма памяти и неограниченного времени для вычислений, что физически не реализуемо. В том реальном мире, в котором мы живём.

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

$$\forall X\subset \mathrm{dom} f\ \exists S : \forall x \in X M_S(x) = f(x) $$

,

$$M_S$$

- вычисление с объемом памяти S. Впрочем, не знаю, насколько эта постановка физическая.

[Nxx]

Цитата:

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

Нет. Задача останова нерешаема, а тезис Черча-Тьюринга считается верным (он утверждает, что машина Тьюринга примерно эквивалентна аккуратному математику с карандашом и бумагой).

Добавлено спустя 2 минуты 37 секунд:

Цитата:

Хотя бы потому, что машина Тьюринга требует неограниченно растущего объёма памяти и неограниченного времени для вычислений, что физически не реализуемо.

Неограниченное - не значит бесконечное. Машина, которая требует бесконечной памяти или бесконечного времени, не является машиной Тьюринга.

[epros]

Nxx писал(а):

Речь идет о вычислении с любой заданной точностью.

Что значит "вычислить омегу с любой заданной точностью"? Как вычислить любое конструктивное действительное число (например, пи) с любой заданной точностью - я представляю, как вычислить омегу - нет.

[Nxx]

epros писал(а):

Nxx писал(а):

Речь идет о вычислении с любой заданной точностью.

Что значит "вычислить омегу с любой заданной точностью"? Как вычислить любое конструктивное действительное число (например, пи) с любой заданной точностью - я представляю, как вычислить омегу - нет.

Омегу нельзя вычислить с любой точностью.

[маткиб]

Интересно, а почему форумчане с такой уверенностью высказываются о том, что что-то нельзя сделать в реальном мире?

[Xaositect]

Nxx писал(а):

Цитата:

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

Нет. Задача останова нерешаема, а тезис Черча-Тьюринга считается верным (он утверждает, что машина Тьюринга примерно эквивалентна аккуратному математику с карандашом и бумагой).

Я это и имел в виду. там опечатка, физической нереализуемости.

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

[Nxx]

Цитата:

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

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

Но это опять же никакого отношения к физике не имееет: в физике время испарения ЧД конечно в системе отсчета любого наблюдателя, как падающего, так и находящегося в состоянии покоя.