Re: Another Halting Problem Question (very difficult)

On Wed, 2024-05-29 at 02:28 +0100, Mike Terry wrote:

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.
 

Rice's theorem: Any nontrivial property about the language recognized by a Turing machine is
undecidable.
http://kilby.stanford.edu/~rvg/154/handouts/Rice.html

The above translated me: Any nontrivial property about a computation function
is undecidable.

typedef bool (*Func)();
bool sat(Func f);

1. Func includes lots of nontrivial functions.
2. sat(f) can't be proved undecidable by Halting Problem like method. I guess
   Rice's theorem is based on the same method for its claim.

   E.g. This typical example won't work. Because whenever u is proven
        undecidable, u is an Invalid Input (Olcott 2024).

        bool u() {
          return sat(u);
        }