Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.software-eng > #2706 > unrolled thread

Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)

Started byolcott <NoOne@NoWhere.com>
First post2021-05-20 12:11 -0500
Last post2021-05-20 13:36 -0500
Articles 3 — 2 participants

Back to article view | Back to comp.software-eng


Contents

  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

#2706 — Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)

Fromolcott <NoOne@NoWhere.com>
Date2021-05-20 12:11 -0500
SubjectHalting 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]


#2707

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-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]


#2708 — Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-20 13:36 -0500
SubjectRe: 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