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


Groups > comp.theory > #34030 > 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-21 08:01 -0500
Articles 5 — 3 participants

Back to article view | Back to comp.theory


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
        Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ] Richard Damon <Richard@Damon-Family.org> - 2021-05-21 08:06 -0400
          Re: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ] olcott <NoOne@NoWhere.com> - 2021-05-21 08:01 -0500

#34030 — 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]


#34032

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-05-20 19:07 +0100
Message-ID<20210520190726.000037df@reddwarf.jmc>
In reply to#34030
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]


#34035 — 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#34032
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] | [next] | [standalone]


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

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-21 08:06 -0400
SubjectRe: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ]
Message-ID<znNpI.109011$b27.60025@fx03.iad>
In reply to#34035
On 5/20/21 2:36 PM, olcott wrote:
> 
> 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.
> 


A Truism to really be a Truism, is so blatantly true that it will be
accepted by ANYONE, even against bias.

If someone IS so biased as reject what you think of as a Truism, then
the answer is to stop and actually PROVE the Truism.

Truism are NOT axiom, which are just taken to be true, but are actually
provable by their meaning.

Your statements that you are calling 'Truisms' aren't that. The mere
fact that you have had to adjust them says that they aren't Truisms.

They are ASSERTIONS you are making, and you should be able to prove them
if they are true. (well, a competent logician could if they were true).
The act of proving them also would fix up some of the looseness in their
definitions, which is one of the problems with them.

Fundamentally, your issue seems to be that you have some ideas of how
logic should work, you want to be able to make the wide reaching
statement that ALL Truth is Provable, and you have seen too many proofs
that show that this Halting Problem is one of the cornerstones that make
it easy to show that there are some Truths that are not actually Provable.

I don't think you know enough logic to actually make a proper formal
proof of anything of this level. You seem to have an understanding of a
lot of the terminology and symbology of the field, but NOT a firm
foundational knowledge of how to work in it.

You CLAIM that everything has an solid analytical proof of it, yet you
have yet to provide ANY real Analytical proof of anything. You will
claim by Axiom/Truism a statement that it close to what you what to say
and then using Rhetorical Arguments that this proves your case.

The stuff you want to claim is way more complicated than what is really
taken as the fundamental axioms of logic, maybe like what an intro
course might provide as 'starting points'.

You then like to play with the meaning of words and symbols altering
their meaning as you go. Proofs are NOT like a computer program, I can't
start and say let X = 1 and one point, and then later say, now let X =
2, especially if I then try to use that I showed that X*Y = Y
originally, so that still holds.

You need to learn the rules of the systems you are trying to work in.
There is a reason Turing Machines were created to talk about Computation
Theory, they fundamentally work in a way that matches the rules of the
Theory. I don't thnk you really understand how a Turing Machine works,
and how it is different from the computers you are used to in normal
programming. The Turing Equivalence Theory has a major limitation on it,
it only applies to things that meet Computation Theory's definition of a
'Computation', and many programs, and especially sub-programs don't meet
that requrement, at least not in the normal manner of looking at it.

[toc] | [prev] | [next] | [standalone]


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

Fromolcott <NoOne@NoWhere.com>
Date2021-05-21 08:01 -0500
SubjectRe: Halting theorem refutation (Three irrefutable truisms lead to one conclusion)(V2)[ Truism(2) ]
Message-ID<idydnbPvvNV4Mzr9nZ2dnUU7-U-dnZ2d@giganews.com>
In reply to#34063
On 5/21/2021 7:06 AM, Richard Damon wrote:
> On 5/20/21 2:36 PM, olcott wrote:
>>
>> 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.
>>
> 
> 
> A Truism to really be a Truism, is so blatantly true that it will be
> accepted by ANYONE, even against bias.
> 
> If someone IS so biased as reject what you think of as a Truism, then
> the answer is to stop and actually PROVE the Truism.
> 
> Truism are NOT axiom, which are just taken to be true, but are actually
> provable by their meaning.
> 
> Your statements that you are calling 'Truisms' aren't that. The mere
> fact that you have had to adjust them says that they aren't Truisms.
> 
> They are ASSERTIONS you are making, and you should be able to prove them
> if they are true. (well, a competent logician could if they were true).
> The act of proving them also would fix up some of the looseness in their
> definitions, which is one of the problems with them.
> 
> Fundamentally, your issue seems to be that you have some ideas of how
> logic should work, you want to be able to make the wide reaching
> statement that ALL Truth is Provable, and you have seen too many proofs
> that show that this Halting Problem is one of the cornerstones that make
> it easy to show that there are some Truths that are not actually Provable.
> 
> I don't think you know enough logic to actually make a proper formal
> proof of anything of this level. You seem to have an understanding of a
> lot of the terminology and symbology of the field, but NOT a firm
> foundational knowledge of how to work in it.
> 
> You CLAIM that everything has an solid analytical proof of it, yet you
> have yet to provide ANY real Analytical proof of anything. You will
> claim by Axiom/Truism a statement that it close to what you what to say
> and then using Rhetorical Arguments that this proves your case.
> 
> The stuff you want to claim is way more complicated than what is really
> taken as the fundamental axioms of logic, maybe like what an intro
> course might provide as 'starting points'.
> 
> You then like to play with the meaning of words and symbols altering
> their meaning as you go. Proofs are NOT like a computer program, I can't
> start and say let X = 1 and one point, and then later say, now let X =
> 2, especially if I then try to use that I showed that X*Y = Y
> originally, so that still holds.
> 
> You need to learn the rules of the systems you are trying to work in.
> There is a reason Turing Machines were created to talk about Computation
> Theory, they fundamentally work in a way that matches the rules of the
> Theory. I don't thnk you really understand how a Turing Machine works,
> and how it is different from the computers you are used to in normal
> programming. The Turing Equivalence Theory has a major limitation on it,
> it only applies to things that meet Computation Theory's definition of a
> 'Computation', and many programs, and especially sub-programs don't meet
> that requrement, at least not in the normal manner of looking at it.
> 

Please take a look at [Halting theorem refutation (V4)]

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [standalone]


Back to top | Article view | comp.theory


csiph-web