Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #34030 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-05-20 12:11 -0500 |
| Last post | 2021-05-21 08:01 -0500 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.theory
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
| 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 | #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]
| 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 | #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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-21 08:06 -0400 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-21 08:01 -0500 |
| Subject | Re: 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