On 11/20/2021 6:44 PM, André G. Isaak wrote:
> On 2021-11-20 13:35, olcott wrote:
>> On 11/20/2021 2:03 PM, André G. Isaak wrote:
>>> On 2021-11-20 10:45, olcott wrote:
>>>> On 11/20/2021 12:57 AM, André G. Isaak wrote:
>>>>> On 2021-11-19 17:16, olcott wrote:
>>>>>> On 11/19/2021 5:33 PM, André G. Isaak wrote:
>>>>>>> On 2021-11-19 15:15, olcott wrote:
>>>>>>>> On 11/19/2021 3:05 PM, André G. Isaak wrote:
>>>>>>>>> On 2021-11-19 13:13, olcott wrote:
>>>>>>>>>> On 11/19/2021 2:03 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2021-11-19 12:26, olcott wrote:
>>>>>>>>>>>> On 11/19/2021 12:31 PM, André G. Isaak wrote:
>>>>>>>>>>>>> On 2021-11-19 11:06, olcott wrote:
>>>>>>>>>>>>>> On 11/19/2021 11:46 AM, André G. Isaak wrote:
>>>>>>>>>>>>>>> On 2021-11-19 10:32, olcott wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The input to (H,P) never halts P(P) halts.
>>>>>>>>>>>>>>>> Here are the divergent execution sequences at the C level:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> int main(){ H(P,P); }
>>>>>>>>>>>>>>>> (1) main()
>>>>>>>>>>>>>>>> (2) calls H(P,P) that simulates the input to H(P,P)
>>>>>>>>>>>>>>>> (3) that calls H(P,P) which aborts its simulation of
>>>>>>>>>>>>>>>> P(P) and returns to
>>>>>>>>>>>>>>>> (4) main().
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> int main(){ P(P); }
>>>>>>>>>>>>>>>> (a) main() calls P(P) that
>>>>>>>>>>>>>>>> (b) calls H(P,P) that simulates the input to H(P,P)
>>>>>>>>>>>>>>>> (c) that calls H(P,P) which aborts its simulation of
>>>>>>>>>>>>>>>> P(P) and returns to
>>>>>>>>>>>>>>>> (d) P(P) that returns to main()
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> (1) diverges from (a) causing (4) to diverge from (d)
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> And a halt decider is concerned only with the SECOND
>>>>>>>>>>>>>>> case, not the first.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> The halt decider is concerned with the execution trace of
>>>>>>>>>>>>>> a sequence of instructions other than the actual execution
>>>>>>>>>>>>>> trace that is specified by actually executing or
>>>>>>>>>>>>>> simulating its actual input?
>>>>>>>>>>>>>
>>>>>>>>>>>>> Your question makes no sense.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> It is proven that the execution trace of P(P) and the
>>>>>>>>>>>> execution trace of the input to H(P,P) are not the same and
>>>>>>>>>>>> that this difference results in different behavior.
>>>>>>>>>>>
>>>>>>>>>>> And the halting problem, BY DEFINITION, is concerned only
>>>>>>>>>>> with the former. The latter is not of interest to anyone.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> It may seem that way until you realize that any other case
>>>>>>>>>> would not be reporting on the actual behavior of the actual
>>>>>>>>>> sequence of instructions specified by the actual execution
>>>>>>>>>> trace of the actual simulation or execution of its actual input.
>>>>>>>>>
>>>>>>>>> The definition is what it is. A halt reporter reports on the
>>>>>>>>> behaviour of the computation described by its input when that
>>>>>>>>> computation is run as an independent computation; not when it
>>>>>>>>> is wrapped inside your H.
>>>>>>>>>
>>>>>>>>> Just because you don't like the definition doesn't mean you can
>>>>>>>>> change it.
>>>>>>>>
>>>>>>>> given the description of a Turing machine M and an input w, does M,
>>>>>>>> when started in the initial configuration q0 w, perform a
>>>>>>>> computation that eventually halts? (Linz:1990:317)
>>>>>>>>
>>>>>>>> In other words: Does UTM(M, w) halt?
>>>>>>>
>>>>>>> That definition makes no mention of UTMs, and he carefully
>>>>>>> distinguishes between the description of M (which he elsewhere
>>>>>>> notates as w_M).
>>>>>>>
>>>>>>> But yes, UTM(w_M, w) will halt if and only if M(w) halts.
>>>>>>>
>>>>>>
>>>>>> Because the behavior of the UTM simulation of the machine
>>>>>> description of TM X on input Y is defined to precisely correspond
>>>>>> to the direct execution of TM X on input Y we can also always rely
>>>>>> on the following:
>>>>>>
>>>>>> If UTM U is adapted to become a halt decider H for a subset of
>>>>>> inputs Z such that it aborts the simulation of its input only when
>>>>>> the behavior of the pure simulation of this input conclusively
>>>>>> proves that this input would never reach its final state, then H
>>>>>> can abort the simulation of every element of Z and correctly
>>>>>> report that its input does not halt.
>>>>>
>>>>> The fact that UTM(M, w) and M(w) have the same halting status has
>>>>> no bearing on the definition of a halt decider and provides no
>>>>> justification for the above.
>>>>>
>>>>> The input to UTM(M, w) doesn't have a halting status anymore than
>>>>> the input to H does. Only actual computations have a halting
>>>>> status. So you can ask about whether UTM(M, w) halts, or about
>>>>> whether the computation described by its input halts, but not about
>>>>> whether the input halts.
>>>>
>>>>
>>>>
>>>>> H(P, P) may or may not reach a final state. P(P) may or may not
>>>>> reach a final state. It is meaningless, though, to talk about the
>>>>> input to H(P, P) reaching a final state.
>>>>>
>>>>> André
>>>>>
>>>>>
>>>>
>>>> Not when the [PSR set] if the basis for this claim:
>>>>
>>>> Computation that halts
>>>> a computation is said to halt whenever it enters a final state.
>>>> (Linz:1990:234)
>>>>
>>>> PSR set: Combinations of H/P having pathological self-reference
>>>> For every possible H of H(P,P) invoked from main() where P(P) calls
>>>> this same H(P,P) and H simulates or executes its input and aborts or
>>>> does not abort its input P never reaches its last instruction.
>>>>
>>>> PSR subset: Because we know that the input to H(P,P) never halts for
>>>> the whole PSR set and a subset of these H/P combinations aborts the
>>>> execution or simulation of its input then we know that for this
>>>> entire subset the input to H(P,P) never halts and H(P,P) halts.
>>>>
>>>> When int main(void) { P(P); } is invoked on H/P elements of the
>>>> above PSR subset, then we have a cases where the input to H(P,P)
>>>> never halts and P(P) halts.
>>>>
>>>> The above cases conclusively prove that when the input to H(P,P)
>>>> never halts and the same P(P) does halt that this does not form any
>>>> contradiction.
>>>
>>> Inputs neither halt nor don't halt. Your 'PSR set' included. Only
>>> Computions halt or don't halt.
>>>
>>
>> Inputs specify a sequence of configurations that either reach a final
>> state or not.
>>
>>> And, as I said, the definition of a Halt Decider is already defined.
>>
>> Halt decider H maps elements of its domain specifying sequences of
>> configurations to {0,1}. Its decision basis is whether or not the
>> specified sequence of configurations ever reaches a final state.
>>
>>> H(P, P), if it is a halt decider, must report whether P(P) called
>>> directly from main halts or not, so your meaningless claim that 'the
>>
>> An actual mathematical function H can only map elements of its domain
>> to elements of its codomain.
>>
>> In mathematics, a function from a set X to a set Y is an assignment of
>> an element of Y to each element of X. The set X is called the domain
>> of the function and the set Y is called the codomain of the function.
>> https://en.wikipedia.org/wiki/Function_(mathematics)
>>
>> Halt decider H can only map elements of its domain specifying
>> sequences of configurations to {0,1}.
>
> The domain of a halt decider is the set of computations (expressed by
> suitable representations)
>
> It maps that domain to 1 for exactly that set of computations which halt
> when run as independent computations and to 0 otherwise.
>
> Since P(P) halts, H(P, P) must map that input to 1.
>
> André
>

How do you tell a mathematical function that it is not allowed to base
its halt status decision on the sequence of configurations specified by
(P, I) and instead must base its halt status decision on P(I) [when run
independently] ???

--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer