Sujet : Re: Another Halting Problem Question (very difficult)
De : news.dead.person.stones (at) *nospam* darjeeling.plus.com (Mike Terry)
Groupes : comp.theoryDate : 29. May 2024, 02:28:31
Autres entêtes
Message-ID : <DO2dnck8JrFdGcv7nZ2dnZfqn_WdnZ2d@brightview.co.uk>
References : 1 2 3 4
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.17
On 29/05/2024 01:31, wij wrote:
[..snip..]
Revision:
Does there exist a decision function sat that determines whether or not a
terminating function bool f() (given as the argument of sat) returns true or
not? IOW, sat(f)==true iff f()==true.
Yes. A UTM meets your requirement, given that the input domain is limited to terminating functions f().
Is Rice's theorem (or GUR if you like) refuted?
No. You may be thinking that identifying functions that return true is identifying a "semantic property of functions" as required for Rice. But your requirement above is restricted to a domain containing only halting programs, so does not match Rice's theorem requirements.
Mike.