PDA

Просмотр полной версии : Задача Neumann`a



50 CENT
09.03.2004, 11:10
Задача Neumann'а:
Написать программу, которая печатает свой код...

DeeJayC
09.03.2004, 13:09
Классика:


char *f="char*f=%c%s%c;main() {printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

А так...
http://www.nyx.net/~gthompso/quine.htm

50 CENT
11.03.2004, 08:31
вообще то я хотел теоретически поразмышлять над проблемой

Машина Тюринга:
Если задачу сформулировать как язык L={e | Me prints e}
(Me is a machine corresponding to Godel number e)
Кажись задача из класса "undecidable" (some literatures use "not recursive"). i.e. there is no machine such that it could decide whethere given encoding 'e' prints 'e'. Если эта задача из класса "undecidable" то можно доказать это используя другую undeciadable problem and reduce it to L. Про reduction надо подумать.

вроде раньше слышал про задачу но в то время не задумался...

P.S. кстати похожая задача: L = {e | Me accepts e (itself)}, i.e. machines/progs which accept themselves. it's an undecidable problem, можно доказать используя reduction из halting (H) problem
(H = {<e,w> | Me halts on w})