Re: D correctly simulated by H cannot possibly halt --- templates and infinite sets

On 5/28/24 10:23 PM, olcott wrote:

On 5/28/2024 9:04 PM, Richard Damon wrote:

On 5/28/24 12:16 PM, olcott wrote:

typedef int (*ptr)();  // ptr is pointer to int function in C
00       int H(ptr p, ptr i);
01       int D(ptr p)
02       {
03         int Halt_Status = H(p, p);
04         if (Halt_Status)
05           HERE: goto HERE;
06         return Halt_Status;
07       }
08
09       int main()
10       {
11         H(D,D);
12         return 0;
13       }
>
When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
*Formalizing the Linz Proof structure*
∃H  ∈ Turing_Machines
∀x  ∈ Turing_Machines_Descriptions
∀y  ∈ Finite_Strings
such that H(x,y) = Halts(x,x)

>
But since for x being the description of the H^ built from that H and y being the same, it turns out that no matter what answer H gives, it will be wrong.
>

 We have not gotten to that point yet this post is so that
you can fully understand what templates are and how they work.

But note, x, being a Turing Machine, is NOT a "template"
And H, isn't a "set of Turing Machines", but an arbitrary member of that set, so all we need to do is find a single x, y, possible determined as a function of H (so, BUILT from a template, but not a template themselves) that shows that particular H was wrong.
That is basically what Linz does.
Given a SPECIFIC (but arbitary) H, we can construct a specific H^ built from a template from H, that that H can not get right.
All the other H's might get this input right, but we don't care, we have shown that for every H we

 

(And I think you have an error in your reference to Halts, I think you mean Halts(x,y) not Halts(x,x)
>

 Yes good catch. I was trying to model embedded_H / ⟨Ĥ⟩
and then changed my mind to make it more general.
 

>
*Here is the same thing applied to H/D pairs*
∃H ∈ C_Functions
∀D ∈ x86_Machine_Code_of_C_Functions
such that H(D,D) = Halts(D,D)

>
Not the same thing.
∃H ∈ C_Functions
is not equivalent to
∃H  ∈ Turing_Machines
>
as there are many C_Functions that are not the equivalent of Turing Machines.
>

 The whole purpose here is to get you to understand what
templates are and how they reference infinite sets.
 

But the problem is that even in your formulation, H and D are, when doing the test, SPECIFIC PROGRAMS and not "templates" as Halts is defined on the domain of PROGRAMS.
Similarly, a "Template" doesn't have a specific set of x86_Machine_Code_of_C_function, at least not one with defined behavior since if it tries to reference code outside of itself, then Halts of that just isn't defined, only Halts of that code + the specific machine deciding it.

>

>
In both cases infinite sets are examined to see
if any H exists with the required properties.
>

>
Yes, but the logic of Turing Machines looks at them one at a time, and the input is a FULL INDEPENDENT PROGRAM.
>

 ∃H  ∈ Turing_Machines
That does not look at one machine it looks as an infinite set of
machines. I am very happy to find out that you were not playing head
games. Linz actually used the words that you referred to.

while the ∃H part can create a set of machines, each element of that set is INDIVIDUALLY TESTED in the following conditions, so, when we get to your test  H(x,y) = Halts(x,x), each of H, x, y are individual members of the set, and we THEN collect the set of all of them.
If we try to say
∃x ∈ Natural Numbers, such that  x+x = 3
we can't say that x is both 1 and 2 and thus as a set meet the requirement. For the conditions, each qualifier select a single prospective element, and those are tested to see if that meet the requirement.

 

I'm not sure what you can define your computation system to be actually based on, and what its supposed use is, since your 'decider' and 'input' are so intertwined.
>

 The whole purpose here is to get you to understand what
templates are and how they reference infinite sets.

I understand how they work, the problem is you think they somehow change the meaning of the final condition.
H(D,D) == Halts(D,D) doesn't mean that we get to look at some other choice of H with some other choice of D to provide the D for Halts then what H was given.

 

And your supposed algorithm just doesn't work when you try to make you system "Turing Complete" by letting D have the ability to have a COPY of H, and being able to make copies of its input, like real Turing machines can.
>

 The whole purpose here is to get you to understand what
templates are and how they reference infinite sets.
 All the other issues are for another different post.
 

And you are just showing that YOU don't understand it, as it doesn't get you anywhere closer to you goal.
The qualifier step is STILL done with a single specific element from each of the sets.
Since for every element of the first set (your ∃H) there exists an input that that particular H will get wrong, you can't use the "infinite set of H/D" to argue that it was right.
All that does is prove that their does NOT exist an H that meets the requirements.