Re: Halting Problem is wrong two different ways

On 2024-06-05 13:59:53 +0000, olcott said:

On 6/5/2024 3:11 AM, Fred. Zwarts wrote:

Op 05.jun.2024 om 04:05 schreef olcott:

On 6/4/2024 8:48 PM, Richard Damon wrote:

On 6/4/24 1:40 PM, olcott wrote:

On 6/4/2024 3:28 AM, Mikko wrote:

On 2024-06-03 18:14:39 +0000, olcott said:
 

On 6/3/2024 9:27 AM, Mikko wrote:

On 2024-06-03 12:20:01 +0000, olcott said:
 

On 6/3/2024 4:42 AM, Ben Bacarisse wrote:

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
 

PO's D(D) halts, as illustrated in various traces that have been posted here.
PO's H(D,D) returns 0 : [NOT halting] also as illustrated in various traces.
i.e. exactly as the Linz proof claims.  PO has acknowledged both these
results.  Same for the HH/DD variants.
 You might imagine that's the end of the matter - PO failed.  :)
 That's right, but PO just carries on anyway!

 He has quite explicitly stated that false (0) is the correct result for
H(D,D) "even though D(D) halts".  I am mystified why anyone continues to
discuss the matter until he equally explicitly repudiates that claim.
 

 Deciders only compute the mapping *from their inputs* to their own
accept or reject state.

 That does not restrict what a problem statement can specify.
If the computed mapping differs from the specified one the
decider does not solve the problem.

 int sum(int x, int y) { return x + y; }
sum(2,3) cannot return the sum of 5 + 6.

 That does not restrict what a problem statement can specify.
If the mapping computed by sum differs from the specified one
the program sum does not solve the problem.
 

 On 6/3/2024 9:53 PM, Richard Damon wrote:
 > Because you keep on mentioning about DD Halting,
 > which IS about the direct execution of DD
 Only when one contradicts the definition of a decider that must
compute the mapping FROM ITS INPUTS BASED ON THE ACTUAL BEHAVIOR
OF THESE INPUTS (as measured by DD correctly simulated by HH).

 But strings don't HAVE "Behavior", they only represent things that do.
 

 Turing Machine descriptions specify behavior to UTMs.
 

And, for a Halt decider, that thing they represent is the program, whose direct execution specifies the proper behavior of the input.
 The DEFINITON IS NOT  "as measured by DD correctly simulated by HH", as deciders, by their definiton, are trying to compute the mapping of their input according to a defined function, which is a function of just that input. Since that function doesn't know which "H' is going to try to decide on it, it can't change its answer based on which H we ask.
 Proper Deciders can not be asked "Subjective" questions, unless we SPECIFICALLY define the mapping to include the decider as one of the inputs, and at that point, the question actually ceases to be subjective, as it becomes, what should THAT H say about this input, which is back to an objective agian (since machines are deterministic, so the definition of H tells us what H will answer to that question).
 

 When we go ahead and contradict this definition then the
*HALTING PROBLEM IS STILL WRONG IN A DIFFERENT WAY*

 Nope, YOU are wrong, because you
 

 When D is defined to do the opposite of whatever yes/no
an answer that H provides then the counter-example input
is precisely isomorphic to the question:
Is this sentence: "This sentence is not true." true or false?
Thus that question and the HP question are both incorrect
because both yes and no are the wrong answer.

 Nope, Just shows how small your mind is.
 Proven elsewhere.,
 

 The theory of computation may be ignorant of the details of
how the context of who is asked a question changes the meaning
of this question, none-the-less this cannot be ignored.
It is and remains incorrect for the theory of computation
to ignore this.
 

 But the question it asks is an OBJECTIVE question that doesn't depend on who it is asked of.
 

 When H is asked about the behavior of a Machine that is programmed
to do the opposite of whatever it says then the context that it is H
that is being asked is an inherent aspect of the meaning of this
question and cannot be correctly ignored.

 But that has nothing to do with your simulation result.

 Notice the subject line of this thread.
That HH is being asked an incorrect question is the second
way that the Halting Problem is wrong.
 

Your simulation does not even reach the part that contradict its result.
Your decider even diagnoses programs as non-halting when they do not contradict the result of the decider, as in:
        typedef int (*ptr)();  // ptr is pointer to int function in C
        int H(ptr p, ptr i);
        int main()
       {
         H(main, 0);
       }
 It is clear that main does not programmed to do the opposite of what H says.
 

 *I was surprised that this worked correctly:

Be specific: the test of HH workeed correcty when it
correctrly demonstrated that HH woked incorrectly.
HH did not work correctly when it, just before main
halted, said that main will not

here are the details*
 int main()
{
   Output("Input_Halts = ", HH(main,(ptr)0));
}
   machine   stack     stack     machine    assembly
  address   address   data      code       language
  ========  ========  ========  =========  =============
[00001e42][00103375][00000000] 55         push ebp      ; begin main
[00001e43][00103375][00000000] 8bec       mov ebp,esp
[00001e45][00103371][00000000] 6a00       push +00
[00001e47][0010336d][00001e42] 68421e0000 push 00001e42 ; push main
[00001e4c][00103369][00001e51] e831f5ffff call 00001382 ; call HH
New slave_stack at:103419
 Begin Local Halt Decider Simulation   Execution Trace Stored at:113421
[00001e42][0011340d][00113411] 55         push ebp      ; begin main
[00001e43][0011340d][00113411] 8bec       mov ebp,esp
[00001e45][00113409][00000000] 6a00       push +00
[00001e47][00113405][00001e42] 68421e0000 push 00001e42 ; push main
[00001e4c][00113401][00001e51] e831f5ffff call 00001382 ; call HH
New slave_stack at:14de41
[00001e42][0015de35][0015de39] 55         push ebp      ; begin main
[00001e43][0015de35][0015de39] 8bec       mov ebp,esp
[00001e45][0015de31][00000000] 6a00       push +00
[00001e47][0015de2d][00001e42] 68421e0000 push 00001e42 ; push main
[00001e4c][0015de29][00001e51] e831f5ffff call 00001382 ; call HH
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
 [00001e51][00103375][00000000] 83c408     add esp,+08
[00001e54][00103371][00000000] 50         push eax
[00001e55][0010336d][00000743] 6843070000 push 00000743
[00001e5a][0010336d][00000743] e843e9ffff call 000007a2
Input_Halts = 0

Here main reports that HH said that main will not halt.

[00001e5f][00103375][00000000] 83c408     add esp,+08
[00001e62][00103375][00000000] eb79       jmp 00001edd
[00001edd][00103375][00000000] 33c0       xor eax,eax
[00001edf][00103379][00000018] 5d         pop ebp
[00001ee0][0010337d][00000000] c3         ret           ; end main

Here main halts.

Number of Instructions Executed(12311) == 184 Pages
 So main() does halt at its final state at [00001ee0] which proves
that the directly executed HH(main,(ptr)0) called by main() halts
and returns 0;

That main halts does not prove that HH returns 0 but that doesn't
mater as that was already proven right after HH returned 0.
--
Mikko