12 views

Skip to first unread message

Jan 17, 2022, 9:30:14 AMJan 17

to

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 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.

Jan 17, 2022, 12:25:36 PMJan 17

to

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

Jan 17, 2022, 5:09:17 PMJan 17

to

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.

Jan 17, 2022, 7:41:48 PMJan 17

to

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.

Jan 18, 2022, 4:27:55 AMJan 18

to

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'.

Jan 18, 2022, 5:10:46 AMJan 18

to

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
> 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.

>

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu