Недоказуемое

[manul91]

mihaild в сообщении #1568115 писал(а):

manul91, физически такое устройство нереализуемо, т.к. у любого конечного физического устройства конечный объем памяти

Так и у этого устройства конечный объем памяти (хотя и неограниченный). Если вы имели ввиду "у любого конечного физического устройства ограниченный объем памяти", то тогда и машину Тьюринга - в топку. Стандартное понятие "вычислимости" (обычной алгоритмической) имеет ясную дефиницию, и оно "позволяет" неограниченного объема памяти (хотя и конечного). Точно также, для выдачи результата м. Тьюринга разрешается любое конечное время (хотя и никакой ограниченый срок/лимит во времени не ставится)

mihaild в сообщении #1568115 писал(а):

атематически же вообще нет никакой "внешней памяти"

Ну считайте ее "внутренней", также как вам нравится считать и у машины Тьюринга

Но ладно, пусть я переборщил с наглядности "железки"; сформулируем это так:
М.Тьюринга плюс квантовая монетка (а вот она вполне конечный физический девайс) - может что-то, что не может "голая" машина Тьюринга - а именно, выдавать невычислимую последовательность.
"Голая" машина Тьюринга, может выдавать только вычислимую : )

mihaild в сообщении #1568115 писал(а):

алгоритм должен каждый раз выдавать один и тот же результат

Он и выдает каждый раз один и тот же результат (если вход один и тот же, разумеется).

[mihaild]

manul91 в сообщении #1568130 писал(а):

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

Так да, МТ на физическом устройстве конечного размера нереализуема, тезис Чёрча только в другую сторону работает.

manul91 в сообщении #1568130 писал(а):

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

Только квантовость монетки (всякие суперпозиции) не нужна, достаточно просто источника случайности.

manul91 в сообщении #1568130 писал(а):

Он и выдает каждый раз один и тот же результат (если вход один и тот же, разумеется).

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

[manul91]

mihaild в сообщении #1568179 писал(а):

Только квантовость монетки (всякие суперпозиции) не нужна, достаточно просто источника случайности.

А кто говорит что здесь суперпозиции должны быть нужными?
А других источников случайности (разумеется истинной) кроме квантовых не известно.

mihaild в сообщении #1568179 писал(а):

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

А то что я описал, не так работает. Она не тупо "копирует" значения которые выдает квантовая монетка. Прочтите описание как она работает еще раз: по запросу номера разряда, выдает значение любого разряда. Если запросить один и тот же разряд, она всегда выдаст то же самое значение, т.к. хранит уже выданные значения в памяти (как конкретно они там записаны, на самом деле не важно).

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

П.П. То, что мы не можем "повторить" такой девайс по заказу (чтобы он выдавал ту же последовательность) - т.е. о полном "отсутствии контроля" - я отметил уже в первом сообщении.
Но это не отменяет тот факт, что М.Тьюринга плюс квантовая монетка (а вот она вполне конечный физический девайс) - все-таки может что-то, что не может "голая" машина Тьюринга - а именно, выдавать невычислимую последовательность (описанным образом). "Голая" машина Тьюринга может выдавать только вычислимую : )

[Skipper]

mihaild в сообщении #1567923 писал(а):

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

И какова считается, мощность множества останавливающихся + неостанавливающихся программ?

[mihaild]

manul91 в сообщении #1568185 писал(а):

А других источников случайности (разумеется истинной) кроме квантовых не известно.

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

manul91 в сообщении #1568185 писал(а):

Если запросить один и тот же разряд, она всегда выдаст то же самое значение, т.к. хранит уже выданные значения в памяти (как конкретно они там записаны, на самом деле не важно).

Это у вас еще какая-то очень странная модель, в которой между запросами сохраняется состояние.

Skipper в сообщении #1568186 писал(а):

И какова считается, мощность множества останавливающихся + неостанавливающихся программ?

Счетная, конечно. Конструктивная мощность классического подмножества может быть меньше конструктивной мощности всего множества.

[manul91]

mihaild в сообщении #1568191 писал(а):

Вы тут смешиваете реальные устройства и модели вычисления.
В реальных устройствах память ограничена.

mihaild в сообщении #1568191 писал(а):

Это у вас еще какая-то очень странная модель, в которой между запросами сохраняется состояние.

