Difficult?: Function simulator does not exist.

[wij]

Let F be the set of computational function that takes no argument and returns
0 or 1. A decision function S:{0,1}* -> {0,1}, takes a function f in F as the
argument and returns whatever f returns.
It is obvious that such S is trivial: int S(Func f) { return f(); }
But there also exists such an instance g(): int g(void) { return !S(g); }
that S(g) always returns the wrong answer.
Therefore: A fully function simulator S cannot exist.

[Andy Walker]

I haven't seen that exact argument before [but I'm not an expert
in this area, merely interested (and in a former life required to teach
it)]. But it's essentially the "Blank Tape Halting Problem" ["Does a
given TM halt when started with a blank tape?"], easily seen to be
equivalent to the standard HP; so membership of "F" is problematic. Of
course, we're then quickly back into familiar territory for this group.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Bucalossi

[Ben Bacarisse]

This is not yet a fully worked-out argument. The main problem is that
that you assume that g is in F and there is no guarantee that it is. In
fact, at first glance it isn't, but that first glance is not definitive
because you are glossing over how an element of {0,1}* represents the
computation, and what the underlying model is. I am not sure this can
be fixed, but you might like to have a go.

(And some of your terminology is misleading. For example, the word
function, in this context, is not like a C function, so it's best
avoided -- unless you really do want the mathematical meaning. And your
"decision function" is not a decider in the usually sense either.)

--
Ben.

[Richard Damon]

Maybe in other words, S(f) only needs to return an answer if f() would
return an answer, we KNOW that it is impossible for S to reliably detect
that f never halts.

That says that f is only a finite computation if S(f) returns and answer
in finite time, so the possible answer to the contradiction of S(f) is
to just not answer, which means that f isn't in F, and S doesn't neec to
give an answer.

From PO's work, we know that any simulator that doesn't try to be a
Halt Decider, if the input contains a copy of the simulator, we end up
with a non-halting computation, so both f() and S(f) become non-halting,
but since f() is non-halting, that doesn't mean that S is not a correct
simulator, as f wasn't in F.

[wij]

{0,1}* means bit-string which can be any program (x86,TM,...)

To avoid the issue that g∉F, we modify the spec. of S:
Spec1: S(x) returns 1 if x() returns 1.
Spec2: S(x) returns 0 if x() returns 0 or x() is non-halting.

S is now looked like a kind of satisfaction function, so call it Sat(x)
Claim: Sat(x) cannot exist, because there always exists such an instance g():
int g(void) { return !Sat(g); }
that Sat cannot accomplish its task.

If g()=1, then Sat(g)=0, but Sat spec2. says g returns 0 or non-halt (Sat failed)
If g()=0, then Sat(g)=1, but Sat spec1. says g returns 1 (Sat failed)
If g() is non-halting, then Sat(g) is non-halting (Sat failed)

Am I confused of or missing anything?
I did not study such question deep and not familiar with 'computation theory'
(I read about 7,8 such books long time ago). This problem is converted from a
similar one I came across recently and seemed appropriate to submit in current
'HP atmosphere'.

[Malcolm McLean]

On Tuesday, 18 January 2022 at 09:27:55 UTC, wij wrote:
> On Monday, 17 January 2022 at 22:30:14 UTC+8, wij wrote:
> > Let F be the set of computational function that takes no argument and returns
> > 0 or 1. A decision function S:{0,1}* -> {0,1}, takes a function f in F as the
> > argument and returns whatever f returns.
> > It is obvious that such S is trivial: int S(Func f) { return f(); }
> > But there also exists such an instance g(): int g(void) { return !S(g); }
> > that S(g) always returns the wrong answer.
> > Therefore: A fully function simulator S cannot exist.
> {0,1}* means bit-string which can be any program (x86,TM,...)
>
> To avoid the issue that g∉F, we modify the spec. of S:
> Spec1: S(x) returns 1 if x() returns 1.
> Spec2: S(x) returns 0 if x() returns 0 or x() is non-halting.
>

So now S(x) can be trivially turned into a halt detector, by passing in
a modified version of x() that always returns 1 if it halts at all.

You've reformulated Turing original proof that halt detectors cannot be
written.