Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory,sci.logic
Subject: Re: D correctly simulated by H cannot possibly halt --- templates and
 infinite sets
Date: Tue, 28 May 2024 23:38:43 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v36803$2d368$3@i2pn2.org>
References: <v3501h$lpnh$1@dont-email.me> <v362eu$2d367$3@i2pn2.org>
 <v363js$vg63$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 29 May 2024 03:38:43 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2526408"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <v363js$vg63$2@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 6655
Lines: 158

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.