Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > sci.logic > #172303 > unrolled thread
| Started by | Newberry <newberryxy@gmail.com> |
|---|---|
| First post | 2018-02-09 16:19 -0800 |
| Last post | 2018-02-10 16:32 +0000 |
| Articles | 20 on this page of 99 — 9 participants |
Back to article view | Back to sci.logic
What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-09 16:19 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 02:05 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 00:31 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:19 +0000
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-10 18:26 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:19 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 00:15 -0800
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-10 06:49 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 18:23 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 15:37 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:16 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-12 17:40 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-12 20:48 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 04:46 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 14:16 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-13 20:46 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:26 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 13:54 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 15:24 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 00:21 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:36 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 18:05 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:12 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 21:10 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-13 21:35 -0800
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 23:36 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:54 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:00 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-14 08:29 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 10:46 -0600
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:37 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-14 21:49 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:52 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:54 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:52 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 14:05 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 07:02 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 07:09 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:41 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:20 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:56 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:05 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:29 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:35 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:55 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 13:44 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 07:21 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 15:39 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 09:08 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:25 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 11:38 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:49 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 12:03 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:23 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:33 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-16 16:49 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 18:20 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:28 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:55 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:46 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 20:53 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 13:36 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-28 13:22 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-28 15:46 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 20:44 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 15:53 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:29 +0000
Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 08:42 -0500
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:35 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:14 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:10 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:39 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:47 -0800
Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 20:55 -0500
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-14 08:27 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:52 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:47 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:12 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:05 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:53 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:51 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:16 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 08:36 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:14 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:19 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:43 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 16:57 +0000
Re: What is the deal with the Halting Theorem? bursejan@gmail.com - 2018-02-15 09:24 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:58 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:33 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:45 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 02:24 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:18 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 05:32 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 00:30 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 14:07 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-13 18:04 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:06 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 16:32 +0000
Page 1 of 5 [1] 2 3 4 5 Next page →
| From | Newberry <newberryxy@gmail.com> |
|---|---|
| Date | 2018-02-09 16:19 -0800 |
| Subject | What is the deal with the Halting Theorem? |
| Message-ID | <p5ldr4$i7$1@dont-email.me> |
For every decider we can construct a "counter-example", i.e. a program constructed from the decider such that it will do the opposite of what the decider says. So there is no universal decider, right? Right, but there is s decider that can prove that it cannot prove that the counter-example halts. [It cannot prove that the counter-example does not halt.] In fact I claim that there exists a decider that can dichotomize the entire space of programs: either it can prove that P halts on q, or it can prove that it cannot prove that P halts on q. I am 80% sure I am right. Prove me wrong.
[toc] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-10 02:05 +0000 |
| Message-ID | <87h8qpppkf.fsf@bsb.me.uk> |
| In reply to | #172303 |
Newberry <newberryxy@gmail.com> writes:
> For every decider we can construct a "counter-example", i.e. a program
> constructed from the decider such that it will do the opposite of what
> the decider says. So there is no universal decider, right?
Kind of. For every program, there is at least one input that it gets
wrong.
> Right, but
> there is s decider that can prove that it cannot prove that the
> counter-example halts. [It cannot prove that the counter-example does
> not halt.] In fact I claim that there exists a decider that can
> dichotomize the entire space of programs: either it can prove that P
> halts on q, or it can prove that it cannot prove that P halts on q.
>
> I am 80% sure I am right. Prove me wrong.
You are 100% right as has been said time and time again. The use of
words that suggest something not decidable (prove[1]) especially
combined with words that also convey possibility ("can", "cannot"[2])
may be hiding more meaning than I am giving to you words, but taking you
to mean just what a TM does and does not do, then yes.
Example: a TM that examines the state transition function of the input
machine to determine if the graph of the function is acyclic. It can
prove that some machines halt on q and it cannot prove that the rest
halt on q (the answer will be the same for any q).
To illustrate the problem with the words, I have no idea if "cannot
prove that the rest halt on q" is the same as "can prove that it cannot
prove that the rest halt on q".
[1] Is a TM that proves M halts on q any different to one that simply
accepts the input <M,q> pair?
[2] Is what a TM can do any different to what it does? Is what a TM
cannot do any different to what it does not do?
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2018-02-10 00:31 -0600 |
| Message-ID | <9KGdndxfVOk1DOPHnZ2dnUU7-KPNnZ2d@giganews.com> |
| In reply to | #172303 |
On 2/9/2018 6:19 PM, Newberry wrote: > For every decider we can construct a "counter-example", i.e. a program constructed from the decider such that it will do the opposite of what the decider says. Actually I have shown that the execution trace never makes it to the self contradictory part in any of those examples. So there is no universal decider, right? Right, but there is s decider that can prove that it cannot prove that the counter-example halts. [It cannot prove that the counter-example does not halt.] In fact I claim that there exists a decider that can dichotomize the entire space of programs: either it can prove that P halts on q, or it can prove that it cannot prove that P halts on q. > > I am 80% sure I am right. Prove me wrong. -- *∀X True(X) ↔ ∃Γ ⊆ Axioms Provable(Γ, X) *
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-10 12:19 +0000 |
| Message-ID | <87zi4gn69f.fsf@bsb.me.uk> |
| In reply to | #172317 |
Pete Olcott <Pete@NoEmail.address> writes: > On 2/9/2018 6:19 PM, Newberry wrote: >> For every decider we can construct a "counter-example", i.e. a >> program constructed from the decider such that it will do the >> opposite of what the decider says. > > Actually I have shown that the execution trace never makes it to > the self contradictory part in any of those examples. Yet you keep saying that it does! Every time you (incorrectly) claim to define H^ (or H or H^x) by writing those two lines that you don't understand you are explicitly contradicting yourself. Also you never explain why there are two lines, because yo leave off the conditions that give rise to one or the other. It's not wonder you can't take the last step in the proof. As it happens you have not shown anything except deep confusion, but the best way to protect future readers from your comments is probably just to point out that you don't know what you are saying when your write TM configurations and traces. Your should return to "reformulating the essential nature of truth". That's harmless. > So there is no universal decider, right? Right, Your quoting has gone wrong. It looks like you are right but you did not say this. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | George Greene <greeneg@email.unc.edu> |
|---|---|
| Date | 2018-02-10 18:26 -0800 |
| Message-ID | <2b591bf5-0dad-42f0-82ac-1cc68067e53b@googlegroups.com> |
| In reply to | #172317 |
On Saturday, February 10, 2018 at 1:31:11 AM UTC-5, Pete Olcott wrote: > Actually I have shown that the execution trace never makes it to > the self contradictory part in any of those examples. The execution traces DO NOT AND CANNOT HAVE ANY "self-contradictory part"! WHAT part MIGHT THAT BE? You CANNOT show ANYthing about any trace past "H' calls H" because YOU DON'T KNOW ANYTHING ABOUT H! You CAN'T TRACE H! But you CAN reason PAST it because it is part of the HYPOTHESES AND DEFINITION OF THE PROBLEM That H *HALTS*! So to analyze what is happening, you COMPLETELY SKIP the BLACK BOX that is this ARBITRARY TM H (IT DOESN'T MATTER what H does) and simply reason FROM ALL THREE OF the possible outcomes! EITHER 1) H halts yes/true/accept ; 2) H halts no/false/reject ; or 3) H never halts at all. YOU CAN CONTINUE ALL relevant "execution-traces" WITHOUT EVER CARING what happens inside H, and YOU *CAN*NOT* "trace" what happens inside H!
[toc] | [prev] | [next] | [standalone]
| From | peteolcott <peterolcott2@gmail.com> |
|---|---|
| Date | 2018-02-12 09:19 -0800 |
| Message-ID | <f4e21d6a-b175-45db-ad42-265ae703b7ca@googlegroups.com> |
| In reply to | #172389 |
On Saturday, February 10, 2018 at 8:26:52 PM UTC-6, George Greene wrote: > On Saturday, February 10, 2018 at 1:31:11 AM UTC-5, Pete Olcott wrote: > > Actually I have shown that the execution trace never makes it to > > the self contradictory part in any of those examples. > > The execution traces DO NOT AND CANNOT HAVE ANY "self-contradictory part"! > WHAT part MIGHT THAT BE? Translate the Liar Paradox: "This sentence is not True". to Prolog and see what you get. > You CANNOT show ANYthing about any trace past "H' calls H" because > YOU DON'T KNOW ANYTHING ABOUT H! You CAN'T TRACE H! > But you CAN reason PAST it because it is part of the HYPOTHESES AND DEFINITION > OF THE PROBLEM That H *HALTS*! So to analyze what is happening, you > COMPLETELY SKIP the BLACK BOX that is this ARBITRARY TM H (IT DOESN'T MATTER > what H does) and simply reason FROM ALL THREE OF the possible outcomes! > EITHER 1) H halts yes/true/accept ; 2) H halts no/false/reject ; or 3) H never halts at all. YOU CAN CONTINUE ALL relevant "execution-traces" WITHOUT EVER CARING what happens inside H, and YOU *CAN*NOT* "trace" what happens inside H!
[toc] | [prev] | [next] | [standalone]
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-02-10 00:15 -0800 |
| Message-ID | <1a665018-d02a-4b71-be09-ce46310610bd@googlegroups.com> |
| In reply to | #172303 |
On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: > For every decider we can construct a "counter-example", i.e. a program > constructed from the decider such that it will do the opposite of what > the decider says. So there is no universal decider, right? Right, but > there is s decider that can prove that it cannot prove that the > counter-example halts. [It cannot prove that the counter-example does > not halt.] In fact I claim that there exists a decider that can > dichotomize the entire space of programs: either it can prove that P > halts on q, or it can prove that it cannot prove that P halts on q. > > I am 80% sure I am right. Prove me wrong. That's fuzzy logic! Halt Loop Neither but TMs are ENUMERABLE and DETERMINISTIC
[toc] | [prev] | [next] | [standalone]
| From | Newberry <newberryxy@gmail.com> |
|---|---|
| Date | 2018-02-10 06:49 -0800 |
| Message-ID | <p5n0qj$lq$1@dont-email.me> |
| In reply to | #172318 |
grahamcooper7@gmail.com wrote:
> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote:
>> For every decider we can construct a "counter-example", i.e. a program
>> constructed from the decider such that it will do the opposite of what
>> the decider says. So there is no universal decider, right? Right, but
>> there is s decider that can prove that it cannot prove that the
>> counter-example halts. [It cannot prove that the counter-example does
>> not halt.] In fact I claim that there exists a decider that can
>> dichotomize the entire space of programs: either it can prove that P
>> halts on q, or it can prove that it cannot prove that P halts on q.
>>
>> I am 80% sure I am right. Prove me wrong.
>
>
> That's fuzzy logic!
No, that's non-bivalent logic.
> Halt Loop Neither
T F ~T
>
> but TMs are ENUMERABLE and DETERMINISTIC
>
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-10 18:23 +0000 |
| Message-ID | <87bmgwn1oj.fsf@bsb.me.uk> |
| In reply to | #172334 |
Newberry <newberryxy@gmail.com> writes: > grahamcooper7@gmail.com wrote: >> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: >>> For every decider we can construct a "counter-example", i.e. a program >>> constructed from the decider such that it will do the opposite of what >>> the decider says. So there is no universal decider, right? Right, but >>> there is s decider that can prove that it cannot prove that the >>> counter-example halts. [It cannot prove that the counter-example does >>> not halt.] In fact I claim that there exists a decider that can >>> dichotomize the entire space of programs: either it can prove that P >>> halts on q, or it can prove that it cannot prove that P halts on q. >>> >>> I am 80% sure I am right. Prove me wrong. >> >> That's fuzzy logic! > > No, that's non-bivalent logic. > >> Halt Loop Neither > > T F ~T Given that every instance of the halting problem is a computation that either halts or does not halt, which computations do you plan to assign to the "neither" camp? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-02-10 15:37 -0800 |
| Message-ID | <55060dd3-194b-4d98-aba7-f4c5629589f8@googlegroups.com> |
| In reply to | #172355 |
On Sunday, Ben Bacarisse wrote: > >> Halt Loop Neither > > > > T F ~T > > Given that every instance of the halting problem is a computation that > either halts or does not halt, which computations do you plan to assign > to the "neither" camp? Peter Olcott already detailed this to you Ben A transition to H.qn means (1) Not a TM (2) Not a correct TM (3) A Correct TM that would not halt [BEN] Yes!
[toc] | [prev] | [next] | [standalone]
| From | peteolcott <peterolcott2@gmail.com> |
|---|---|
| Date | 2018-02-12 09:16 -0800 |
| Message-ID | <955791b3-0b0c-4b81-8e5d-3f366c1451b6@googlegroups.com> |
| In reply to | #172355 |
On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote: > Newberry writes: > > > grahamcooper wrote: > >> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: > >>> For every decider we can construct a "counter-example", i.e. a program > >>> constructed from the decider such that it will do the opposite of what > >>> the decider says. So there is no universal decider, right? Right, but > >>> there is s decider that can prove that it cannot prove that the > >>> counter-example halts. [It cannot prove that the counter-example does > >>> not halt.] In fact I claim that there exists a decider that can > >>> dichotomize the entire space of programs: either it can prove that P > >>> halts on q, or it can prove that it cannot prove that P halts on q. > >>> > >>> I am 80% sure I am right. Prove me wrong. > >> > >> That's fuzzy logic! > > > > No, that's non-bivalent logic. > > > >> Halt Loop Neither > > > > T F ~T > > Given that every instance of the halting problem is a computation that > either halts or does not halt, which computations do you plan to assign > to the "neither" camp? > > -- > Ben. http://liarparadox.org/index.php/2018/01/18/refutation-of-the-halting-problem-proof/ Therefore H would correctly transition to its H.qn state rejecting the infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the semantic error of Pathological self-reference(Olcott 2004).
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-12 17:40 +0000 |
| Message-ID | <87fu66hzs7.fsf@bsb.me.uk> |
| In reply to | #172493 |
peteolcott <peterolcott2@gmail.com> writes: > On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote: >> Newberry writes: >> >> > grahamcooper wrote: >> >> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: >> >>> For every decider we can construct a "counter-example", i.e. a program >> >>> constructed from the decider such that it will do the opposite of what >> >>> the decider says. So there is no universal decider, right? Right, but >> >>> there is s decider that can prove that it cannot prove that the >> >>> counter-example halts. [It cannot prove that the counter-example does >> >>> not halt.] In fact I claim that there exists a decider that can >> >>> dichotomize the entire space of programs: either it can prove that P >> >>> halts on q, or it can prove that it cannot prove that P halts on q. >> >>> >> >>> I am 80% sure I am right. Prove me wrong. >> >> >> >> That's fuzzy logic! >> > >> > No, that's non-bivalent logic. >> > >> >> Halt Loop Neither >> > >> > T F ~T >> >> Given that every instance of the halting problem is a computation that >> either halts or does not halt, which computations do you plan to assign >> to the "neither" camp? > > Therefore H would correctly transition to its H.qn state rejecting the > infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the > semantic error of Pathological self-reference(Olcott 2004). This is not an answer to my question. I think Newberry does not reply to my posts (for which I am grateful) so I should probably not have phrased it as a question. I should simply have asserted that there are no instances for which the "neither" camp is correct, and then there would have been no question for you to not answer. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2018-02-12 20:48 -0600 |
| Message-ID | <tuednf9IGNVozB_HnZ2dnUU7-IvNnZ2d@giganews.com> |
| In reply to | #172499 |
On 2/12/2018 11:40 AM, Ben Bacarisse wrote: > peteolcott <peterolcott2@gmail.com> writes: > >> On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote: >>> Newberry writes: >>> >>>> grahamcooper wrote: >>>>> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: >>>>>> For every decider we can construct a "counter-example", i.e. a program >>>>>> constructed from the decider such that it will do the opposite of what >>>>>> the decider says. So there is no universal decider, right? Right, but >>>>>> there is s decider that can prove that it cannot prove that the >>>>>> counter-example halts. [It cannot prove that the counter-example does >>>>>> not halt.] In fact I claim that there exists a decider that can >>>>>> dichotomize the entire space of programs: either it can prove that P >>>>>> halts on q, or it can prove that it cannot prove that P halts on q. >>>>>> >>>>>> I am 80% sure I am right. Prove me wrong. >>>>> >>>>> That's fuzzy logic! >>>> >>>> No, that's non-bivalent logic. >>>> >>>>> Halt Loop Neither >>>> >>>> T F ~T >>> >>> Given that every instance of the halting problem is a computation that >>> either halts or does not halt, which computations do you plan to assign >>> to the "neither" camp? >> >> Therefore H would correctly transition to its H.qn state rejecting the >> infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the >> semantic error of Pathological self-reference(Olcott 2004). > > This is not an answer to my question. I think Newberry does not reply > to my posts (for which I am grateful) so I should probably not have > phrased it as a question. I should simply have asserted that there are > no instances for which the "neither" camp is correct, and then there > would have been no question for you to not answer. > H.qy pair of finite strings represent a correct TMD that halts on its input else (1) Not a syntactically correct TMD (2) Not a semantically correct TFD (PSR) error (3) A correct TMD that does not halt. The first two being not a TMD that halts and not a TMD that does not halt, thus neither. -- *∀X True(X) ↔ ∃Γ ⊆ Axioms Provable(Γ, X) *
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-13 04:46 +0000 |
| Message-ID | <87h8qlh4z9.fsf@bsb.me.uk> |
| In reply to | #172541 |
Pete Olcott <Pete@NoEmail.address> writes: > On 2/12/2018 11:40 AM, Ben Bacarisse wrote: >> peteolcott <peterolcott2@gmail.com> writes: >> >>> On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote: >>>> Newberry writes: >>>> >>>>> grahamcooper wrote: >>>>>> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: >>>>>>> For every decider we can construct a "counter-example", i.e. a program >>>>>>> constructed from the decider such that it will do the opposite of what >>>>>>> the decider says. So there is no universal decider, right? Right, but >>>>>>> there is s decider that can prove that it cannot prove that the >>>>>>> counter-example halts. [It cannot prove that the counter-example does >>>>>>> not halt.] In fact I claim that there exists a decider that can >>>>>>> dichotomize the entire space of programs: either it can prove that P >>>>>>> halts on q, or it can prove that it cannot prove that P halts on q. >>>>>>> >>>>>>> I am 80% sure I am right. Prove me wrong. >>>>>> >>>>>> That's fuzzy logic! >>>>> >>>>> No, that's non-bivalent logic. >>>>> >>>>>> Halt Loop Neither >>>>> >>>>> T F ~T >>>> >>>> Given that every instance of the halting problem is a computation that >>>> either halts or does not halt, which computations do you plan to assign >>>> to the "neither" camp? >>> >>> Therefore H would correctly transition to its H.qn state rejecting the >>> infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the >>> semantic error of Pathological self-reference(Olcott 2004). >> >> This is not an answer to my question. I think Newberry does not reply >> to my posts (for which I am grateful) so I should probably not have >> phrased it as a question. I should simply have asserted that there are >> no instances for which the "neither" camp is correct, and then there >> would have been no question for you to not answer. > > H.qy pair of finite strings represent a correct TMD that halts on its input > else > (1) Not a syntactically correct TMD > (2) Not a semantically correct TFD (PSR) error > (3) A correct TMD that does not halt. > > The first two being not a TMD that halts and not a TMD that does not > halt, thus neither. You could do that, but that is not the halting problem. The halting problem (when expressed in terms of string as you prefer) is to decide the set of strings that encode a TM and a string where the TM would halt when given that string. Thus (1) and (3) must be rejected and all other string must be accepted[1]. If you add an extra condition like (2) then you are talking about some other problem which I'll call the PO-problem. As I have said to you (and to Newberry) *that* problem may well have decider. If you have not been talking about the halting problem all this time, then shame on you. You could repair the situation by proving that strings in category (2) are either a decidable set (in which case we are back on track but the theorem still stands) or that they are not a decidable set which, whilst allowing a PO-problem decider to exist, would immediately show that the halting theorem stands. You see the theme? It complicates things, but does not alter the fundamentals of the theorem you object to. So, are string of the form (2) a decidable set or not? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2018-02-13 14:16 -0600 |
| Message-ID | <_9adnVcnyNEZ2h7HnZ2dnUU7-cfNnZ2d@giganews.com> |
| In reply to | #172560 |
On 2/12/2018 10:46 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
>
>> On 2/12/2018 11:40 AM, Ben Bacarisse wrote:
>>> peteolcott <peterolcott2@gmail.com> writes:
>>>
>>>> On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote:
>>>>> Newberry writes:
>>>>>
>>>>>> grahamcooper wrote:
>>>>>>> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote:
>>>>>>>> For every decider we can construct a "counter-example", i.e. a program
>>>>>>>> constructed from the decider such that it will do the opposite of what
>>>>>>>> the decider says. So there is no universal decider, right? Right, but
>>>>>>>> there is s decider that can prove that it cannot prove that the
>>>>>>>> counter-example halts. [It cannot prove that the counter-example does
>>>>>>>> not halt.] In fact I claim that there exists a decider that can
>>>>>>>> dichotomize the entire space of programs: either it can prove that P
>>>>>>>> halts on q, or it can prove that it cannot prove that P halts on q.
>>>>>>>>
>>>>>>>> I am 80% sure I am right. Prove me wrong.
>>>>>>>
>>>>>>> That's fuzzy logic!
>>>>>>
>>>>>> No, that's non-bivalent logic.
>>>>>>
>>>>>>> Halt Loop Neither
>>>>>>
>>>>>> T F ~T
>>>>>
>>>>> Given that every instance of the halting problem is a computation that
>>>>> either halts or does not halt, which computations do you plan to assign
>>>>> to the "neither" camp?
>>>>
>>>> Therefore H would correctly transition to its H.qn state rejecting the
>>>> infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the
>>>> semantic error of Pathological self-reference(Olcott 2004).
>>>
>>> This is not an answer to my question. I think Newberry does not reply
>>> to my posts (for which I am grateful) so I should probably not have
>>> phrased it as a question. I should simply have asserted that there are
>>> no instances for which the "neither" camp is correct, and then there
>>> would have been no question for you to not answer.
>>
>> H.qy pair of finite strings represent a correct TMD that halts on its input
>> else
>> (1) Not a syntactically correct TMD
>> (2) Not a semantically correct TFD (PSR) error
>> (3) A correct TMD that does not halt.
>>
>> The first two being not a TMD that halts and not a TMD that does not
>> halt, thus neither.
>
> You could do that, but that is not the halting problem. The halting
> problem (when expressed in terms of string as you prefer) is to decide
> the set of strings that encode a TM and a string where the TM would halt
> when given that string. Thus (1) and (3) must be rejected and all other
> string must be accepted[1].
This is analogous to requiring a yes or no answer to the following
question: "What time is it (yes or no)?"
Notice that the above question is indeed syntactically correct,
it is only incorrect because of the semantics.
What I am saying here is enormously difficult to understand. I am not
making a mistake, so please do not dismiss what I am saying out-of-hand.
I have spent 7000 hours on this since 1997.
>
> If you add an extra condition like (2) then you are talking about some
> other problem which I'll call the PO-problem.
If the original problem did not have this requirement and (as I have shown)
this requirement is necessary, then I have corrected the error of the original
problem.
> As I have said to
> you (and to Newberry) *that* problem may well have decider. If you have
> not been talking about the halting problem all this time, then shame on
> you.
>
Shame on no one. It is enormously difficult to understand.
> You could repair the situation by proving that strings in category (2)
> are either a decidable set
The whole concept of decidability theory is erroneous because of the
error that I pointed out. This error occurred because prior formal
systems had gaps in their formalization of the underlying semantics.
> (in which case we are back on track but the
> theorem still stands) or that they are not a decidable set which, whilst
> allowing a PO-problem decider to exist, would immediately show that the
> halting theorem stands. You see the theme? It complicates things, but
> does not alter the fundamentals of the theorem you object to.
>
> So, are string of the form (2) a decidable set or not?
>
All of decidability has been defined with inherent semantic incoherence.
I just fixed one key aspect of that problem when I formalized the correct
notion of True and False, as Tarski "proved" was impossible:
An {a priori fact} is an expression X of (natural or formal) language L that has been assigned the semantic property of True.
A set T of {a priori facts} of language L forms the ultimate foundation of the notion of Truth in language L.
To verify that an expression X of language L is True or False only requires a syntactic logical consequence inference chain (formal proof) from X or ~X to one or more elements of T.
Copyright 2017, 2018 Pete Olcott
--
*∀X True(X) ↔ ∃Γ ⊆ Axioms Provable(Γ, X) *
[toc] | [prev] | [next] | [standalone]
| From | Peter Percival <peterxpercival@hotmail.com> |
|---|---|
| Date | 2018-02-13 20:46 +0000 |
| Message-ID | <p5viqg$n42$1@news.albasani.net> |
| In reply to | #172612 |
Pete Olcott wrote: > making a mistake, so please do not dismiss what I am saying out-of-hand. Nothing you say is dismissed out of hand. Your claims have been thoroughly countered for years. If TM states are a problem for you, consider a formulation that makes no use of them. Programs consisting of a finite sequence of numbered statements, each one or other of - PRINT 1 PRINT 0 GO RIGHT GO LEFT GO TO STEP i IF 1 IS SCANNED GO TO STEP i IF 0 IS SCANNED STOP (the above formulation is due to Post) The unsolvability of the halting problem is demonstrable for Post machines too.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2018-02-13 19:26 -0600 |
| Message-ID | <wfadnWO8lMnZDR7HnZ2dnUU7-YGdnZ2d@giganews.com> |
| In reply to | #172613 |
On 2/13/2018 2:46 PM, Peter Percival wrote: > Pete Olcott wrote: > >> making a mistake, so please do not dismiss what I am saying out-of-hand. > > Nothing you say is dismissed out of hand. Your claims have been thoroughly countered for years. > There have not even been attempts at countering my reasoning. > If TM states are a problem for you, consider a formulation that makes no use of them. Programs consisting of a finite sequence of numbered statements, each one or other of - > > PRINT 1 > PRINT 0 > GO RIGHT > GO LEFT > GO TO STEP i IF 1 IS SCANNED > GO TO STEP i IF 0 IS SCANNED > STOP > > (the above formulation is due to Post) > > The unsolvability of the halting problem is demonstrable for Post machines too. -- *∀X True(X) ↔ ∃Γ ⊆ Axioms Provable(Γ, X) *
[toc] | [prev] | [next] | [standalone]
| From | Peter Percival <peterxpercival@hotmail.com> |
|---|---|
| Date | 2018-02-14 13:54 +0000 |
| Message-ID | <p61f29$c8b$1@news.albasani.net> |
| In reply to | #172613 |
Peter Percival wrote: > Pete Olcott wrote: > >> making a mistake, so please do not dismiss what I am saying out-of-hand. > > Nothing you say is dismissed out of hand. Your claims have been > thoroughly countered for years. > > If TM states are a problem for you, consider a formulation that makes no > use of them. Programs consisting of a finite sequence of numbered > statements, each one or other of - > > PRINT 1 > PRINT 0 > GO RIGHT > GO LEFT > GO TO STEP i IF 1 IS SCANNED > GO TO STEP i IF 0 IS SCANNED > STOP > > (the above formulation is due to Post) > > The unsolvability of the halting problem is demonstrable for Post > machines too. I wonder why it is that Turing's formulation remains more popular than Post's? Turing's paper is hard to read (for me, maybe I'm thick) but Post's (it's in the Davis "The undecidable..." collection) is rather clear.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-14 15:24 +0000 |
| Message-ID | <87h8qjbnli.fsf@bsb.me.uk> |
| In reply to | #172697 |
Peter Percival <peterxpercival@hotmail.com> writes: > Peter Percival wrote: <snip> >> The unsolvability of the halting problem is demonstrable for Post machines too. > > I wonder why it is that Turing's formulation remains more popular than > Post's? Turing's paper is hard to read (for me, maybe I'm thick) but > Post's (it's in the Davis "The undecidable..." collection) is rather > clear. Yes, Turing's paper is a bit messy, but then it's presenting quite a few results, the main one being something a bit left-field for modern-day readers (he's interested in machines that /don't/ halt). He also presents a lot of detail because he can't presume the reader will accept any short cuts whereas a modern proof can just say "make a new machine that copes the input". He is also making up terms to refer to things that have become known by other names. The paper talks about macros, jumps and subroutines but using other names. I learned the topic using Minsky machines -- a simple counter machine where the arcs of the state transition diagrams increment and decrement unbounded registers. I thought that was a very simple and clear formalism. Peter Olcott's "lazer-like focus" prevents him from seeing the huge interconnected set of results in this area. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-02-14 00:21 +0000 |
| Message-ID | <87y3jwe6zm.fsf@bsb.me.uk> |
| In reply to | #172612 |
Pete Olcott <Pete@NoEmail.address> writes:
> On 2/12/2018 10:46 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
<snip>
>>> H.qy pair of finite strings represent a correct TMD that halts on its input
>>> else
>>> (1) Not a syntactically correct TMD
>>> (2) Not a semantically correct TFD (PSR) error
>>> (3) A correct TMD that does not halt.
>>>
>>> The first two being not a TMD that halts and not a TMD that does not
>>> halt, thus neither.
>>
>> You could do that, but that is not the halting problem. The halting
>> problem (when expressed in terms of string as you prefer) is to decide
>> the set of strings that encode a TM and a string where the TM would halt
>> when given that string. Thus (1) and (3) must be rejected and all other
>> string must be accepted[1].
>
> This is analogous to requiring a yes or no answer to the following
> question: "What time is it (yes or no)?"
No. That question is nonsense, whereas in contrast, every TM, when run
with some tape, either halts or does not halt. Asking which is the case
is in no way analogous to your question. This analogy has led you
astray for years.
I even know why you think this. You are stuck inside the proof by
contradiction and can't get out because the only way out -- that there
can be no halt decider -- goes against your religious convictions. The
halting instances you think of as "pathological" simply don't exist
because they are all constricted from hypothetical machines that don't
exit. Since you start from the conviction that there must be one of
these hypothesised machines, it's consequences are bound to seem
pathological.
> Notice that the above question is indeed syntactically correct,
> it is only incorrect because of the semantics.
The question of whether a TM halts on some input or other is correct in
every possible sense. Every single such question has a correct yes/no
answer.
<snip>
>> If you add an extra condition like (2) then you are talking about some
>> other problem which I'll call the PO-problem.
>
> If the original problem did not have this requirement and (as I have shown)
> this requirement is necessary, then I have corrected the error of the original
> problem.
A decider that puts any non-halting computations into that category is
not a halt decider. The "pathological" cases can be correctly rejected
only if there are none or they all happen to be halting computations.
Your supposed decider is not a halt decider but a PO-something decider.
>> As I have said to
>> you (and to Newberry) *that* problem may well have decider. If you have
>> not been talking about the halting problem all this time, then shame on
>> you.
>
> Shame on no one. It is enormously difficult to understand.
It's trivial. A halt decider must say which of two things would happen.
One or other of these two things happens for every possible computation.
If you are not talking about that problem, you are talking about
something else.
>> You could repair the situation by proving that strings in category (2)
>> are either a decidable set
>
> The whole concept of decidability theory is erroneous because of the
> error that I pointed out. This error occurred because prior formal
> systems had gaps in their formalization of the underlying semantics.
There is no error. Do you seriously doubt that every computation either
halts or does not halt? Do you really think that asking which happens
is somehow erroneous?
Unless you sort out these basic misunderstandings out, you will be
forever stuck in this rut.
>> (in which case we are back on track but the
>> theorem still stands) or that they are not a decidable set which, whilst
>> allowing a PO-problem decider to exist, would immediately show that the
>> halting theorem stands. You see the theme? It complicates things, but
>> does not alter the fundamentals of the theorem you object to.
>>
>> So, are string of the form (2) a decidable set or not?
>
> All of decidability has been defined with inherent semantic
> incoherence.
Then it is dishonest to pretend that you are using the terms as everyone
else uses them. You should simply accept the theorem because you have
nothing to say about it other than you have redefined the terms.
You need to lead with that. Your first post (when you next come back
again with the same topic) should be that will be talking about the
PO-halting problem about PO-deciders.
> I just fixed one key aspect of that problem when I formalized the correct
> notion of True and False, as Tarski "proved" was impossible:
>
> An {a priori fact} is an expression X of (natural or formal) language
> L that has been assigned the semantic property of True.
>
> A set T of {a priori facts} of language L forms the ultimate
> foundation of the notion of Truth in language L.
>
> To verify that an expression X of language L is True or False only
> requires a syntactic logical consequence inference chain (formal
> proof) from X or ~X to one or more elements of T.
None of that says anything about what other people mean by the halting
theorem. If you have nothing to say about it, just accept it. And stop
pretending that you are talking about the same thing.
--
Ben.
[toc] | [prev] | [next] | [standalone]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | sci.logic
csiph-web