50 CENT » 11 мар 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})
вообще то я хотел теоретически поразмышлять над проблемой
Машина Тюринга:
Если задачу сформулировать как язык 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})