Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2706 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-05-20 12:11 -0500 |
| Last post | 2021-05-20 13:36 -0500 |
| Articles | 3 — 2 participants |
Back to article view | Back to comp.software-eng
Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2) olcott <NoOne@NoWhere.com> - 2021-05-20 12:11 -0500
Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2) Mr Flibble <flibble@reddwarf.jmc> - 2021-05-20 19:07 +0100
Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ] olcott <NoOne@NoWhere.com> - 2021-05-20 13:36 -0500
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-20 12:11 -0500 |
| Subject | Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2) |
| Message-ID | <Y7adnVlvwpWdBTv9nZ2dnUU7-QfNnZ2d@giganews.com> |
This is a {clarification, correction and simplification} of the Peter
Linz text:
(a) Clarification all states are labeled with the machine name
(b) Correction the second q0 start state has been renamed qx
(c) Simplification tape states do not provide any useful information and
have been removed.
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
The above is adapted from (Linz:1990:319).
It shows that Turing machine Ĥ copies its input at (q0) and begins
executing an embedded copy of the original halt decider with this input
at (qx).
The (qy) state indicates that the halt decider has determined that its
input would halt.
The appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt
decider has determined that its input would halt.
The ((qn)) state indicates that the halt decider has decided that its
input would not halt.
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
*Three irrefutable truisms lead to one conclusion*
Truism (1a) and (1b) are semantically equivalent paraphrases of the
exact same hypothetical case:
Truism(1a)
The simulation of: ([Ĥ][Ĥ]) by the simulating halt decider @ Ĥ.qx would
never halt unless Ĥ.qx aborts this simulation.
Truism(1b)
(1a) is another way of saying that the simulation of: ([Ĥ][Ĥ]) by a UTM
@ Ĥ.qx would never halt.
Truism(2)
Every simulation of input P that would never halt unless simulating halt
decider H stopped simulating it <is> a non-halting computation. This
remains true even after H stops simulating P.
Any high school student would be able to analyze the basic logic of the
above and know that it is correct very easily.
Basic logic of the above
If X is the only cause of Y and not X then not Y.
That you and others try to dance all around this very obviously correct
logic seems quite disingenuous.
X = H stops simulating P
Y = The simulation of P stops
~X = H never stops simulating P
~Y = The simulation of P never stops
I am merely generalizing the the halt deciding principle that overcomes
the pathological self-reference error of the halting theorem.
Truism(3)
Ĥ([Ĥ]) Halts because it aborted the simulation of its input.
Conclusion:
Ĥ is a halting computation and its input is not a halting computation
therefore Ĥ decides its input [Ĥ] as non-halting correctly.
http://www.liarparadox.org/Halting_problem_undecidability_and_infinitely_nested_simulation.pdf
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-05-20 19:07 +0100 |
| Message-ID | <20210520190726.000037df@reddwarf.jmc> |
| In reply to | #2706 |
On Thu, 20 May 2021 12:11:14 -0500
olcott <NoOne@NoWhere.com> wrote:
> This is a {clarification, correction and simplification} of the Peter
> Linz text:
[snip]
>
> Conclusion:
> Ĥ is a halting computation and its input is not a halting computation
> therefore Ĥ decides its input [Ĥ] as non-halting correctly.
Conclusion:
Truisms by definition are self evidently true so if you are having to
explain truisms then Occam's Razor suggests that they are not in fact
truisms and you are barking up the wrong tree. Also, you haven't
refuted Turing until you address the issue of branching logic
predicated on arbitrary program input.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-20 13:36 -0500 |
| Subject | Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ] |
| Message-ID | <qPGdnY_knfeNMTv9nZ2dnUU7-LnNnZ2d@giganews.com> |
| In reply to | #2707 |
On 5/20/2021 1:07 PM, Mr Flibble wrote:
> On Thu, 20 May 2021 12:11:14 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> This is a {clarification, correction and simplification} of the Peter
>> Linz text:
> [snip]
>>
>> Conclusion:
>> Ĥ is a halting computation and its input is not a halting computation
>> therefore Ĥ decides its input [Ĥ] as non-halting correctly.
>
> Conclusion:
> Truisms by definition are self evidently true so if you are having to
> explain truisms then Occam's Razor suggests that they are not in fact
> truisms and you are barking up the wrong tree. Also, you haven't
> refuted Turing until you address the issue of branching logic
> predicated on arbitrary program input.
>
> /Flibble
>
Truisms would not seem self-evidently true to people that are so biased
against a position that they pay almost no attention to what is being said.
Only when a truism is made so obviously correct that rebutting would
seem utterly foolish to most everyone will such a bias be overcome.
Truism(2)
Every simulation of input P that would never halt unless simulating halt
decider H stopped simulating it <is> a non-halting computation. This
remains true even after H stops simulating P.
Any high school student would be able to analyze the basic logic of the
above and know that it is correct very easily.
Basic logic of the above
If X is the only cause of Y and not X then not Y.
X = H stops simulating P
Y = The simulation of P stops
~X = H never stops simulating P
~Y = The simulation of P never stops
Truism(2) generalizes the key halt deciding criteria that overcomes the
pathological self-reference error of the halting theorem.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [standalone]
Back to top | Article view | comp.software-eng
csiph-web