Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

The steady state of disks is full. -- Ken Thompson

programming / comp.lang.asm.x86 / Re: Refuting the {Linz, Sipser, Kozen} HP Proofs (Ben's example)

o Re: Refuting the {Linz, Sipser, Kozen} HP Proofs (Ben's example)olcott

Subject: Re: Refuting the {Linz, Sipser, Kozen} HP Proofs (Ben's example)
From: olcott
Newsgroups: comp.theory,, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Thu, 17 Dec 2020 02:15 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
From: (olcott)
Newsgroups: comp.theory,,comp.lang.asm.x86
Subject: Re: Refuting the {Linz, Sipser, Kozen} HP Proofs (Ben's example)
Date: Wed, 16 Dec 2020 20:15:25 -0600
Organization: A noiseless patient Spider
Lines: 58
Approved: - comp.lang.asm.x86 moderation team.
Message-ID: <>
References: <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <rrdomo$4ta$>
<> <rrdqe4$i7d$>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info:; posting-host="4a23faa1200c6b29da9d0c80fbd9723f";
logging-data="32532"; mail-complaints-to=""; posting-account="U2FsdGVkX18aulg87ADCmyBa371nMxsF+NCxlqc40M0="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Cancel-Lock: sha1:apJW6iHzULjrkttVT7qej8tUCtc=
View all headers
On 12/16/2020 7:48 PM, Kaz Kylheku wrote:
On 2020-12-17, olcott <> wrote:
On 12/16/2020 6:21 PM, Kaz Kylheku wrote:
If Halts is really a pure function of two arguments, and it generates a
hierarchy of UTMs, then every call to Halts with the same two arguments
must generate exactly the same hierarchy of UTMs, and come to exactly
the same conclusion when it examines that hierarchy.

According to your reasoning the chairman of the board of a corporatation
is at the same place in the corporate hierarchy as the janitor.

You're forgetting that the hierarchy here is infinitely recursive due
to precise self-embedding: invocations of Halts(X, Y) contain
invocations of Halts(X, Y).

No you are forgetting that the pinnacle of the otherwise infinite simulation hierarchy cuts off the subsequent simulations as soon as it has seen enough of their execution trace to decide that it would be otherwise infinite.

We are talking about an actual program that actually executes one step at a time. Every time Halts executes it creates a process context that has its own registers memory and stack. It then executes its input as a separate virtual machine within this process context.

Then H_Hat executes Halts again and yet another process context is created to execute yet another virtual machine. Every time this occurs the number of process contexts and virtual machine increases to some finite number.

So for the corporation analogy not to be a strawman, we have to make
the corporation likewise infinitely nested, and we have to have
identical copies of the janitor and chairman at various levels.

Infinity is cut off at three.

The first invocation of Halts() is the pinnacle of the hierarchy and
every invocation after that is subordinate to the preceding one.

Every recursive invocation is indistinguishable.

Bullshit each one has a unique process ID.

Just like the suffix of
an infinite list of identical ducks is exactly the same as the original

Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre minds." Einstein

rocksolid light 0.7.2