Re: Another Halting Problem Question (very difficult)

On Wed, 2024-05-29 at 06:55 +0800, wij wrote:

On Wed, 2024-05-29 at 06:20 +0800, wij wrote:

On Wed, 2024-05-29 at 05:37 +0800, wij wrote:

Everybody knows the Halting Problem is undecidable (liars also know). But if we
restrict the condition a little bit: Does there exists a decision function h, h
determines whether or not an arbitrary function void f() (given as the argument
of h) terminates or not (h,f∈O(2^N)) ? IOW, h(f)==true iff f() terminates.

 
Sorry, too quick in rephrasing the real problem. I should fix this latter.
 

 
Correction:
Does there exist a O(2^N) decision function sat, sat terminates whether or not
a O(2^N) function bool f() (given as the argument of sat) returns true or not?
IOW, sat(f)==true iff f()==true
 
 

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.

Is Rice's theorem (or GUR if you like) refuted?