Так, значит, выходит: утром лирические мысли, а вечером - физические. Такой сегодня день.
Некто
talash напомнил/а о теме: способы "обойти" ограничения машин Тюринга, в частности, решить
the Halting Problem (Шишков, прости...), используя разного рода "физические" трюки.
Года два назад завязался спор по этому поводу в
рассылке FOM,
Джо Шипман
утверждал, что некоторые свойства квантовой физики - в основном связанные с нормализацией - могут в принципе дать нам возможность экспериментально измерить со сколь угодно высокой точностью значения нерекурсивных действительных чисел. Я же пытался ему
доказать, что у него было слишком наивное понимание того, что есть computation в принципе и что мы понимаем под решением проблемы в частности. Самую важную мысль оттуда надо повторить здесь, она пытается взглянуть поближе на вопрос о предварительном знании, о котором обычно предпочитают не вспоминать; надо будет над этим ещё думать:
Imagine that I let you work with a black box,
with one input string and one output string, which purports to solve the
halting problem. You know that the black box entails an algorithm in the usual sense of a Turing machine, but you don't know what the algorithm is. You cannot then prove experimentally, by working with the black box, that it doesn't solve the halting problem (to be able in general to do that, you would have to be able to recursively enumerate nonhalting machines to find the one it misidentifies as halting - i.e. to be able yourself to solve the halting problem).
А недавно вот была другая статья, лектора с факультета философии здешнего Иерусалимского университета, о возможном решении halting problem с помощью общей теории относительности. Но и там по сути дела те же проблемы - он не понимает принципиальной важности верификации (точнее, возможности верификации), без которой просто нет причин доверять никакому физическому аппарату, который претендует на то, что он вычисляет нерекурсивную функцию.
В этот раз изюминка была такая: система Эйнштейновских уравнений в принципе допускает такую конфигурацию, при которой в одной части пространства время течёт бесконечно быстрее (при помощи ускорения, я полагаю) другой части пространства, и при этом они могут обмениваться сигналами. Тогда мы можем решить halting problem так: пошлём описание алгоритма в "быструю часть", в которой проходит "вечность" в то время, что у нас проходит секунда; там запустим алгоритм на обычной машине Тюринга, и если он остановится, пошлём сигнал обратно; если первоначальная машина не получит сигнал за секунду, значит, алгоритм не останавливается.
Проблема опять-таки в полной невозможности математической формализации этого аппарата, в отсутствие которой нет причины верить в то, например, что неполучение сигнала вызвано именно тем, что алгоритм не остановился, а не тем, что сигнал потерялся по дороге. Т.е. и в обычных компьютерах сигналы могут теряться, но там мы знаем, что виновато "железо", а не математическая модель, которой мы доверяем; и возможность независимой верификации позволяет нам уменьшать риск ошибки, вызванный физическими причинами. А в этом аппарате "физические" причины и невозможность верификации - принципиальны: there's inevitable spillage of the mathematical into the physical.
Вот вместо того, чтобы лениться, надо бы засесть как следует за это, и расписать более ясно и внятно. Да только вряд ли выйдет.
giggly