mihaild, в последний раз:
Я определяю интерфейс к чему-то, назовем его гипотетической "Штукенции X":
- На вход оно принимает только натуральные числа (и ничего больше)
- Для каждого натурального числа на входе, оно за конечное (но неограниченное) время должно выдать соответное значение, 0 или 1
- Оно персистентно в смысле что если подать то же самое число на входе, должно выдавать то же самое значение на выходе
- Бесконечная последовательность соответствующая данному однозначному отображению "нат. номер -> значение", - невычислима.

Никакие другие требования и ограничения (типа ограниченность памяти, ограниченность времени работы, возможность пересоздать копию этой штукенции по желанию и т.д.) на "Штукенции Х" не ставятся.
И да, это я определяю "требования и ограничения", ибо я и дефинирую "штукенцию Х".
И вот теперь я говорю: такую "штукенцию Х" (с таким интерфейсом) одной только обычной м. Тьюринга реализовать нельзя. А через м. Тьюринга плюс квантового источника - вполне даже можно.
С чем тут спорить-то?

Да, если выдумать дополнительные требования типа ограниченность памяти до 10 мегабайт, ограниченность времени работы до 10 минут на запрос, требования возможности пересоздания по желанию такой же штуки генерящей такой же последовательности и пр. - конечно сделают мое утверждение неверным. Но ведь мое утверждение относится не к некоей "штукенции Z" с этими требованиями, а именно к "штукенции Х" описанной выше у которой таких требований нет.
С другой стороны, можно требовать например возможность разложения на простые множители за полиномиальное время - и тогда опять м. Тьюринга не справится, а с квантам - справится (и суперпозиция тоже влезет в дело - будет необходима - как вам почему-то хочется). Но речь ведь не об этом, а про "штукенции Х" выше.

mihaild в сообщении #1568191 писал(а):

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

Наверно тут терминологическая путаница. Что вы называете "классической случайностью"? Для меня "классически" означает "по законам классической физики", без учета квантовой механики. Законы классической физики на фундаментальном уровне детерминированы - поэтому никакой случайности через них не получить (только "псевдослучайность", типа генераторов псевдослучайных чисел в компе у которого нет аппаратного генератора сл.чисел на базе квантовых шумов). Единственный реальный известный источник "истинной случайности" в нашем мире - это кванты.
А что дает истинная (квантовая) случайность - в частности, она дает возможность существования "штукенции Х" описанной выше, которая представляет какую-то определенную невычислимую последовательность.
Насколько такие невычислимые последовательности "полезны" в жизни - это совершенно другой вопрос... : )

[mihaild]

manul91 в сообщении #1568196 писал(а):

Я определяю интерфейс к чему-то, назовем его гипотетической "Штукенции X":

Это физическое устройство (возможно сложно реализуемое, типа размером в миллиард световых лет, но не противоречащее законам физики), или математическая модель?

manul91 в сообщении #1568196 писал(а):

Что вы называете "классической случайностью"? Для меня "классически" означает "по законам классической физики", без учета квантовой механики.

Тут я говорю про мат. модель. Есть модель вычислений со случайностью, когда к стандартным операциям добавляется "бросить монетку" (или, что эквивалентно, когда МТ подается на вход случайная последовательность). Но т.к. теперь выход МТ зависит не только от аргумента, но и от этого дополнительного входа, нужно уточнять, что вообще значит "МТ со случайностью что-то вычисляет".
Есть квантовая МТ, в которой (примерно) у МТ есть дополнительные операции вида "применить такой-то оператор к вектору в пространстве состояний" (и считается, что пространство состояний имеет экспоненциальную размерность, но применение некоторых конкретных операторов занимает полиномиальное время) и "померять этот вектор с его изменением по правилу Борна" [на самом деле там есть еще суперпозиция состояний МТ, а то что я сказал ближе к квантовым схемам, но это в данном контексте ни на что не влияет].
Очевидно, что МТ со случайностью эмулируется на квантовой с не более чем полиномиальным замедлением. Квантовая МТ эмулируется на МТ со случайностью с не более чем экспоненциальным замедлением (просто честно следим за вектором, при измерениях считаем распределение и бросаем монетку для сэпмлирования из него).

[manul91]

mihaild в сообщении #1568197 писал(а):

Это физическое устройство (возможно сложно реализуемое, типа размером в миллиард световых лет, но не противоречащее законам физики), или математическая модель?

