тюринговедение
Jun. 24th, 2001 07:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaТак, значит, выходит: утром лирические мысли, а вечером - физические. Такой сегодня день.
Некто![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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.
Вот вместо того, чтобы лениться, надо бы засесть как следует за это, и расписать более ясно и внятно. Да только вряд ли выйдет.
Некто
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.
Вот вместо того, чтобы лениться, надо бы засесть как следует за это, и расписать более ясно и внятно. Да только вряд ли выйдет.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2001-06-24 12:26 pm (UTC)no subject
Date: 2001-06-24 02:16 pm (UTC)Òàê. ß ïðèìåðíî ýòî è ñêàçàë åìó âî âðåìÿ ëåêöèè, íî îí ìåíÿ íå ïîíÿë ñîâñåì. Ò.å. ó íåãî õîä ìûñëåé áûë ïðèìåðíî òàêîé: íó è ÷òî, ÷òî ìîæíî ïîääåëàòü, êîãî ýòî âîëíóåò âîîáùå? íàñ èíòåðåñóåò, êàê ìîæíî ñäåëàòü in the first place. À ÿ äóìàþ, êàê áû ýòî ïîëó÷øå ñôîðìóëèðîâàòü, ÷òî íåëüçÿ âîîáùå ñäåëàòü, íåëüçÿ ãîâîðèòü î òîì, ÷òî ñäåëàíî, åñëè ìîæíî ýôôåêòèâíî ïîääåëàòü.
È â ïðèíöèïå-òî ýòî ìíå ÿñíî, íî ïî-íàñòîÿùåìó óáåäèòåëüíî ýòî äîêàçàòü ÿ, êàæåòñÿ, íå ìîãó ïîêà. Òàêîå âïå÷àòëåíèå, ÷òî íàäî ñïóñòèòñÿ ÷óòü-÷óòü ïîíèæå è çàíÿòüñÿ ôóíäàìåíòàëüíûì âîïðîñîì - ÷òî åñòü computation è ÷òî ïîçâîëÿåò íàì íåêèé ïðîöåññ ñ÷èòàòü computation, à íåêèé äðóãîé íå ñ÷èòàòü. Ïðîøó ïðîùåíèÿ, åñëè âñ¸ ýòî ñëèøêîì ñóìáóðíî çâó÷èò.
"Ñîëîâåöêèé îðàêóë"
Date: 2001-06-24 08:32 pm (UTC)Ïîýòîìó òàêàÿ ìîäåëü óæå íå áóäåò ýêâèâàëåíòíà òþðèíãîâñêîé.
Êñòàòè, à ïðèíèìàåì ëè ìû òàêóþ ñîìíèòåëüíóþ âåùü, êàê âåðèôèêàöèÿ ðàáîòû ìàøèíû Òþðèíãà ïðè ïîìîùè òàêîé æå (ýêâèâàëåíòíîé) ìàøèíû Òþðèíãà? Âî ÷òî ìû "âåðèì", ïðèíèìàÿ ýòî?
Íåòó ëè òóò íåêîåãî Catch-22?
Another comment about oracle
Date: 2001-06-25 01:47 am (UTC)There is a subfield of CS called "Computational Complexity" which among the rest deals with similar problems. However the more one-tries to go to the foundations of "computation", "knowledge", "information" the more scholastic it becomes. It resembles theological debates of XI-XIII century. If "object A" exists then we can prove such and such wonderful results... And we belive that "object A" exists.
Scientific value of this stuff may be questionable, but it is definitely a great fun!
Re:
Date: 2001-06-25 02:13 am (UTC)Êñòàòè, à ïðèíèìàåì ëè ìû òàêóþ ñîìíèòåëüíóþ âåùü, êàê âåðèôèêàöèÿ ðàáîòû ìàøèíû Òþðèíãà ïðè ïîìîùè òàêîé æå (ýêâèâàëåíòíîé) ìàøèíû Òþðèíãà? Âî ÷òî ìû "âåðèì", ïðèíèìàÿ ýòî? [/i]
Íàñêîëüêî ÿ ïîíèìàþ, âñå ýòî îñíîâûâàåòñÿ íà áàçîâîé àêñèîìå íàó÷íîãî ìåòîäà - ÷òî ñóùåñòâóþò íåêèå îáüåêòèâíûå çàêîíû, êîòîðûå ìîæíî íàáëþäàòü îïûòíûì ïóòåì.  ÷àñòíîñòè, ÷òî ôóíêöèîíèðîâàíèå ÌÒ ïîä÷èíÿåòñÿ íåêèì îáüåêòèâíûì çàêîíàì, à, ñëåäîâàòåëüíî, àíàëîãè÷íàÿ ÌÒ, ïîä÷èíÿÿñü òåì æå çàêîíàì, áóäåò ðàáîòàòü òàê æå. È åñëè ìû íàáëþäàåì ðàçëè÷èÿ, òî ïðè÷èíà òóò íåèçáåæíî áóäåò â ðàçëè÷èè íà÷àëüíûõ óñëîâèé.
Íî äàåò ëè îíà ïðè ýòîì ïðàâèëüíûé îòâåò íà çàäà÷ó?
Date: 2001-06-25 02:47 am (UTC)Re: Íî äàåò ëè îíà ïðè ýòîì ïðàâèëüíûé îòâåò íà çàäà÷ó?
Date: 2001-06-25 04:42 am (UTC)Ìîæåò, îíà "íà òî"...
Date: 2001-06-25 05:06 am (UTC)Ïîëó÷àåòñÿ òàê
Date: 2001-06-25 05:29 am (UTC)2. Ìû ñòðîèì íåêóþ ðåàëüíóþ ÌÒ, ñîîáðàçóÿñü ñ íàøèìè çíàíèÿìè î òîì, êàê âåäóò ñåáÿ ðåàëüíûå ôèçè÷åñêèå ÿâëåíèÿ. Î ïðàâèëüíîñòè ìû ñóäèì, ñðàâíèâàÿ ðåçóëüòàòû ðàáîòû ýòîé ÌÒ ñ òåì, ÷òî äîëæíà âûäàâàòü èäåàëüíàÿ ÌÒ. Åñëè ýòè ðåçóëüòàòû ñîâïàäàþò, ìû ñ÷èòàåì, ÷òî îíà ïîñòðîåíà ïðàâèëüíî. Äîêàçàòü ýòî ìû íå ìîæåì.
Ñîîòâåòñòâåííî, ïîëó÷àåòñÿ, ÷òî íèêàêîå äîêàçàòåëüñòâî, ïîëó÷åííîå ñ ïîìîùüþ òîëüêî ðåàëüíîé ÌÒ, íå ìîæåò ÿâëÿòüñÿ 100% ñòðîãèì, è îñíîâàíî íà íàøåì "äîâåðèè" ê ðåçóëüòàòàì ðåàëüíîé ÌÒ, ñâÿçàííîì ñ òåì, ÷òî èçâåñòíûå íàì çàäà÷è îíà ðåøàåò òàê, êàê äîëæíà ýòà äåëàòü èäåàëüíàÿ ÌÒ.
This way of cheating seems to be incorrect
Date: 2001-06-25 01:18 am (UTC)Re: This way of cheating seems to be incorrect
Date: 2001-06-25 02:10 am (UTC)The physical side of this is also that it might not be feasible to discover "fake" with sufficiently large values of T.
Re: This way of cheating seems to be incorrect
Date: 2001-06-25 02:36 am (UTC)1..2^n and then halts. Computer A will probe computer B' with such programs for n=1,2... he knows for sure the correct answer for all of them. Although A does not know T , A can catch the cheater in finite (but possibly not bounded) number of steps. The order of quatifiers is important here: T has to be chosen before A starts its tests.
Re: This way of cheating seems to be incorrect
Date: 2001-06-25 03:02 am (UTC)Re: This way of cheating seems to be incorrect
Date: 2001-06-25 02:42 am (UTC)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
Date: 2001-06-25 05:17 am (UTC)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
Date: 2001-06-25 05:25 am (UTC)Re: Simple proof
Date: 2001-06-25 05:29 am (UTC)Hmmm
Date: 2001-06-25 05:59 am (UTC)Like in the immortal poem by Nikolai Glazkov:
ß ñïðîñèë: "êàêèå â ×èëè
Ñóùåñòâóþò ãîðîäà?"
Îí îòâåòèë: "Íèêîãäà" -
È åãî ðàçîáëà÷èëè.
Re: Hmmm
On a second thought,
Date: 2001-06-25 06:10 am (UTC)For some reason, I was thinking exactly of that definition. Ah, the importance of defining everything...
no subject
Date: 2001-06-24 12:58 pm (UTC)ß ïðîñòîäóøíî ïîëîãàë, ÷òî åñòü ìîäåëü Òþðèíãà,
â íåé îäíè ïðîáëåìû. Åñòü ìîäåëü êâàíòîâîãî êîìïóòåðà
-- òàì äðóãèå. Ìîæíî ñîáðàòü ìîäåëü ñ
áåñêîíå÷íûì óñêîðåíèåì âðåìåíè -- áóäåò åùå
êàêàÿ-òî, âðÿä ëè èíòåðåñíàÿ.
no subject
Date: 2001-06-24 02:07 pm (UTC)Èäåÿ òóò â òîì, ÷òî äà, ìîäåëè òàêèå (êñòàòè â ìîäåëè êâàíòîâîãî êîìïüþòåðà òå æå ïðîáëåìû, îí ïîëíîñòüþ ýìóëèðóåòñÿ íà êëàññè÷åñêîé ìàøèíå Òþðèíãà, òîëüêî ñ ýêñïîíåíöèàëüíûì çàìåäëåíèåì, â ýòîì-òî âñÿ èçþìèíêà), à âîò ýòè ãîâîðÿò, ÷òî íà ïðàêòèêå, èñïîëüçóÿ ôèçèêó, ìîæíî ïðåâçîéòè îãðàíè÷åíèÿ ìîäåëåé. À ÿ ñ ýòèì íå ñîãëàñåí, íî ïðè÷èíû ýòîãî íåñîãëàñèÿ êàê ðàç ëåæàò â îáëàñòÿõ ýïèñòåìîëîãèè, êîòîðûå ïðàêòè÷íûå êîìïüþòåð ñàéåíòèñòû îáû÷íî çàìåòàþò ïîä êîâ¸ð.
Íî ïðàêòè÷íî ëè âñ¸ ýòî? - êîíå÷íî, íåò. Äà è êâàíòîâûå êîìïüþòåðû ïîêà åù¸ ñîâåðøåííî íåïðàêòè÷íû, è íåÿñíî ñîâåðøåííî, áóäóò ëè è êîãäà.
no subject
Date: 2001-06-24 02:53 pm (UTC)ëè ôèçè÷åñêè îñìûñëåííàÿ ìîäåëü âû÷èñëåíèé íå
íå ñâîäÿùàÿñÿ ê Òþðèíãîâñêîé. Èñïîëüçóé ïàðàäîêñû.
Áûëà çàáàâíàÿ ðàáîòà Õàëôèíà (Khalfin), ïðî íåðàâåíñòâà Áåëëà è óïðàâëÿåìóþ ôèçèêó. Òåîðåìà, ÷òî ïðàâèëüíî íàáëþäàÿ,
ìîæíî íàáëþäàòü çàðàíåå çàêàçàííóþ êàðòèíó
ìèðîçäàíüÿ. Ìîæåò ìîæíî ÷åãî èçâëå÷ü.
Ìåíÿ êîãäà-òî ðàçâëåêàëè ðàçìûøëåíèÿ î ãëîáàëüíîé
îðãàíèçàöèè âû÷èñëåíèé. Ìû âñå ñ÷èòàåì è çàáûâàåì
è âñÿêèé ðàç, ïåðåãðóçèâøèñü, ñíîâà â íà÷àëå âðåìåí.
À ìîæíî ëè óñòðîèòü êàê â íàóêå --
êîïèòü ãëàâíóþ ÷àñòü èíòåðåñíîãî âû÷åñëåííîãî â âèäå ìèðîâûõ êîíñòàíò? Ïðèìåðû åñòü --
âñÿêèå çàäà÷è êëàññèôèêàöèè, à â öåëîì?
no subject
Date: 2001-06-24 01:15 pm (UTC)íàáëþäàòåëÿ, ïðè÷¸ì â êîíå÷íîå ÷èñëî ðàç (íî íèêàê íå óñêîðèòü); â ÎÒÎ, íàñêîëüêî ÿ ïîìíþ, òàêæå íåò ñïîñîáà óñêîðèòü âðåìÿ, òåì áîëåå "áåñêîíå÷íî" (òóò ÿ ñîâñåì íå ïîíèìàþ).
no subject
Date: 2001-06-24 01:55 pm (UTC)no subject
Date: 2001-06-24 10:29 pm (UTC)Îäíàêî, ðàññóæäåíèÿ î áåñêîíå÷íîñòÿõ â ÑÒÎ/ÎÒÎ - áîëòîëîãèÿ, ò.ê. áåñêîíå÷íîå çàìåäëåíèå âðåìåíè ïðåäïîëàãàåò áåñêîíå÷íîå Ëîðåíòöåâî ñæàòèå, áåñêîíå÷íûå ïðèëèâíûå ñèëû è ò.ï.
Òàì - ñèíãóëÿðíîñòü, íå îïèñûâàåìàÿ èçâåñòíûìè ôèçè÷åñêèìè çàêîíàìè (áîëüøå òîãî, ýòà íåîïèñóåìîñòü åñòü íåîáõîäèìûé ýëåìåíò èçâåñòíûõ ôèçè÷åñêèõ çàêîíîâ), è ðàññóæäåíèå, îïèðàþùååñÿ íà âîçìîæíîñòü ÷òî-òî äåëàòü â ýòîé òî÷êå, êàê íà ïîñûëêó, çàâåäîìî íåêîððåêòíî.
 ÷åðíîé äûðå âïîëíå ìîãóò âîäèòüñÿ ÷åðòè ñ ðîãàìè è õâîñòàìè, ïî÷åìó íåò ?
no subject
Date: 2001-06-25 02:29 am (UTC)ñëåäû äèñêóññèé î ðàçðåøåíèè óêàçàííîé êâàíòîâî/GRT
ñèíãóëÿðíîñòè-øèçîôðåíèè. Õîêèíã-Ïåíðîóç --
âûëåòàåò ëè èíôîðìàöèÿ èç ÷åðíîé äûðû.
no subject
Date: 2004-01-16 01:57 pm (UTC)Сильно сомневаюсь, честно говоря. Такая ситуация просто лишена физического смысла, если задуматься.