On 7/28/2021 11:15 PM, André G. Isaak wrote:
> No, it isn't a definition of halting. At best, it is something which you
> have proposed as a *test* for halting, but it is a broken test since, at
> least according to you, it sometimes gives an answer that does *not*
> correspond to the *actual* definition of halting.
>
It is computationally equivalent to not halting.
>
>>>> then we have the same situation as "This sentence is not true." It
>>>> is indeed not true and the definition of a true sentence is whether
>>>> or not its assertion is satisfied.
>>>
>>> I fail to see any parallels between P and the liar.
>>>
>>>> When we explicitly take into account the self-contradictory nature
>>>> of these two cases things are not as cut-and-dried.
>>>
>>> There's nothing self-contradictory about it.
>>>
>>>> "This sentence is not true." is indeed not true yet when we apply
>>>> this to the satisfaction of the whole sentence and not just its
>>>> assertion
>>>
>>> That is gibberish.
>>>
>>>> then we get a contradiction. If it is true that it is not true then
>>>> that makes is not true.
>>>>
>>>> It is an easily verifiable fact that the input to H(P,P) cannot
>>>> possibly reach its final state while H remains a pure simulator.
>>>> Because H
>>>
>>> But the definition of halting makes no reference to what H does at
>>> all, nor to pure simulators. whether P(P) halts is based solely on
>>> the behaviour of P(P).
>>>
>>
>> The definition of UTM does make reference to computational equivalence
>> forcing this statement to be necessarily true:
>
> Please show me a definition of UTM which makes reference to
> computational equivalence.
>
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
>> Every input to a simulating halt decider that only stops running when
>> its simulation is aborted unequivocally specifies a computation that
>> never halts.
>
> A 'simulating halt decider' and UTM are different things.
>
Not while the simulating halt decider is in pure simulator mode.
>>>> remains a pure simulator until after it makes its halt status
>>>> decision then its decision that its input never halts is necessarily
>>>> correct.
>>>>
>>>> That the first P in the infinitely recursive sequence reaches its
>>>> final state after H has made its correct halt status decision is
>>>> just like saying the liar paradox is true on the basis that its
>>>> assertion is satisfied.
>>>
>>> No. That the first P reaches its final state means that P(P) halts.
>>> The definition of halting doesn't care how or why it reaches this
>>> state. Only that it does.
>>
>> So then we must conclude the the self contradictory input causes the
>> logic of the system to be inconsistent because it proves that P halts
>> and it proves that P never halts.
>
> It shows the logic of the *decider* to be inconsistent. It doesn't show
> anything inconsistent about the definition of halting, nor does it
> provide to treat a computation which halts as anything other than a
> computation which halts.
>
Within the hypothesis that this is correct:
Within the hypothesis that this is correct:
Within the hypothesis that this is correct:
Within the hypothesis that this is correct:
Every input to a simulating halt decider that only stops running when
its simulation is aborted unequivocally specifies a computation that
never halts.
Then the fact that the first P of int main(){ P(P); } reaches its final
state wold seem to prove that we are getting the same contradiction as
the liar paradox.
This make perfect sense:
garbage in (self contradictory input)
garbage out (contradictory result).
> Whether P(P) halts is a question which is independent of any 'halt
> decider'.
>
> H cannot decide P(P) correctly. Other partial deciders are able to
> decide it correctly. But the definition of halting makes no reference to
> whether any other TM can decide it correctly. It refers only to whether
> P(P) reaches a final state in a finite number of steps. It does.
> Therefore it halts.
> You've raised this before. It's as meaningless now as it was when you
> first suggested it.
>
No it is not. It does perfectly address the issue of the liar paradox.
>>
https://www.researchgate.net/publication/323866366_The_Notion_of_Truth_in_Natural_and_Formal_Languages
>>
>>
>>> P(P), on the other hand, fully meets the definition of halting.
>>>
>>>> Whenever the assertion of a declarative sentence is satisfied we
>>>> know that this declarative sentence is true unless this declarative
>>>> sentence is self-contradictory.
>>>>
>>>> Whenever H decides that its input never halts its input never
>>>> reaches a final state. When its input is self-contradictory then
>>>> another different
>>>
>>> The input to H is simply *data*. Halting applies to *computations*.
>>>
>>
>> Not exactly: UTM(P,I) ≡ P(I)
>
> The inputs to a UTM are equally not a computation. They are data.
>
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
The simulation of the TM description of TM P on input I is stipulated to
be computationally equivalent to P(I). In an honest dialogue I would not
have to repeat this fifty times.
>>>> instance of the program that is not an input to H may halt.
>>>>
>>>>>>> But if P(P) doesn't halt in a 'pure simulator' then what kind of
>>>>>>
>>>>>> I did not say that P(P) does not halt in a pure simulator, you
>>>>>> must pay careful attention to every single word that I say. When
>>>>>> you skip a single word that reverses the meaning of what I say.
>>>>>>
>>>>>> The input to H(P,P) never halts while H remains in pure simulator
>>>>>> mode.
>>>>>
>>>>> So what's the difference between a 'pure simulator' and H running
>>>>> in 'pure simulator mode'? One would have assumed that the latter
>>>>> meant that H was acting as a pure simulator.
>>>>>
>>>>
>>>> H is evaluating the halt status of its input on the basis of what
>>>> the behavior of this input would be if H never aborts the simulation
>>>> of this input.
>>>
>>> Which is the wrong criterion for evaluating this. The correct
>>> criterion is simply whether P(P) reaches a final state.
>>>
>>> <snippage>
>>>
>>>> The bottom line is that self-contradiction must be treated
>>>> differently, the conventional rules do not apply to self-contradiction.
>>>
>>> Where does the definition of halting entail some class which must be
>>> treated differently? All computations either reach a final state in a
>>> finite amount of time or they do not. There is no third option.
>>>
>>
>> It is generally always the case that self-contradictory expressions of
>> language must always be treated differently than non
>> self-contradictory expressions of language.
>
> But there is no 'self-contradictory expression of language' in the Linz
> proof.
>
The input is defined to contradict whatever the halt decider decides
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to
M is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
The input is defined to contradict whatever the halt decider decides
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to
M is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
The input is defined to contradict whatever the halt decider decides
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to
M is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
> The definition of halting exhaustively partitions the set of all Turing
> Machines into two categories: those that halt and those that don't.
> There is *no* turing machine which fails to belong to one of these two
> classes because there is no logically possible third option.
>
>> That some sub-fields never noticed this is their fault and limitation.
>>
>>>> When the assertion of a declarative sentence is satisfied this makes
>>>> the sentence true unless the sentence is self-contradictory.
>>>>
>>>> The fact that "This sentence is not true." is not true does not make
>>>> the sentence true because the sentence is self-contradictory.
>>>>
>>>> When a simulating halt decider reports that its input does not halt
>>>> then no instance of the same program ever reaches a final state
>>>> unless the input program specifies self-contradiction.
>>>
>>> There are no 'instances of the same program' when talking in terms of
>>> Turing Machines.
>>>
>>> André
>>>
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt
>>
>> Ĥ( ⟨Ĥ⟩ ) specifies an infinite cycle from Ĥ.qx to Ĥ.q0 all the time
>> that Ĥ.qx remains a pure simulator of its input.
>>
>> Every simulation that would never stop unless its simulating halt
>> decider stops it at some point specifies infinite execution. This
>> remains true for: Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩)
>>
>> Ĥ( ⟨Ĥ⟩ ) only stops because its simulating halt decider stops it at
>> some point.
>
> And the definition of halting gives not one damn about *why* something
> halts. It only cares that it halts.
>
> André