Хороший вопрос : ) Из-за неограниченности памяти и времени, кажется зависит от того, бесконечна ли вселенная или нет....: ) По-вашему стандартная машина Тьюринга - это "математическая" модель, или "физическая" - и почему?

mihaild в сообщении #1568197 писал(а):

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

Да, я понял. Дело однако как раз в том, что вполне физически, "присовокупив" источник квантовой (истинной) случайности к м.Тьюринга (чей "физический" или "математический" статус пока неуточнен) - нам ненужен никакой "дополнительный вход".
Природа обеспечила нам источник истинной случайности - вполне физически конечный - и существующий реально, без никаких абстракций - им можно воспользоваться.
Это вам на "голой" машине Тьюринга нужен бесконечный дополнительный вход, чтобы интерфейса "штукенции Х" воспроизвести (и тогда, строго говоря - это уже не машина Тьюринга)! А на м. Тьюринга (стандартной!) с присобаченным аппаратным источником истинной случайности, никакой дополнительный вход ненужен (чтобы воспроизвести интерфейса "штукенции Х").

[пианист]

manul91
Но Вы, конечно, в курсе, что на НМТ ничего сверх того, что вычисляется на МТ, не вычисляется?

[manul91]

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

manul91Но Вы, конечно, в курсе, что на НМТ ничего сверх того, что вычисляется на МТ, не вычисляется?

Разумеется (что относится до стандартного определения что есть "вычисление").

[mihaild]

manul91 в сообщении #1568200 писал(а):

По-вашему стандартная машина Тьюринга - это "математическая" модель, или "физическая" - и почему?

Математическая. Потому что вроде как физическое её построение противоречит законам физики.

manul91 в сообщении #1568200 писал(а):

Дело однако как раз в том, что вполне физически, "присовокупив" источник квантовой (истинной) случайности к м.Тьюринга (чей "физический" или "математический" статус пока неуточнен) - нам ненужен никакой "дополнительный вход".

Я не знаю, как присоединять физические штуки к математическим моделям.

manul91 в сообщении #1568200 писал(а):

А на м. Тьюринга (стандартной!) с присобаченным аппаратным источником истинной случайности, никакой дополнительный вход ненужен (чтобы воспроизвести интерфейса "штукенции Х").

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

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

Но Вы, конечно, в курсе, что на НМТ ничего сверх того, что вычисляется на МТ, не вычисляется?

Тут речь о рандомизированных, а не недетерменированных МТ.

[manul91]

mihaild в сообщении #1568205 писал(а):

Потому что вроде как физическое её построение противоречит законам физики.

Что значит "вроде как"? Противоречит или не противоречит?.. И в чем именно, и почему?

mihaild в сообщении #1568205 писал(а):

Я не знаю, как присоединять физические штуки к математическим моделям.

Если затруднение только в этом - все просто, делаете "математическую модель" физической штуки, и присоединяете математичесую модель к математической модели - так подойдет? Как это делается например для модели квантовых машин тьюринга.

mihaild в сообщении #1568205 писал(а):

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

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

[mihaild]

Но вы противопоставляли дополнительный вход "стандартной МТ с присобаченным источником истинной случайности".

manul91 в сообщении #1568200 писал(а):

Это вам на "голой" машине Тьюринга нужен бесконечный дополнительный вход, чтобы интерфейса "штукенции Х" воспроизвести (и тогда, строго говоря - это уже не машина Тьюринга)! А на м. Тьюринга (стандартной!) с присобаченным аппаратным источником истинной случайности, никакой дополнительный вход ненужен (чтобы воспроизвести интерфейса "штукенции Х").

manul91 в сообщении #1568207 писал(а):

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

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

[manul91]

mihaild в сообщении #1568209 писал(а):

Но вы противопоставляли дополнительный вход "стандартной МТ с присобаченным источником истинной случайности".

Не скажу бы что "противопоставлял", скорее сравнивал. Разумеется я согласен, что эти две модели (с включенном источником истинной случайности, и с дополнительной подачи бесконечных данных на вход снаружи) математически эквивалентны, что касается возможности выдачи требуемого результата. Но заметьте что в моем определении интерфейса "штукенции Х" особо оговаривается, что ничего большего ее на вход не подается. А значит "модель с бесконечных данных подаваемых на вход" не проходит по условию.

mihaild в сообщении #1568209 писал(а):

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

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

[mihaild]

manul91 в сообщении #1568210 писал(а):

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

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

manul91 в сообщении #1568210 писал(а):

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

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

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