Re: Another Halting Problem Question (very difficult)

Liste des GroupesRevenir à theory 
Sujet : Re: Another Halting Problem Question (very difficult)
De : news.dead.person.stones (at) *nospam* darjeeling.plus.com (Mike Terry)
Groupes : comp.theory
Date : 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.

Date Sujet#  Auteur
28 May 24 * Another Halting Problem Question (very difficult)6wij
29 May 24 `* Re: Another Halting Problem Question (very difficult)5wij
29 May 24  `* Re: Another Halting Problem Question (very difficult)4wij
29 May 24   `* Re: Another Halting Problem Question (very difficult)3wij
29 May 24    `* Re: Another Halting Problem Question (very difficult)2Mike Terry
29 May 24     `- Re: Another Halting Problem Question (very difficult)1wij

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal