тюринговедение

[avva]

Так, значит, выходит: утром лирические мысли, а вечером - физические. Такой сегодня день.

Некто 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.

Вот вместо того, чтобы лениться, надо бы засесть как следует за это, и расписать более ясно и внятно. Да только вряд ли выйдет.

Comments

Re: This way of cheating seems to be incorrect

[avva.livejournal.com]

Yes, but the point is, since you don't know T, you can't put any time bound on your algorithm of finding the cheater. Thus if you are faced with *some* machine you're talking to, without knowing whether it's a cheater or the real thing, you don't have a deterministic algorithm, which does not depend on the value of T, and which would determine whether you're talking to a cheater. If you just keep throwing programs that stop in 2^n steps at it, it might just go on forever in case you're talking to the "real thing", thus your algorithm won't halt.

Of course, if you know the value of T, then it's easy. And since the value of T is something, and for each value of T there's a simple algorithm (depending on that value) which catches the cheater, you can claim that there is an algorithm that catches the cheater, you just don't know which one it is.

It's a typical Catch-22 situation (typical for this kind of considerations): the cheater cannot cheat perfectly, because then the cheater would have to be able to solve the Halting Problem himself. But the cheater can cheat effectively, and in order to call his bluff without knowing which cheating algorithm he chose you would have to be able to solve the Halting Problem yourself.

Simple proof

[khatul.livejournal.com]

Theorem: catching a cheating oracle for any yes/no problem is equivalent to solving the problem

Proof:

1) You got a solution? Compare it with oracle's reply. If they're different, the oracle cheats.

2) Got an algorithm to catch any cheater? Take Edgar Poe's oracle - a black box which answers "nevermore" to any question. The answer to the question "is it lying" is solving the original problem. QED

Nothing nontrivial. But then, so is half of all theorems.

Exactly

[stas]

That's generally what I meant. Thanks for formulating it cleaner :)

Re: Simple proof

[avva.livejournal.com]

Not quite so easy there, sport. If you have an algorithm to catch any cheater, the algorithm need only find one input to which the cheater answers incorrectly; it doesn't have to catch the cheater on any possible input, so to speak. Thus to catch Poe's cheater it's only have to find one input with the answer "yes", which is vastly easier than solving the problem.

Hmmm

[khatul.livejournal.com]

For THAT DEFINITION of catching a cheater, you're absolutely right.

Like in the immortal poem by Nikolai Glazkov:

ß ñïðîñèë: "êàêèå â ×èëè
Ñóùåñòâóþò ãîðîäà?"
Îí îòâåòèë: "Íèêîãäà" -
È åãî ðàçîáëà÷èëè.

Re: Hmmm

[avva.livejournal.com]

But I'll suspect you'll have to agree with me that mine is the natural definition of catching a cheater. There's nothing natural in defining "catching a cheater" as "being able to judge the truth of cheater's response on ANY possible input" :)

On a second thought,

[khatul.livejournal.com]

I agree with you wholeheartedly.

For some reason, I was thinking exactly of that definition. Ah, the importance of defining everything...