On 04/05/2025 01:20, Mike Terry wrote:
On 03/05/2025 20:45, Richard Heathfield wrote:
<snip>
>
I am conscious that you have already explained to me (twice!) that Mr O's approach is aimed not at overturning the overarching indecidability proof but a mere detail of Linz's proof. Unfortunately, your explanations have not managed to establish a firm root in what passes for my brain.
Third time's a charm, I think, or at least I'm further forward. (See question about a mile VVVVVsouthVVVVV of here.)
In case I ever bail again, you have my full permission to remind me of <~/alldata/usenet/M_Terry_explains_olcott_reasoning.eml> where I have saved your reply for future re-enlightenment.
This may be because I'm too dense to grok them, or possibly it's because your explanations are TOAST (see above).
Turned out to be 50/50.
I generally think I post way too much,
I think Usenauts are best measured by their S/N ratio. That is, it's what you post rather than how much there is of it.
and tend to wander off topic with unnecessary background and so on,
Isaac Asimov was always at his happiest when starting an essay with the magic words "The Ancient Greeks..." In 1965 he wrote a book to be called "The Neutrino". He spent the first three quarters or so of the book on what he considered to be /necessary/ background, and Chapter 500-or-so is called "Enter The Neutrino". When he got the proofs back for checking, he saw that his copy editor had pencilled into the margin "AT LAST!"
and probably I write too much from a "maths" perspective, because that's my background. Not sure if I can change any of that! :) Just ask if I use obscure notation or let me know if I'm going too fast/slow. Part of the problem is I don't know your background and what things you're super familiar with.
ISTR that I have recently gone on record as claiming (when asked if I have ever done any programming) to be a professional potato painter. The claim is rather less accurate than I generally try to be, and whilst it is true that I am super familiar (and perhaps too familiar) with potatoes, I haven't actually painted one since infants' school.
My background? Unfortunately my potato-painting career never really took off, so I decided instead to earn my corn writing computer programs for a living.
Any good?
Well, maybe, maybe not. But I'll let my peers answer that one, if I can find some for you.
They say you should never Google yourself because you might not like what you read. But what the hell, yeah? My seventh hit was for an ancient Usenet thread entitled "Richard HeathField. Bad ideas!" in which I am severely taken to task by a chap called "paulcr". It makes an entertaining read. His beef is with my claim that there's no /one/ way to do non-blocking input that can be guaranteed to work.
https://groups.google.com/g/comp.lang.c.moderated/c/W9ViD37NpzEI would draw your attention not so much to my accuser as to the counsel for the defence. Doug Gwyn's name, for example, can be found in the acknowledgements section of K&R, and Francis Glassborow was for many years the chairman of the Association of C and C++ Users.
Or if you prefer pictures, here's one I prepared earlier. Figuring out what it does is easy - suck it and see the Olcott way. Figuring out how it works, though, is a touch more challenging, and I leave it as an exercise with which to while away a Sunday morning:
#include <stdlib.h>
#include <stdio.h>
#define O int
#define B main
#define F char
#define U if
#define S atoi
#define C for
#define A putchar
#define T '*'
#define E ' '
#define D '\n'
#define c ==
#define o =
#define d ++
#define e return
#define r ||
O
B (
O k
, F
* v
[ ]
) {
O i
, j = 9
; U ( k > 1
) { j = S
( v [ 1
] ) ; }
U ( ! (
j > 0 )
) { j =
5 ; } U ( (
j & 1 ) c 0 ) {
d j ; } C (
i = 0 ;
i < j * j
; A ( i / j
c ( 3 * j
) / 2 -
( i % j + 1
) r i / j c j /
2 - i % j r
i / j c
j / 2 +
i % j r
i / j c
i % j -
j / 2 ? T
: E ) , i d
, i % j
c 0
? A
( D
) :
0 )
; e
0 ;
}
You have said, I think, that Olcott doesn't need a universal decider in order to prove his point. But a less ambitious decider doesn't contradict Linz's proof, surely? So once more for luck, what exactly would PO be establishing with his non-universal and impatient simulator if he could only get it to work?
Yes. PO is aiming to refute the /proof method/ that Linz (and similar) proofs use, i.e. to attack the /reasoning/ behind the proof. In effect, he is saying that his HHH/DD provide a counter-example to that reasoning. His HHH/DD are not full halt deciders - they're /partial/ halt deciders but that would be enough. I cover what a partial HD is below, and why it is enough for his argument [..if HHH/DD worked as originally claimed..]
Okay. Nous sommes getting somewhere (or should that be someou?)
If he was successful with his HHH/DD programs, it would mean the Linz proof contained some logical error, and so the conclusion of the proof (the HP theorem) would not be warranted /by that proof/, We would have to cross that proof out of our Master Book Of Mathematical Theorems And Their Proofs! As there are other proofs of the theorem, the theorem itself could remain.
It would be like the following scenario: there are many alternative proofs of Pythagorus' Theorem, but let's imagine that one of them - the "MikeT" proof - is the first one taught to all school children across the world, and it's been that way for the last 50 years. Suddenly PO finds a flaw in that proof! Sure, there are other proofs without that flaw so we still trust Pythagorus' Theorem, but we're not going to continue teaching children an incorrect proof of it, right. So finding such a flaw would force many changes on our education system and be highly interesting in its own right.
Okay, so maybe Linz's formulation is a bigger deal than I have been giving it credit for. (BTW ITYM Pythagoras. Spelling schmelling, sure, but I do think that names are important.)
This doesn't explain exactly how PO's HHH/DD would "refute" the Linz proof, so that's what the rest of the post tries to do.
Cue three descending chords, with just a hint of tremolo...
BTW, when I refer to "the Linz proof" it is purely because the Linz book is apparently the one that PO has access to, and when he started posting here he claimed to have refuted the "Linz" proof that appears in that book. As you suspect, the proof is nothing to do with Linz other than appearing in his book!
I am reminded of Hellin's Law, which documents the as yet unexplained fact that for n>1, n-tuple births occur once in 89^{n-1} pregnancies. In 1895, Hellin wrote down what biologists and demographers had already known for years. This penmanship appears to be his only contribution to the matter, and yet... Hellin's Law.
It also appears I expect in some form in most computer science books covering computation theory, because it's so well known. Hmm, not sure who discovered it, but it would be one of the big guys like Turing, Church, Kleene,... all doing related work in the early days of the field.
Turing, I think., in 1936.
ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO
THE ENTSCHEIDUNGSPROBLEM
I have a 2MB PDF copy. I can't remember where I found it but, if you want it, drop me an email and I'll send it by return.
So to say what PO's code would refute, I need to explain exactly how the Linz proof works. Sorry if you already perfectly clear on that!
I'm fine with the general idea of the proof. If we have a universal decider U we can (easily!) use it to make a program that it can't decide, and we have reductio QED.
<snipped but not skipped>
This next bit might be a missing key for you... Looking at the above, we started by me giving you a "halt decider" H. What if I only gave you a lesser achievement: a "partial halt decider" that correctly decides halting for certain (P,I) inputs, but fails to halt for all the rest?
What's to stop the partial decider from deciding pseudorandomly? For example: hashing the input tapes and deciding according to the hash modulo 2? This would:
1) always decide (as required);
2) sometimes get it right (as required);
3) sometimes get it wrong (as required if it's to be only 'partial');
4) always make the same decision when given the same input (clearly desirable);
5) be trivial to write;
6) would step around all the simulation nonsense and puncture about 99% of the current quarrel.
7) It could obviously be arranged if need be to interpret the hash mod 2 so that when fed itself as input it gets itself (a) right or (b) wrong.
Clearly this won't do, because surely /somebody/ would have pointed it out by now, but... /why/ won't it do?
The answer is the same logic still applies, but the conclusion is slightly different:
- I give you a /partial/ HD H
- You follow the same instructions to create the new TM, H^
- The same reasoning of the Linz proof shows that my H does not correctly decide halting
for the case of TM H^ running against input <H^>
a) If H decides HALTS, we can show H^(<H^>) never halts
b) If H decides NEVER_HALTS, we can show H^(<H^>) halts
c) If H fails to decide (i.e. it loops) then H^(<H^>) never halts
This last possibility is new, because H is only a partial halt decider
Now we can look at what PO claims to have: a *partial* halt decider H, which CORRECTLY decides its corresponding input (<H^>,<H^>). Specifically, he claims his H decides NEVER_HALTS, and that indeed H^(<H^>) never halts. This contradicts the Linz proof /reasoning/ which lead to (b) above.
Since the Linz proof reasoning would have been shown to reach a false conclusion [in the case of PO's HHH/DD programs], the reasoning must be wrong somewhere, and if the reasoning is wrong it can't be used in the Linz proof. It is ok here that H is only a partial halt decider - in fact the above only requires that PO's H correctly decides the one H^(<H^>) case to get the contradiction.
Er, that's it!
Just as a reminder I'll repeat the final outcome of all this:
- PO's H does decide NEVER_HALTS for TM H^ running with input <H^>.
- PO's H^ running with input <H^> in fact halts, in line with Linz logic (b) above.
...and so there's nothing to see.
A final observation - nothing in this post is anything to do with "simulation". That comes later looking at how PO's H supposedly works...
Got it... ish.
I suspect that I'll be re-reading your reply for some time to come.
-- Richard HeathfieldEmail: rjh at cpax dot org dot uk"Usenet is a strange place" - dmr 29 July 1999Sig line 4 vacant - apply within
Re: Refutation of Turing’s 1936 Halting Problem Proof Based on Self-Referential Conflation as a Category (Type) Error
Re: Refutation of Turing’s 1936 Halting Problem Proof Based on Self-Referential Conflation as a Category (Type) Error
