Re: [PO] Halting Problem Final Conclusion
Amr Sabry
> with every time it answers "I don't know". How many times are you
> going to accept "I don't know" for an answer before deciding on the
> silliness of the ides.
There is a LOT of work on termination analysis. See for example
Andreas Abel publications, especially "Termination Checking with
Types."
http://www.tcs.informatik.uni-muenchen.de/~abel/publications.html
The fact that such analyses must be conservative, and may reject some
terminating programs, does not render them useless. --Amr
Abdulaziz Ghuloum
Right. There are many ways of forcing termination. A language that
allows primitive recursion only (eg. Hofstadter's BLooP: bounded loops
and no recursive calls) is such decidable language. It is not useless.
Another system may reject all non-halting programs as well as some
programs that do actually halt (and in these cases, one can modify the
program to convince the checker that it does halt).
The thread was initially about the general halting problem (for TMs)[1].
It quickly turned into C by G.Frege's while(1); example.
How would you describe a halt analyzer for TMs if it's allowed to return
"I Don't Know" in addition to "Halts" and "Doesn't Halt"?
Aziz,,,
[1] Actually, Peter did say that he's not talking about solving the
halting problem, but I had no idea what he was talking about if it was
not the halting problem. He never replied to my question.
Peter Olcott
"Abdulaziz Ghuloum" <aghu...@c-s-remove-dashes.indiana.edu> wrote in message news:chg6sc$bue$1...@hood.uits.indiana.edu...
> Peter Olcott wrote:
> > I am not talking about solving the halting problem.
>
> What are you talking about then?
>
> > There are three possible cases for the Halt Analyzer
> > to report:
> > (1) Halts
> > (2) Does Not Halt
> > (3) I Don't Know
> >
> > Simply treat "I Don't Know" as another form of error,
> > as if it was "Does Not Halt". Although there could be
> > some cases where "I Don't Know" is not an error,
> > all the cases where "Halts" is reported can be correct.
>
> Hmmm. So, is the following code a valid Halt Analyzer function:
>
> HaltResult Analyze(Program code){
> return I_DONT_KNOW; // always reporting case (3) above
> }
>
> To me, it seems perfectly valid (according to your definition) and
> completely useless.
This is (of course) not what I intended.
What I intended is that the progression of the technology
of the automatic detection of programming errors can for
all practical purposes circumvent the Halting Problem.
Peter Olcott
"Marc Goodman" <marc.g...@comcast.net> wrote in message news:XxS_c.138729$mD.52502@attbi_s02...
> Abdulaziz Ghuloum wrote:
> > For me, the usefulness of this halt anayzer diminishes exponentially
> > with every time it answers "I don't know". How many times are you going
> > to accept "I don't know" for an answer before deciding on the silliness
> > of the ides.
>
> Powerpoint, Access, Outlook, Lotus Notes, and some other apps.
> It would be _very_helpful_ to me if I had some way of telling whether
> these programs were infinite looping or _just_taking_a_REALLY_long_time.
> I'd be pretty happy, even if it didn't work for, say, LoopIfHalts.
>
> So, in the real world, I'd be willing to take "I don't know" for an
> answer sometimes.
> --
> I have found that the supernatural power of faith can overcome
> great obstacles: Apparently analytical truth is not one of them.
> - Peter Olcott on comp.theory
>
You forget to mention that other crucial half of
my statement. I will paraphrase because I don't
remember the exact words, for math sometimes
intuition is incorrect. Ultimately I counted much more
on intuition than faith. I was having faith that my intuition
was correct.
Robert Low
Peter Olcott <olc...@worldnet.att.net> wrote:
><news...@comcast.net> wrote in message
>> In comp.theory Peter Olcott <olc...@worldnet.att.net> wrote:
>> > of error. If the Halting Problem is redefined (which does not
>> > refute anyone), then this redefined problem can be easily
>> > solved.
>> Sigh.... two steps forward, one step back....
>I am not talking about solving the halting problem.
Oh, OK. So you've changed the question, and allowed
'Don't know' as one possible answer. I guess that
you have then proved that a different problem can
'solved' by an algorithm that doesn't always tell
you the answer. Why is this interesting?
Peter Olcott
"Robert Low" <mtx...@linux.services.coventry.ac.uk> wrote in message news:chhav1$b2g$1...@sunbeam.coventry.ac.uk...
It is far better than simply not bothering to attempt
to solve any aspect of the problem at all. Realistically,
how often would a function such as LoopIfHalts be
inadvertently encoded within an application?
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>
><news...@comcast.net> wrote in message news:ybK_c.298530$eM2.241548@attbi_s51...
>> In comp.theory Peter Olcott <olc...@worldnet.att.net> wrote:
>> > The Liar Paradox can be shown to be nothing more than
>> > a incorrectly formed statement because of its pathological
>> > self-reference. The Halting Problem can only exist because
>> > of this same sort of pathological self-reference.
>> >
>> > The primary benefit of solving the Halting Problem was to
>> > detect programs that failed to halt, thus were incorrect.
>> > Pathological self-reference can also be viewed as a form
>> > of error. If the Halting Problem is redefined (which does not
>> > refute anyone), then this redefined problem can be easily
>> > solved.
>> >
>> > Now we have three possible correct results:
>> > (a) Halts
>> > (b) Does Not Halt
>> > (c) Pathological Self Reference to Halt
>> >
>> > Compared to my prior claims, this one seem trivial and
>> > obvious. Possibly this claim adds a slight nuance to the
>> > problem that has not been widely discussed before.
>> > If we construe pathological self-reference as another
>> > error condition, then this does remove the impossibility
>> > of creating a useful tool.
>>
>> Sigh.... two steps forward, one step back....
>>
>> Even if you could sensibly and unambiguously define what you mean by a
>> "pathological self reference to halt", it wouldn't do you any good.
>> There's no program that can "solve the halting problem" by simply
>> trying to eliminate these self-referencial cases -- you still couldn't
>> give the correct halts/doesn't-halt answer in all the other cases.
>
>I am not talking about solving the halting problem.
>There are three possible cases for the Halt Analyzer
>to report:
>(1) Halts
>(2) Does Not Halt
>(3) I Don't Know
>
>Simply treat "I Don't Know" as another form of error,
>as if it was "Does Not Halt". Although there could be
>some cases where "I Don't Know" is not an error,
>all the cases where "Halts" is reported can be correct.
now we don't know what a correct solution to your
modified problem is. because you've -never- answered
the following simple question: -does- a routine that
always returns "don't know" count as a correct solution?
that's a yes or no question - you should really reply
to it some time, because it's a question about exactly
what altered problem -you- are talking about.
[hint: it's obvious to everyone why you continually
refuse to answer the question: if you say yes then
your new improved halting problem is utterly dumb,
while if you say no then it's clear you have not
yet specified the problem you're talking about.
you should really answer the question so we know
which case holds.]
>> But I'm not getting into this again. Read those books you ordered and
>> learn what you can.
>>
>> --
>>
>> That's News To Me!
>> news...@comcast.net
>
************************
David C. Ullrich
sorry about the inelegant formatting - typing
one-handed for a few weeks...
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>
>"Abdulaziz Ghuloum" <aghu...@c-s-remove-dashes.indiana.edu> wrote in message news:chg6sc$bue$1...@hood.uits.indiana.edu...
>> Peter Olcott wrote:
>> > I am not talking about solving the halting problem.
>>
>> What are you talking about then?
>>
>> > There are three possible cases for the Halt Analyzer
>> > to report:
>> > (1) Halts
>> > (2) Does Not Halt
>> > (3) I Don't Know
>> >
>> > Simply treat "I Don't Know" as another form of error,
>> > as if it was "Does Not Halt". Although there could be
>> > some cases where "I Don't Know" is not an error,
>> > all the cases where "Halts" is reported can be correct.
>>
>> Hmmm. So, is the following code a valid Halt Analyzer function:
>>
>> HaltResult Analyze(Program code){
>> return I_DONT_KNOW; // always reporting case (3) above
>> }
>>
>> To me, it seems perfectly valid (according to your definition) and
>> completely useless.
>
>This is (of course) not what I intended.
ah, at last an answer. [there's no 'of course' about it, btw,
for two reasons: first, you've said many things equally
ridiculous, and second you've told us many times that we
should -not- try to figure out what you intended but read
exactly what you wrote. if we read exactly what you wrote
it looks like the above -is- what you intended.]
what -did- you intend then?
>What I intended is that the progression of the technology
>of the automatic detection of programming errors can for
>all practical purposes circumvent the Halting Problem.
huh? that's not remotely like something that can be
given a logical proof.
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>
>"Robert Low" <mtx...@linux.services.coventry.ac.uk> wrote in message news:chhav1$b2g$1...@sunbeam.coventry.ac.uk...
>>
>> Peter Olcott <olc...@worldnet.att.net> wrote:
>> ><news...@comcast.net> wrote in message
>> >> In comp.theory Peter Olcott <olc...@worldnet.att.net> wrote:
>> >> > of error. If the Halting Problem is redefined (which does not
>> >> > refute anyone), then this redefined problem can be easily
>> >> > solved.
>> >> Sigh.... two steps forward, one step back....
>> >I am not talking about solving the halting problem.
>>
>> Oh, OK. So you've changed the question, and allowed
>> 'Don't know' as one possible answer. I guess that
>> you have then proved that a different problem can
>> 'solved' by an algorithm that doesn't always tell
>> you the answer. Why is this interesting?
>>
>> --
>> Rob. http://www.mis.coventry.ac.uk/~mtx014/
>
>It is far better than simply not bothering to attempt
>to solve any aspect of the problem at all.
huh?????? who told you that nobody was trying to solve
any aspect of the problem?
>Realistically,
>how often would a function such as LoopIfHalts be
>inadvertently encoded within an application?
it's like you have no memory at all, the way you
continually imply that this is the only problem.
realistically, consider the following:
def divides(a, b):
return (b%a)==0
def perfect(n):
s = 0
for d in range(1,n):
if divides(d,n):
s = s + d
return s==n
def findOddPerfect():
n = 3
while 1:
if perfect(n):
return n
n = n + 2
findOddPerfect()
does that halt or not? realistically, does
it contain something like loopifhalts?
Robert Low
Peter Olcott <olc...@worldnet.att.net> wrote:
>"Robert Low" <mtx...@linux.services.coventry.ac.uk> wrote in message
>> 'Don't know' as one possible answer. I guess that
>> you have then proved that a different problem can
>> 'solved' by an algorithm that doesn't always tell
>> you the answer. Why is this interesting?
>to solve any aspect of the problem at all. Realistically,
That's what I'm asking you to justify. For example,
I can easily write such a 'halt analyser' for a
language whose repetition constructs are limited to
a 'for' loop and a 'while' loop. If it doesn't have
a 'while' statement, return 'halts': if it does,
return 'don't know'. This is not particularly
interesting, though it is true.
So, since you've apparently accepted that a halt
analyser cannot be constructed, and are falling
back to the (admittedly interesting) question of
just how good a job *can* be done, what do you
have to say about that problem?
>how often would a function such as LoopIfHalts be
>inadvertently encoded within an application?
There is no such function as LoopIfHalts; LoopIfHalts
is a function whose existence is implied by the existence
of a halt analyser, and which provides the contradiction
to show that a halt analyser cannot in fact exist.
G. Frege
<marc.g...@comcast.net> wrote:
>
> So, in the real world, I'd be willing to take "I don't know" for an
> answer sometimes.
>
Same for me.
F.
G. Frege
<aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
> The thread was initially about the general halting problem (for TMs)[1].
> It quickly turned into C by G.Frege's while(1); example.
>
Huh???
But it was YOU who started this argument.
Quote:
-------------------------------------------------------------
Hmmm. So, is the following code a valid Halt Analyzer function:
HaltResult Analyze(Program code){
return I_DONT_KNOW; // always reporting case (3) above
}
To me, it seems perfectly valid (according to your definition) and
completely useless.
-------------------------------------------------------------
Of course, I'm NOT talking about C here, but just some program code (in
some declarative language).
Hence my little (demo) program also might be:
:
100 goto 100
:
or
:
do
while TRUE
:
or whatever. (Of course I do assume that this code is reached in the
flow of the program. :-)
>
> Actually, Peter did say that he's not talking about solving the
> halting problem, but I had no idea what he was talking about if
> it was not the halting problem.
>
See comments above. The question simply might be: does this program/code
halt or not?
And the ANSWER then might be (one of):
Yes
No
Don't know / Can't say
This way, the answer m a y always be correct/acceptable. If you ONLY had
the possibilities
Yes
No
The answer WOULD HAVE TO BE w r o n g in some cases (or the Halt
Analyzer just would loop itself, also not that a favorable outcome).
F.
G. Frege
<olc...@worldnet.att.net> wrote:
> > >
> > > There are three possible cases for the Halt Analyzer
> > > to report:
> > >
> > > (1) Halts
> > > (2) Does Not Halt
> > > (3) I Don't Know
> > >
> > Hmmm. So, is the following code a valid Halt Analyzer function:
> >
> > HaltResult Analyze(Program code){
> > return I_DONT_KNOW; // always reporting case (3) above
> > }
> >
> > To me, it seems perfectly valid (according to your definition) and
> > completely useless.
> >
> This is (of course) not what I intended.
> What I intended is that the progression of the technology
> of the automatic detection of [certain] programming errors
> can for all practical purposes [succeed].
>
Well, let's say "for /many/ practical purposes", or even "for /most/
practical purposes", etc. This certainly might be possible, some day (or
not - but it's not _excluded_ by a rigorous proof, to my knowledge.)
As others have pointed out:
Quote:
-------------------------------------------------------------
There is a LOT of work on termination analysis. See for example
Andreas Abel publications, especially "Termination Checking with
Types."
http://www.tcs.informatik.uni-muenchen.de/~abel/publications.html
The fact that such analyses must be conservative, and may reject some
terminating programs, does not render them useless. --Amr
-------------------------------------------------------------
F.
G. Frege
Low) wrote:
> >
> > I am not talking about solving the halting problem.
> >
> Oh, OK. So you've changed the question, and allowed
> 'Don't know' as one possible answer.
>
Right. Good idea, imho. If you c a n't answer a question, say so!
>
> Why is this interesting?
>
Why not?
F.
G. Frege
<ull...@math.okstate.edu> wrote:
> >
> > What I intended is that the progression of the technology
> > of the automatic detection of [some] programming errors can
> > for [many/most] practical purposes [succeed].
> >
> huh? that's not remotely like something that can be
> given a logical proof.
>
On the other hand, at least it's not _excluded_ by a rigorous proof (to
to my knowledge). Hence it m i g h t be possible.
As others have pointed out:
Quote:
-------------------------------------------------------------
There is a LOT of work on termination analysis. See for example
Andreas Abel publications, especially "Termination Checking with
Types."
http://www.tcs.informatik.uni-muenchen.de/~abel/publications.html
The fact that such analyses must be conservative, and may reject some
terminating programs, does not render them useless. --Amr
-------------------------------------------------------------
F.
P.S.
Is there a p r o o f that AI is "possible", c a n there be such a
proof? (Don't think so.) So what?
G. Frege
Low) wrote:
>
> I can easily write such a 'halt analyser' for a
> language whose repetition constructs are limited to
> a 'for' loop and a 'while' loop. If it doesn't have
> a 'while' statement, return 'halts': if it does,
> return 'don't know'. This is not particularly
> interesting, though it is true.
>
Fine, this proves that there IS a solution.
And since it c a n be done, one certainly might ask IF it can be done
better (than that). I guess, the answer is yes.
F.
Robert Low
You misunderstand---though that may well be my fault. I didn't mean
'Why is interesting to have something that works some of the
time?'; I meant 'What interesting things do you [Peter Olcott]
have to say about this problem?' There is an easy algorithm that
never gives a wrong answer, but also never gives a useful one,
for example. I'd be surprised if he had anything even that good
to offer. (Pleasantly surprised, but surprised.)
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
G. Frege
<ull...@math.okstate.edu> wrote:
>>>
>>> Oh, OK. So you've changed the question, and allowed
>>> 'Don't know' as one possible answer. I guess that
>>> you have then proved that a different problem can
>>> 'solved' by an algorithm that doesn't always tell
>>> you the answer. Why is this interesting?
>>>
>>> Rob.
>>
>> It is far better than simply not bothering to attempt
>> to solve any aspect of the problem at all.
>>
>> [...]
>>
> realistically, consider the following:
>
> def divides(a, b):
> return (b%a)==0
>
> def perfect(n):
> s = 0
> for d in range(1,n):
> if divides(d,n):
> s = s + d
> return s==n
>
> def findOddPerfect():
> n = 3
> while 1:
> if perfect(n):
> return n
> n = n + 2
>
> findOddPerfect()
>
> does that halt or not?
>
Quote:
-------------------------------------------------
[...] Idea: when the routine (your Halt Analyzer) is started, it calls a
timer. And then tries to find out if the considered program halts or
doesn't halt. If the timer interrupts that procedure after some time, it
might just return "I Don't Know".
But that just means (again) the Haling Problem is (still) not solved.
(Right, it c a n't be solved, as Turing has shown.)
F.
P.S.
Reporting "I Don't Know" would NOT be an error in this case: it simply
states the fact that the Halt Analyzer was not able to detect "Halts" /
"Does Not Halt" _in a given amount of time_. I really like your proposal
(of 3 possible answers): it's certainly the best we can hope for
concerning the (solution of the) "Halting Problem". (Not sure if the
"Timer Device" can be implemented with a TM - I guess not.)
-------------------------------------------------
F.
P.S.
Quote:
-------------------------------------------------
...the ANSWER then might be (one of):
Yes
No
Don't know / Can't say
This way, the answer m a y always be correct/acceptable. If you ONLY had
the possibilities
Yes
No
The answer WOULD HAVE TO BE w r o n g in some cases (or the Halt
Analyzer just would loop itself, also not that a favorable outcome).
-------------------------------------------------
G. Frege
<ull...@math.okstate.edu> wrote:
> >
> > I am not talking about solving the halting problem.
> > There are three possible cases for the Halt Analyzer
> > to report:
> >
> > (1) Halts
> > (2) Does Not Halt
> > (3) I Don't Know
> >
> >
> now we don't know what a correct solution to your
> modified problem is. because you've -never- answered
> the following simple question: -does- a routine that
> always returns "don't know" count as a correct solution?
>
C'mon. OF COURSE its a _correct_ solution, since it's ONE of the
possible cases "for the Halt Analyzer to report". Though it's
completely _useless_. So what?
Can y o u prove that this is a necessary outcome? No? So shut up!
F.
Hint - quote:
G. Frege
Low) wrote:
>
> I meant 'What interesting things do you [Peter Olcott]
> have to say about this problem?'
>
I see.
Well, but he d i d point out that it would be a good idea to have 3
possible answers:
> >
> > There are three possible cases for the Halt Analyzer
> > to report:
> >
> > (1) Halts
> > (2) Does Not Halt
> > (3) I Don't Know
> >
And from this we immediately get a first result:
>
> There is an easy algorithm that never gives a wrong answer, but also
> never gives a useful one [...].
>
Right.
On the other hand I can present an algorithm which is able to give a
answer which is slightly more useful.
We consider programs (say in "C") which are limited to (max.) ONE
occurrence of a "repetition construct". Then the program reports
"Does Not Halt" if it encounters constructions like
while (1);
or
for(;;);
etc.
This way, at least SOME "loops" would be caught.
Moreover it may report "Halts" if it does not encounter any "repetition
construct".
This way the Halt Analyzer would report "Halts" for
int main(void)
{
printf("Tell me!\n");
return 0;
}
And it would report "Does Not Halt" for
int main(void)
{
printf("Tell me!\n");
while (1);
return 0;
}
And it might report "I Don't Know" for
int main(void)
{
for (int i = 0; i < 10; i++)
printf("Tell me!\n");
return 0;
}
>
> I'd be surprised if he had anything even that good
> to offer. (Pleasantly surprised, but surprised.)
>
See?!
F.
Robert Low
>On 6 Sep 2004 13:13:15 GMT, mtx...@linux.services.coventry.ac.uk (Robert
>Low) wrote:
>> There is an easy algorithm that never gives a wrong answer, but also
>> never gives a useful one [...].
>>
>Right.
>
>On the other hand I can present an algorithm which is able to give a
>answer which is slightly more useful.
Your algorithm is a variation on what I was thinking
about and characterizing as 'never useful'. You can
tell just by looking at the code that a program
whose only iterative structures are for
loops with a fixed number of repetitions will halt.
This is completely bleeding obvious.
>> I'd be surprised if he had anything even that good
>> to offer. (Pleasantly surprised, but surprised.)
>See?!
I don't see PO offering anything better than what
somebody with twenty-five minutes exposure to programming
constructs would come up with. In fact, I haven't
seen him yet offer anything that useful. I'm sure
that there *are* things more useful than that
to be found; there are, after all, standard strategies
for showing that while loops terminate (well, when
they do) it I'm sure it's possible to make a useful
algorithm for guessing/finding loop invariants and so
on. But where's the Olcott contribution to this
endeavour?
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
Peter Olcott
"David C. Ullrich" <ull...@math.okstate.edu> wrote in message news:7ajoj01dt1fso2trf...@4ax.com...
A non-answer to a stupid question counts as a negative.
David C. Ullrich
>On Mon, 06 Sep 2004 06:53:38 -0500, David C. Ullrich
><ull...@math.okstate.edu> wrote:
>
>> >
>> > What I intended is that the progression of the technology
>> > of the automatic detection of [some] programming errors can
>> > for [many/most] practical purposes [succeed].
that's not something i wrote, it's your modified version
of something peter wrote.
it's -not- what peter wrote. he wrote
>> >What I intended is that the progression of the technology
>> >of the automatic detection of programming errors can for
>> >all practical purposes circumvent the Halting Problem.
there's a huge difference between 'for all practical
purposes circumvent the Halting Problem' and
'the automatic detection of [some] programming errors can
for [many/most] practical purposes [succeed]'. for example
if we can for all practical purposes circumvent the
halting problem then we can immediately answer -many-
if not all unsolved problems of mathematics.
>> huh? that's not remotely like something that can be
>> given a logical proof.
>>
>
>On the other hand, at least it's not _excluded_ by a rigorous proof (to
>to my knowledge). Hence it m i g h t be possible.
this has no relevance to anything i said.
>As others have pointed out:
>
>Quote:
>-------------------------------------------------------------
>
>There is a LOT of work on termination analysis. See for example
>Andreas Abel publications, especially "Termination Checking with
>Types."
>
> http://www.tcs.informatik.uni-muenchen.de/~abel/publications.html
>
>The fact that such analyses must be conservative, and may reject some
>terminating programs, does not render them useless. --Amr
>
>-------------------------------------------------------------
well, duh - who said anything to the contrary?
>F.
>
>
>P.S.
>Is there a p r o o f that AI is "possible", c a n there be such a
>proof? (Don't think so.) So what?
Abdulaziz Ghuloum
> On Mon, 06 Sep 2004 01:52:34 -0500, Abdulaziz Ghuloum
> <aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
>
>>The thread was initially about the general halting problem (for TMs)[1].
>> It quickly turned into C by G.Frege's while(1); example.
>>
>
> Huh???
>
> But it was YOU who started this argument.
>
> Quote:
> -------------------------------------------------------------
>
> Hmmm. So, is the following code a valid Halt Analyzer function:
>
> HaltResult Analyze(Program code){
> return I_DONT_KNOW; // always reporting case (3) above
> }
>
> To me, it seems perfectly valid (according to your definition) and
> completely useless.
>
> -------------------------------------------------------------
I wrote the analyzer in C. I did not say it was analyzing C programs.
The input to that function was `Program', not 'C_Program'.
David C. Ullrich
>On Mon, 06 Sep 2004 06:57:28 -0500, David C. Ullrich
><ull...@math.okstate.edu> wrote:
>
>>>>
>>>> Oh, OK. So you've changed the question, and allowed
>>>> 'Don't know' as one possible answer. I guess that
>>>> you have then proved that a different problem can
>>>> 'solved' by an algorithm that doesn't always tell
>>>> you the answer. Why is this interesting?
>>>>
>>>> Rob.
>>>
>>> It is far better than simply not bothering to attempt
>>> to solve any aspect of the problem at all.
>>>
>>> [...]
>>>
>> realistically, consider the following:
you're simply mangling quotes - this is somewhere between
irritating and dishonest. my 'realistically, consider the following'
was not in reply to
[i] 'It is far better than simply not bothering
to attempt to solve any aspect of the problem at all',
it was in reply to
[ii] '>Realistically, how often would a function such as
LoopIfHalts be inadvertently encoded within an application?'
there's a big difference - [i] is not something anyone has
denied, and my reply makes no sense as a reply to [i].
on the other hand [ii] shows that peter is still very
confused - my reply, if read as a reply to [ii], demonstrates
this fact.
if you have something to say say it. if you have a comment on
something that was said fine. but stop this business of
distorting what was said.
>> def divides(a, b):
>> return (b%a)==0
>>
>> def perfect(n):
>> s = 0
>> for d in range(1,n):
>> if divides(d,n):
>> s = s + d
>> return s==n
>>
>> def findOddPerfect():
>> n = 3
>> while 1:
>> if perfect(n):
>> return n
>> n = n + 2
>>
>> findOddPerfect()
>>
>> does that halt or not?
************************
David C. Ullrich
>On Mon, 06 Sep 2004 06:47:57 -0500, David C. Ullrich
><ull...@math.okstate.edu> wrote:
>
>> >
>> > I am not talking about solving the halting problem.
>> > There are three possible cases for the Halt Analyzer
>> > to report:
>> >
>> > (1) Halts
>> > (2) Does Not Halt
>> > (3) I Don't Know
>> >
>> >
>> now we don't know what a correct solution to your
>> modified problem is. because you've -never- answered
>> the following simple question: -does- a routine that
>> always returns "don't know" count as a correct solution?
>>
>C'mon. OF COURSE its a _correct_ solution, since it's ONE of the
>possible cases "for the Halt Analyzer to report". Though it's
>completely _useless_. So what?
uh, the question was an attempt to get peter to clarify exactly
what problem he had in mind. if you read what he wrote elsewhere
you see that no, it's not a correct solution.
>Can y o u prove that this is a necessary outcome?
huh? prove that what is a necessary outcome of what?
>No? So shut up!
been forgetting to take our how-to-make-friends pills
again?
>F.
>
>
>Hint - quote:
>-------------------------------------------------------------
>
>There is a LOT of work on termination analysis. See for example
>Andreas Abel publications, especially "Termination Checking with
>Types."
>
> http://www.tcs.informatik.uni-muenchen.de/~abel/publications.html
>
>The fact that such analyses must be conservative, and may reject some
>terminating programs, does not render them useless. --Amr
>
>-------------------------------------------------------------
if this had anything to do with anything i said i'd reply.
Peter Olcott
"David C. Ullrich" <ull...@math.okstate.edu> wrote in message news:5tsoj0ta3esa47t9g...@4ax.com...
> On Mon, 06 Sep 2004 15:03:18 +0200, G. Frege <no_...@aol.com> wrote:
>
> >On Mon, 06 Sep 2004 06:53:38 -0500, David C. Ullrich
> ><ull...@math.okstate.edu> wrote:
> >
> >> >
> >> > What I intended is that the progression of the technology
> >> > of the automatic detection of [some] programming errors can
> >> > for [many/most] practical purposes [succeed].
If we change the model of programming limiting what is permitted
to be expressed (such as edsger dijkstra proposed) more of these
sorts of problems derive simpler solutions. Instead of deriving
formal specification languages whereby a mathematical proof of
correctness can assess the validity of arbitrary programming
constructs, merely use the formal specification as the basis for
generating the program that meets this specification.
G. Frege
Low) wrote:
>
> Your algorithm is a variation on what I was thinking
> about and characterizing as 'never useful'.
>
?
Imho the following is _never_ useful:
HaltResult Analyze(Program code){
return I_DONT_KNOW; // always reporting case (3) above
}
Now you say:
>
> You can tell just by looking at the code that a program
> whose only iterative structures are for loops with a
> fixed number of repetitions will halt. This is completely
> bleeding obvious.
>
Sure, but things may become more complicated easily:
:
for (i = 1; i < 10; i++)
{
:
1000 lines of code
:
if (i == 5) then i = 0 // Should read "...then j = 0".
:
1000 lines of code
:
}
:
>
> I don't see PO offering anything better than what
> somebody with twenty-five minutes exposure to programming
> constructs would come up with.
>
Why s h o u l d he?
>
> In fact, I haven't seen him yet offer anything that useful.
>
Well, *I* like the idea of returning a 3rd "value".
>
> [...] there are, after all, standard strategies
> for showing that while loops terminate (well, when
> they do) it I'm sure it's possible to make a useful
> algorithm for guessing/finding loop invariants and so
> on.
>
Sure. Still such an algorithm will not detect ALL possible cases, i.e.
be able to decide /yes/, /no/ for all cases; then it would be a good
idea to return /Don't know/. Don't you think so?
F.
David C. Ullrich
<olc...@worldnet.att.net> wrote:
uh, no, not in this context. because, as explained
below: [i] you've said so many stupid things here that
the fact that what you seem to be saying is stupid
is no evidence that it's not what you meant, [ii]
you've complained many times about people trying
to figure out what you mean instead of reading
exactly what you wrote.
exactly what you wrote indicates that always saying
don't know does count as a solution to the problem.
and you always write exactly what you mean. so i
take it that's what you mean.
news...@comcast.net
>
> "Robert Low" <mtx...@linux.services.coventry.ac.uk> wrote in message news:chhav1$b2g$1...@sunbeam.coventry.ac.uk...
>>
>> Peter Olcott <olc...@worldnet.att.net> wrote:
>> ><news...@comcast.net> wrote in message
>> >> In comp.theory Peter Olcott <olc...@worldnet.att.net> wrote:
>> >> > of error. If the Halting Problem is redefined (which does not
>> >> > refute anyone), then this redefined problem can be easily
>> >> > solved.
>> >> Sigh.... two steps forward, one step back....
>> >I am not talking about solving the halting problem.
>>
>> Oh, OK. So you've changed the question, and allowed
>> 'Don't know' as one possible answer. I guess that
>> you have then proved that a different problem can
>> 'solved' by an algorithm that doesn't always tell
>> you the answer. Why is this interesting?
(I'm posting this while repeatedly chanting to myself "I will not get
sucked back into this discussion, I will not get sucked back into this
discussion, ...)
> It is far better than simply not bothering to attempt
> to solve any aspect of the problem at all.
Of course. Who exactly is "simply not bothering to attempt to solve
any aspect of the problem at all"? There are lots of examples of
people doing static analysis on programs, using model checkers, and
all sorts of things, in order to analyze programs for some interesting
subset of problems. As an aside from the practical world, I'll let
you know that Microsoft (not that they're a great example of
high-quality code) actually has some static analysis tools built into
their CVS-type system -- programmers are not allowed to check in code
that doesn't pass the tests. There's a *huge* amount of work along
these lines.
> Realistically,
> how often would a function such as LoopIfHalts be
> inadvertently encoded within an application?
Realistically, who cares? The functions "such as LoopIfHalts" are a
completely insignificant subset of the problems that can't be
analyzed. It's just that they're convenient for one particular form
of proof. Other than that, no one cares. You seem to be under the
mistaken impression (in this post and in some others) that the
"LoopIfHalts" pattern is the only thing that causes problems to a halt
analyzer, so if you could just handle that case somehow you could
solve all the other problems. Nothing could be further from the truth.
Robert Low
G. Frege <no_...@aol.com> wrote:
>On 6 Sep 2004 14:08:50 GMT, mtx...@linux.services.coventry.ac.uk (Robert
>Low) wrote:
>> I don't see PO offering anything better than what
>> somebody with twenty-five minutes exposure to programming
>> constructs would come up with.
>Why s h o u l d he?
To susbtantiate his claim that he can do something
that *for all practical purposes* avoids the fact
that the halting problem is uncomputable. This
is a very strong claim.
It can clearly be done (easily) in some simple cases;
essentially automating stuff where you have a very
simply rule of thumb but there are lots of lines
of code. It can less clearly be done in other,
more interesting cases, and that is a subject
of current research. But 'for all practical
purposes'? Now, instead of not even knowing
the game, he's claiming to be ahead of it.
That requires justification.
>> In fact, I haven't seen him yet offer anything that useful.
>Well, *I* like the idea of returning a 3rd "value".
I have the sneaking suspicion that other people
have already had the idea of returning 'can't tell'
to this type of problem. Then again, Olcott's the
one with the 'barely near-genius IQ' (whatever
that means) so I suppose it is possible that nobody
else ever thought of it.
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
The Ghost In The Machine
<no_...@aol.com>
wrote
on Mon, 06 Sep 2004 01:40:52 +0200
<cu8nj0l7okpi7kub2...@4ax.com>:
> On Mon, 06 Sep 2004 01:33:03 +0200, G. Frege <no_...@aol.com> wrote:
>
>>
>> For example, it should be possible to write a Halt Analyzer (for the
>> language C) which is able to determine "Does Not Halt" if it encounters
>> (for example) the code
>>
>> :
>> while (1); <--- corrected
>> :
>>
>
> Ah, right, it's C. :-)
>
>
> F.
Heuristics are useful; we might even be able to correctly answer
most of the questions of "Yes", "No", and "Maybe". The point is
that we can't answer all of them.
(I think that's the point Peter Olcott is missing.)
--
#191, ewi...@earthlink.net
It's still legal to go .sigless.
Jon Haugsand
> I have the sneaking suspicion that other people
> have already had the idea of returning 'can't tell'
> to this type of problem. Then again, Olcott's the
> one with the 'barely near-genius IQ' (whatever
> that means) so I suppose it is possible that nobody
> else ever thought of it.
Really? This is something occationally discussed in local fora. To
bring this idea a bit further, let IHM denote the set of all
algorithms that given a program and an input string will return
"halts", "doesn't halt" or "uknown" and if one of the first two, it
will do so correctly. What can be said of this set? As shown by
Turing, there is no element that will never return "unknown". Let <=
be the following order on the elements:
For a1,a2 \in IHM we define p1 <= p2 iff \forall programs P and
inputs I: a2(P,I)="unknown" -> a1(P,I)="unknown"
We can then show that <= is a partial ordering (reflexive,
antisymmetric and transitive") on IHM.
Further, given two arbitrarely algorithms a1 and a1, define a1 V a2 as
follows:
(a1 V a2)(P,I) == if a1(P,I) = "unknown" then a2(P,I) else a1(P,I)
endif
That is, we take the value that is not "unknown" if one of a1 or a2
can find it. OLH is therefore a semilattice.
One interesting question is what I would like to call "social
programming". Given that there is an ongoing competition to find the
"highest" element in OLH, that is, if each year the person who can
make an element that can beat all other known elements in OLH in the
sense that the candidate a-highest is >= all other, it wins a price.
Will the sequennce a-highest_0, a-highest_1, ... as the years pass in
the end for any program P and input I manage to contain an element
a-highest_i so that a-highst_i(P,I) is not equal to "unknown".
I guess this is a ridiculus question...
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
Jon Haugsand
> For a1,a2 \in IHM we define p1 <= p2 iff \forall programs P and
> inputs I: a2(P,I)="unknown" -> a1(P,I)="unknown"
>
> We can then show that <= is a partial ordering (reflexive,
> antisymmetric and transitive") on IHM.
Actually not true, because antisymmentry isn't there. However, we can
factor out all the equivalence classes found by all symmetric
algorithms and thus let each equivalence class represent the
algorithms inside it.
Jon Haugsand
> For a1,a2 \in IHM we define p1 <= p2 iff \forall programs P and
> inputs I: a2(P,I)="unknown" -> a1(P,I)="unknown"
>
> We can then show that <= is a partial ordering (reflexive,
> antisymmetric and transitive") on IHM.
Actually not true, because antisymmentry isn't there. However, we can
factor out all the equivalence classes found by the natural
equivalence relation (all algorithms that always give the same answer)
and thus let each equivalence class represent the algorithms inside
it.
--
G. Frege
<ew...@aurigae.athghost7038suus.net> wrote:
>
> Heuristics are useful; we might even be able to correctly answer
> most of the questions of "Yes", "No", and "Maybe". The point is
> that we can't answer all of them.
>
Sorry, can't follow. I mean it is _possible_ to construct a computing
device which always correctly generates one of the answers "Yes", "No",
and "Don't know". (Say with a timer which interrupts the calculation
after some fixed amount of time. In this case "Don't know" is returned.)
Of course, this might not be realizable with a TM proper, I guess.
F.
Abdulaziz Ghuloum
What does `realizable with a TM proper' mean?
Aziz,,,
G. Frege
<aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
> What does 'realizable with a TM proper' mean?
>
A "TM" with some timer device (to allow for "interrupts") attached is
certainly not a TM (in the originally defined sense) any more. No?
(So probably it's better to talk more generally about a "computing
device" in this case.)
F.
Abdulaziz Ghuloum
> On Mon, 06 Sep 2004 15:31:24 -0500, Abdulaziz Ghuloum
> <aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
>
>>What does 'realizable with a TM proper' mean?
>>
>
> A "TM" with some timer device (to allow for "interrupts") attached is
> certainly not a TM (in the originally defined sense) any more. No?
Of course it is still a TM. A timer can easily be simulated inside a
vanilla TM.
> (So probably it's better to talk more generally about a "computing
> device" in this case.)
No it's not.
G. Frege
<aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
> Of course it is still a TM. A timer can easily be simulated inside a
> vanilla TM.
>
Really? What's the clock rate of your vanilla TM? (I'm just curios.)
(Right, a "step counter" would be ok for me too. :-)
> >
> > (So probably it's better to talk more generally about a "computing
> > device" in this case.)
> >
F.
|-|erc
> On Mon, 06 Sep 2004 17:14:33 -0500, Abdulaziz Ghuloum
> <aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
> >
> > Of course it is still a TM. A timer can easily be simulated inside a
> > vanilla TM.
> >
> Really? What's the clock rate of your vanilla TM? (I'm just curios.)
>
> (Right, a "step counter" would be ok for me too. :-)
>
UTMs have a fetch cycle, so it should be trivial to have a timeout.
Herc
|-|erc
> > (Right, a "step counter" would be ok for me too. :-)
> >
>
> UTMs have a fetch cycle, so it should be trivial to have a timeout.
>
but the solution will only return
1/ halts
2/ I don't know
it will never conclude "does not halt" at all.
the key that Peter and Kent are close to is identifying_self_reference.
the only argument against this is that different programs can be
functionally similar.
but how do you prove one program cannot recognise the other?
it is your burden to show they can't. otherwise we are safe to assume
a COMPLETE ALL KNOWING halt program can be written with
outputs :
1/ halts
2/ does not halt
3/ contains reference to *a* halt algorithm
There is another hypothetical soln to halt which was ignored several
months ago when I posted it.
An algorithm produces a set of godel numbers for pHalt programs.
AllHalt() = {1, 5, 20, 55, 999, 23838... }
Each of these programs is a partial halt function that behaves correctly
with the outputs :
1/ halts
2/ does not halt
3/ don't know
(this is a weaker 'don't know' than Peter's 'contains self reference', it
literally just doesn't parse that function)
None of the phalt functions can contradict another, though some will
know the answer and others will not.
So instead of a SINGLE halt function that is prone to self referential
contradition,
we have a **SET** of phalt functions, and add the conjecture.
Conjecture of halt soln : En, n e AllHalt, UTM(n, (f, a)) = Halt(f, a)
where Halt(f, a) is the bona fide halt function.
If we apply the halting proof to try to prove this is impossible..
Loops(a) = if (Halt(a, a), infiniteloop) *1
Loops(a) = if (! Halt(a, a), return)
Loops(loops) =
if ( En, n e AllHalt, UTM(n, (loops, loops)), infiniteloop)
IF Loops(loops) halts
THEN En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
(by the conjecture)
IF Loops(loops) halts
THEN infiniteloop is not reached *1
THEREFORE En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
What contradiction does this reach?
En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
AND
En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
No contradiciton!
i.e. a solution to the problem can be found, but it is not a single TM.
Herc
Peter Olcott
> "|-|erc" <go...@beauty.com> wrote in > >
> > > (Right, a "step counter" would be ok for me too. :-)
> > >
> >
> > UTMs have a fetch cycle, so it should be trivial to have a timeout.
> >
>
> but the solution will only return
>
> 1/ halts
> 2/ I don't know
>
> it will never conclude "does not halt" at all.
>
> the key that Peter and Kent are close to is identifying_self_reference.
> the only argument against this is that different programs can be
> functionally similar.
> but how do you prove one program cannot recognise the other?
>
> it is your burden to show they can't. otherwise we are safe to assume
> a COMPLETE ALL KNOWING halt program can be written with
> outputs :
>
> 1/ halts
> 2/ does not halt
> 3/ contains reference to *a* halt algorithm
I think that News...@comcast.net (why not use a real name)
suggested that the latter might also be undecidable. I would certainly
trust his judgment.
|-|erc
> > > > (Right, a "step counter" would be ok for me too. :-)
> > > >
> > >
> > > UTMs have a fetch cycle, so it should be trivial to have a timeout.
> > >
> >
> > but the solution will only return
> >
> > 1/ halts
> > 2/ I don't know
> >
> > it will never conclude "does not halt" at all.
> >
> > the key that Peter and Kent are close to is identifying_self_reference.
> > the only argument against this is that different programs can be
> > functionally similar.
> > but how do you prove one program cannot recognise the other?
> >
> > it is your burden to show they can't. otherwise we are safe to assume
> > a COMPLETE ALL KNOWING halt program can be written with
> > outputs :
> >
> > 1/ halts
> > 2/ does not halt
> > 3/ contains reference to *a* halt algorithm
>
> I think that News...@comcast.net (why not use a real name)
> suggested that the latter might also be undecidable. I would certainly
> trust his judgment.
This was your OP
Now we have three possible correct results:
(a) Halts
(b) Does Not Halt
(c) Pathological Self Reference to Halt
Is this debunked already? It was discussed some time ago regarding Rice
Theorem but nothing concrete was posted. people here will blindly refute
existence of an algorithm with no reason to.
Herc
G. Frege
<olc...@worldnet.att.net> wrote:
> >
> > 1/ halts
> > 2/ does not halt
> > 3/ contains reference to *a* halt algorithm
> >
> I think that News...@comcast.net (why not use a real name)
> suggested that the latter might also be undecidable. I would certainly
> trust his judgment.
>
Right.
1. Halts
2. Doesn't halt
3. Don't know (Can't say)
should be good enough.
And several people already provided simple algorithms to implement such
a Halt Analyzer. The most trivial (but completely useless) solution
would be
analyze(string: program, string: input)
{
return "Don't know"
}
Certainly that's not the only possible solution. (Though it still IS a
solution, and this way PROVES that such a halt analyzer c a n be
implemented.)
F.
Simon G Best
> "|-|erc" <go...@beauty.com> wrote in > >
>
>>>(Right, a "step counter" would be ok for me too. :-)
>>
>>UTMs have a fetch cycle, so it should be trivial to have a timeout.
>
> but the solution will only return
>
> 1/ halts
> 2/ I don't know
>
> it will never conclude "does not halt" at all.
>
> the key that Peter and Kent are close to is identifying_self_reference.
> the only argument against this is that different programs can be
> functionally similar.
> but how do you prove one program cannot recognise the other?
>
> it is your burden to show they can't. otherwise we are safe to assume
> a COMPLETE ALL KNOWING halt program can be written with
> outputs :
>
> 1/ halts
> 2/ does not halt
> 3/ contains reference to *a* halt algorithm
No, we are *not* "safe to assume" that. A lack of proof *does not* mean
that it's "safe to assume" the opposite.
> There is another hypothetical soln to halt which was ignored several
> months ago when I posted it.
What you wrote here (following this) wasn't terribly clear, but I
/think/ I see what you're getting at.
> An algorithm produces a set of godel numbers for pHalt programs.
> AllHalt() = {1, 5, 20, 55, 999, 23838... }
I'm taking "pHalt" to mean a Turing Machine which constitutes a partial
solution to the Halting Problem.
I'll also take "AllHalt" to be a set, rather than "An algorithm", as it
seems that that's what you /really/ mean.
> Each of these programs is a partial halt function that behaves correctly
> with the outputs :
>
> 1/ halts
>
> 2/ does not halt
>
> 3/ don't know
> (this is a weaker 'don't know' than Peter's 'contains self reference', it
> literally just doesn't parse that function)
>
> None of the phalt functions can contradict another, though some will
> know the answer and others will not.
>
> So instead of a SINGLE halt function that is prone to self referential
> contradition,
> we have a **SET** of phalt functions,
Which must be an infinite set,
> and add the conjecture.
>
> Conjecture of halt soln : En, n e AllHalt, UTM(n, (f, a)) = Halt(f, a)
>
> where Halt(f, a) is the bona fide halt function.
Which doesn't actually help. While there certainly is such a set as
AllHalt, no Turing Machine can list its elements.
Here's a quick sketch of the proof.
If there was a Turing Machine, A, which could list the elements of
AllHalt, we could easily use it as the basis for a Turing Machine, H,
which would implement Halt.
We would arrange H to get each element, n, of AllHalt in turn, and try
it. If n results in a 'don't know' answer, then the next element of
AllHalts is tried. If, instead, n results in a 'halts' or 'does not
halt' answer, then that is the answer H itself gives, and H halts.
As A would list all the elements of AllHalt, H would eventually find an
n which would give the right answer for the case in question. As Turing
Machines themselves are countable, AllHalt (which is a subset of the set
of Turing Machines) is countable, and each element would eventually be
found in a finite amount of time, so we can be sure that H will always
halt in a finite amount of time.
We already have proofs that H cannot exist. Therefore, A cannot exist.
> If we apply the halting proof to try to prove this is impossible..
We will find, as always, that it is, indeed, impossible.
But anyway...
> Loops(a) = if (Halt(a, a), infiniteloop) *1
> Loops(a) = if (! Halt(a, a), return)
Okay, though you haven't actually said how to get from your conjecture
to an actual Halt Turing Machine...
[1]:
> Loops(loops) =
> if ( En, n e AllHalt, UTM(n, (loops, loops)), infiniteloop)
Okay...
> IF Loops(loops) halts
> THEN En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
> (by the conjecture)
which implies that Loops(loops) loops forever, and never halts.
> IF Loops(loops) halts
> THEN infiniteloop is not reached *1
Incorrect.
If Loops(loops) halts, then "En, n e AllHalt, UTM(n, (loops, loops)",
and "infiniteloop" /is/ reached, and so Loops(loops) does not halt. But
that implies that there is no such n in AllHalt, which implies that
Loops(loops) /does/ halt.
> THEREFORE En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
>
> What contradiction does this reach?
>
> En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
> AND
> En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
>
> No contradiciton!
You seem to have got confused, and misunderstood your own conjecture :-(
> i.e. a solution to the problem can be found, but it is not a single TM.
That doesn't follow from what you wrote above. You're leaping to
conclusions.
Simon
|-|erc
> |-|erc wrote:
> > "|-|erc" <go...@beauty.com> wrote in > >
> >
> >>>(Right, a "step counter" would be ok for me too. :-)
> >>
> >>UTMs have a fetch cycle, so it should be trivial to have a timeout.
> >
> > but the solution will only return
> >
> > 1/ halts
> > 2/ I don't know
> >
> > it will never conclude "does not halt" at all.
> >
> > the key that Peter and Kent are close to is identifying_self_reference.
> > the only argument against this is that different programs can be
> > functionally similar.
> > but how do you prove one program cannot recognise the other?
> >
> > it is your burden to show they can't. otherwise we are safe to assume
> > a COMPLETE ALL KNOWING halt program can be written with
> > outputs :
> >
> > 1/ halts
> > 2/ does not halt
> > 3/ contains reference to *a* halt algorithm
>
> No, we are *not* "safe to assume" that. A lack of proof *does not* mean
> that it's "safe to assume" the opposite.
If we *label* HypotheticalFunction() as an assumption then we can assume it.
Unless you are falling back on the popular argument, 'ok what is the halt
function then!'.
>
> > There is another hypothetical soln to halt which was ignored several
> > months ago when I posted it.
>
> What you wrote here (following this) wasn't terribly clear, but I
> /think/ I see what you're getting at.
>
> > An algorithm produces a set of godel numbers for pHalt programs.
> > AllHalt() = {1, 5, 20, 55, 999, 23838... }
>
> I'm taking "pHalt" to mean a Turing Machine which constitutes a partial
> solution to the Halting Problem.
>
> I'll also take "AllHalt" to be a set, rather than "An algorithm", as it
> seems that that's what you /really/ mean.
>
> > Each of these programs is a partial halt function that behaves correctly
> > with the outputs :
> >
> > 1/ halts
> >
> > 2/ does not halt
> >
> > 3/ don't know
> > (this is a weaker 'don't know' than Peter's 'contains self reference',
it
> > literally just doesn't parse that function)
> >
> > None of the phalt functions can contradict another, though some will
> > know the answer and others will not.
> >
> > So instead of a SINGLE halt function that is prone to self referential
> > contradition,
> > we have a **SET** of phalt functions,
>
> Which must be an infinite set,
Right! I'll be using this later to escape the contradiction.
>
> > and add the conjecture.
> >
> > Conjecture of halt soln : En, n e AllHalt, UTM(n, (f, a)) = Halt(f, a)
> >
> > where Halt(f, a) is the bona fide halt function.
>
> Which doesn't actually help. While there certainly is such a set as
> AllHalt, no Turing Machine can list its elements.
>
> Here's a quick sketch of the proof.
>
> If there was a Turing Machine, A, which could list the elements of
> AllHalt, we could easily use it as the basis for a Turing Machine, H,
> which would implement Halt.
>
> We would arrange H to get each element, n, of AllHalt in turn, and try
> it. If n results in a 'don't know' answer, then the next element of
> AllHalts is tried. If, instead, n results in a 'halts' or 'does not
> halt' answer, then that is the answer H itself gives, and H halts.
>
> As A would list all the elements of AllHalt, H would eventually find an
> n which would give the right answer for the case in question. As Turing
> Machines themselves are countable, AllHalt (which is a subset of the set
> of Turing Machines) is countable, and each element would eventually be
> found in a finite amount of time, so we can be sure that H will always
> halt in a finite amount of time.
>
> We already have proofs that H cannot exist. Therefore, A cannot exist.
As I specified AllHalt the conjecture is false, but there is another soln.
>
> > If we apply the halting proof to try to prove this is impossible..
>
> We will find, as always, that it is, indeed, impossible.
>
> But anyway...
>
> > Loops(a) = if (Halt(a, a), infiniteloop) *1
> > Loops(a) = if (! Halt(a, a), return)
>
> Okay, though you haven't actually said how to get from your conjecture
> to an actual Halt Turing Machine...
>
> [1]:
> > Loops(loops) =
> > if ( En, n e AllHalt, UTM(n, (loops, loops)), infiniteloop)
>
> Okay...
>
> > IF Loops(loops) halts
> > THEN En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
> > (by the conjecture)
>
> which implies that Loops(loops) loops forever, and never halts.
>
> > IF Loops(loops) halts
> > THEN infiniteloop is not reached *1
>
> Incorrect.
From inspection of Loops,
> [1]:
> > Loops(loops) =
> > if ( En, n e AllHalt, UTM(n, (loops, loops)), infiniteloop) *2
(If functionX halts, then its infinite loop is not reached) is self evident.
>
> If Loops(loops) halts, then "En, n e AllHalt, UTM(n, (loops, loops)",
> and "infiniteloop" /is/ reached, and so Loops(loops) does not halt. But
> that implies that there is no such n in AllHalt, which implies that
> Loops(loops) /does/ halt.
>
> > THEREFORE En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
> >
> > What contradiction does this reach?
> >
> > En, n e AllHalt, UTM(n, (loops, loops)) = 'halt'
> > AND
> > En, n e AllHalt, UTM(n, (loops, loops)) != 'halt'
> >
> > No contradiciton!
>
> You seem to have got confused, and misunderstood your own conjecture :-(
>
> > i.e. a solution to the problem can be found, but it is not a single TM.
>
> That doesn't follow from what you wrote above. You're leaping to
> conclusions.
What I meant to write was :
halt(f, a) -> En, n e AllHalt, UTM(n, f(a))=true
!halt(f, a) -> An, n e AllHalt, UTM(n, f(a))='don't know'
as an example, AllHalt could be an infinite set of Universal Turing
Machines,
but they timeout after various amounts of time. If the parameter f(a)
halted
then it outputs TRUE, otherwise DONTKNOW. Since the number of these
partial Halt functions is infinite, we should come across one with enough
test cycles to determine if any function halts.
Herc
Simon G Best
>>
>>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
>>that it's "safe to assume" the opposite.
>
> If we *label* HypotheticalFunction() as an assumption then we can assume it.
Certainly an assumption is an assumption. That does not contradict what
I said.
[...]
>
>>>and add the conjecture.
>>>
>>>Conjecture of halt soln : En, n e AllHalt, UTM(n, (f, a)) = Halt(f, a)
which I take to mean:
Af, Aa, En, n e AllHalt, UTM(n, (f, a)) = Halt(f, a)
>>>where Halt(f, a) is the bona fide halt function.
>>
>>Which doesn't actually help. While there certainly is such a set as
>>AllHalt, no Turing Machine can list its elements.
>>
>>Here's a quick sketch of the proof.
>>
[...]
>
> As I specified AllHalt the conjecture is false, but there is another soln.
The conjecture isn't false!
>>>If we apply the halting proof to try to prove this is impossible..
>>
>>We will find, as always, that it is, indeed, impossible.
>>
>>But anyway...
>>
[...]
>>
>>Incorrect.
>
> From inspection of Loops,
>
>>[1]:
>>
>>>Loops(loops) =
>>>if ( En, n e AllHalt, UTM(n, (loops, loops)), infiniteloop) *2
>
> (If functionX halts, then its infinite loop is not reached) is self evident.
Ah, you seem to be missing the contradiction:
>>If Loops(loops) halts, then "En, n e AllHalt, UTM(n, (loops, loops)",
>>and "infiniteloop" /is/ reached, and so Loops(loops) does not halt. But
>>that implies that there is no such n in AllHalt, which implies that
>>Loops(loops) /does/ halt.
Whether or not loops(loops) halts depends, by definition (of loops), on
whether or not there exists an n in AllHalt such that UTM(n, (loops,
loops)) = 'halts'.
Whether or not there exists an n in AllHalt such that UTM(n, (loops,
loops)) = 'halts' also depends, by definition (of AllHalt), on whether
or not loops(loops) halts.
If such an n is found to exist in AllHalt, loops(loops) will not halt
(because that's how it's defined). But if loops(loops) does not halt,
then there is no such n in AllHalt. But that means that loops(loops) halts!
Do you see the contradiction now?
[...]
>>
>>>i.e. a solution to the problem can be found, but it is not a single TM.
>>
>>That doesn't follow from what you wrote above. You're leaping to
>>conclusions.
>
> What I meant to write was :
>
> halt(f, a) -> En, n e AllHalt, UTM(n, f(a))=true
> !halt(f, a) -> An, n e AllHalt, UTM(n, f(a))='don't know'
>
> as an example, AllHalt could be an infinite set of Universal Turing
> Machines,
> but they timeout after various amounts of time. If the parameter f(a)
> halted
> then it outputs TRUE, otherwise DONTKNOW. Since the number of these
> partial Halt functions is infinite, we should come across one with enough
> test cycles to determine if any function halts.
But, for all functions f, for all inputs a, where f does not halt on a,
your 'solution' never determines that f does not halt on a.
It's no better than just running the UTM on (f, a) and waiting to see
whether or not it ever halts.
Indeed, that is really all your 'solution' is!
Simon
|-|erc
> |-|erc wrote:
> > "Simon G Best" <s.g....@btopenworld.com> wrote in
> >
> >>|-|erc wrote:
> >>
> [...]
> >>
> >>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
> >>that it's "safe to assume" the opposite.
> >
> > If we *label* HypotheticalFunction() as an assumption then we can assume it.
>
> Certainly an assumption is an assumption. That does not contradict what
> I said.
fraid so.
if you have NOT proven x, i may assume !x T/F
i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
only one result of the halt function, to determine the opposite (does not halt)
you have to trial infinite n.
>
> [...]
> >>
> >>>i.e. a solution to the problem can be found, but it is not a single TM.
> >>
> >>That doesn't follow from what you wrote above. You're leaping to
> >>conclusions.
> >
> > What I meant to write was :
> >
> > halt(f, a) -> En, n e AllHalt, UTM(n, f(a))=true
> > !halt(f, a) -> An, n e AllHalt, UTM(n, f(a))='don't know'
> >
> > as an example, AllHalt could be an infinite set of Universal Turing
> > Machines,
> > but they timeout after various amounts of time. If the parameter f(a)
> > halted
> > then it outputs TRUE, otherwise DONTKNOW. Since the number of these
> > partial Halt functions is infinite, we should come across one with enough
> > test cycles to determine if any function halts.
>
> But, for all functions f, for all inputs a, where f does not halt on a,
> your 'solution' never determines that f does not halt on a.
>
> It's no better than just running the UTM on (f, a) and waiting to see
> whether or not it ever halts.
>
> Indeed, that is really all your 'solution' is!
>
> Simon
not at all, that was just a trivial *example* of the solution using clumsy UTMs.
the idea works for an infinite set of smart phalt functions, or the opposite! an
infinite set of nohalt functions.
here's a better example.
NHalt2() = {2, 6, 33, 655, ..}
NHalt2 is an infinite set of godel numbers whos functions can be parsed by a UTM.
each of these functions has independant probability of 50% of answering if the input function
does not halt, otherwise it will return DONTKNOW.
As an example.
the program with godel number 999 is
10 goto 10
UTM(2, 999) = NOTHALT (ignoring the parameter of function 999)
UTM(6, 999) = DONTKNOW
UTM(33, 999) = NOTHALT
UTM(655, 999) = DONTKNOW
...
the program with godel number 1000 is
10 print 10
UTM(2, 1000) = DONTKNOW
UTM(6, 1000) = DONTKNOW
UTM(33, 1000) = DONTKNOW
UTM(655, 1000) = DONTKNOW
From these outputs we can determine *without running the programs*
1/ program 999 does not halt
2/ program 1000 halts with probability of error 1/16.
Herc
Bryan Olson
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
>
> Is this debunked already?
Essentially, yes. The advocates of the 3-way outcome never
presented a precise definition for (c), which prevents rigorous
treatment. We do know that there *is* a TM that answers (a) if
and only if a is correct, and no TM that always returns one
of the three answers above can do that.
--
--Bryan
Simon G Best
> "Simon G Best" <s.g....@btopenworld.com> wrote
>
>>|-|erc wrote:
>>
>>>"Simon G Best" <s.g....@btopenworld.com> wrote in
>>>
>>>>|-|erc wrote:
>>>
>>[...]
>>
>>>>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
>>>>that it's "safe to assume" the opposite.
>>>
>>>If we *label* HypotheticalFunction() as an assumption then we can assume it.
>>
>>Certainly an assumption is an assumption. That does not contradict what
>>I said.
>
> fraid so.
>
> if you have NOT proven x, i may assume !x T/F
And that still doesn't mean it's a "safe" assumption.
[...]
>>
>>Do you see the contradiction now?
>
> i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
> only one result of the halt function, to determine the opposite (does not halt)
> you have to trial infinite n.
That doesn't work. A Turing Machine using that method will never halt,
because it will never "trial infinite n" in any finite amount of time.
Surely this is just utterly obvious?
[...]
>>
>>But, for all functions f, for all inputs a, where f does not halt on a,
>>your 'solution' never determines that f does not halt on a.
>>
>>It's no better than just running the UTM on (f, a) and waiting to see
>>whether or not it ever halts.
>>
>>Indeed, that is really all your 'solution' is!
>
> not at all, that was just a trivial *example* of the solution using clumsy UTMs.
> the idea works for an infinite set of smart phalt functions, or the opposite! an
> infinite set of nohalt functions.
But it *doesn't work*.
> here's a better example.
>
> NHalt2() = {2, 6, 33, 655, ..}
>
> NHalt2 is an infinite set of godel numbers whos functions can be parsed by a UTM.
>
> each of these functions has independant probability of 50% of answering if the input function
> does not halt, otherwise it will return DONTKNOW.
>
> As an example.
>
> the program with godel number 999 is
>
> 10 goto 10
>
> UTM(2, 999) = NOTHALT (ignoring the parameter of function 999)
> UTM(6, 999) = DONTKNOW
> UTM(33, 999) = NOTHALT
> UTM(655, 999) = DONTKNOW
> ...
Except that you haven't provided a way to actually list the elements of
NHalt2. Indeed, no Turing Machine can list the elements of NHalt2, the
proof being fairly similar to the proof I quickly sketched for the
nonexistence of a Turing Machine that could list the elements of AllHalt.
Without such a Turing Machine, you can't actually have a Turing Machine
applying your method.
> the program with godel number 1000 is
>
> 10 print 10
>
> UTM(2, 1000) = DONTKNOW
> UTM(6, 1000) = DONTKNOW
> UTM(33, 1000) = DONTKNOW
> UTM(655, 1000) = DONTKNOW
>
> From these outputs we can determine *without running the programs*
> 1/ program 999 does not halt
> 2/ program 1000 halts with probability of error 1/16.
That would be an heuristic, *not* a general solution to the Halting Problem.
Simon
|-|erc
> |-|erc wrote:
> > "Simon G Best" <s.g....@btopenworld.com> wrote
> >
> >>|-|erc wrote:
> >>
> >>>"Simon G Best" <s.g....@btopenworld.com> wrote in
> >>>
> >>>>|-|erc wrote:
> >>>
> >>[...]
> >>
> >>>>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
> >>>>that it's "safe to assume" the opposite.
> >>>
> >>>If we *label* HypotheticalFunction() as an assumption then we can assume it.
> >>
> >>Certainly an assumption is an assumption. That does not contradict what
> >>I said.
> >
> > fraid so.
> >
> > if you have NOT proven x, i may assume !x T/F
>
> And that still doesn't mean it's a "safe" assumption.
You mean I *can assume* halt exists, but it's NOT *safe to assume* halt exists
in this domain of discourse??
You are splitting a fine hair between what is formally correct for me to write
and one particular colloquial meaning of "safe".
<unsnip>
but how do you prove one program cannot recognise the other?
it is your burden to show they can't. otherwise we are safe to assume
a COMPLETE ALL KNOWING halt program can be written
</unsnip>
>
> [...]
> >>
> >>Do you see the contradiction now?
> >
> > i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
> > only one result of the halt function, to determine the opposite (does not halt)
> > you have to trial infinite n.
>
> That doesn't work. A Turing Machine using that method will never halt,
> because it will never "trial infinite n" in any finite amount of time.
> Surely this is just utterly obvious?
The halt machine runs for 1 microsecond and outputs
"program 922 halts with probability 0.999999999999999"
On a second trial, after 1 second it outputs
"program 922 halts with probability 0.9999999999999999999999999999999999"
After 10 minutes it outputs
"program 999 halts with probability 0.999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999999"
The halt machine runs for 100 microseconds on another input,
"program 833 does not halt"
and again
"program 99484 does not halt"
The halt machine does halt for one output value, and gives accurate information for the other.
The infinite run allows it to
1/ still give perfectly useful results
2/ evade ANY contradiction
>
> [...]
> >>
> >>But, for all functions f, for all inputs a, where f does not halt on a,
> >>your 'solution' never determines that f does not halt on a.
> >>
> >>It's no better than just running the UTM on (f, a) and waiting to see
> >>whether or not it ever halts.
> >>
> >>Indeed, that is really all your 'solution' is!
> >
> > not at all, that was just a trivial *example* of the solution using clumsy UTMs.
> > the idea works for an infinite set of smart phalt functions, or the opposite! an
> > infinite set of nohalt functions.
>
> But it *doesn't work*.
assumption
>
> > here's a better example.
> >
> > NHalt2() = {2, 6, 33, 655, ..}
> >
> > NHalt2 is an infinite set of godel numbers whos functions can be parsed by a UTM.
> >
> > each of these functions has independant probability of 50% of answering if the input function
> > does not halt, otherwise it will return DONTKNOW.
> >
> > As an example.
> >
> > the program with godel number 999 is
> >
> > 10 goto 10
> >
> > UTM(2, 999) = NOTHALT (ignoring the parameter of function 999)
> > UTM(6, 999) = DONTKNOW
> > UTM(33, 999) = NOTHALT
> > UTM(655, 999) = DONTKNOW
> > ...
>
> Except that you haven't provided a way to actually list the elements of
> NHalt2. Indeed, no Turing Machine can list the elements of NHalt2, the
> proof being fairly similar to the proof I quickly sketched for the
> nonexistence of a Turing Machine that could list the elements of AllHalt.
assumption
>
> Without such a Turing Machine, you can't actually have a Turing Machine
> applying your method.
falicious argument. "The halt program is not written, that proves it doesn't exist."
>
> > the program with godel number 1000 is
> >
> > 10 print 10
> >
> > UTM(2, 1000) = DONTKNOW
> > UTM(6, 1000) = DONTKNOW
> > UTM(33, 1000) = DONTKNOW
> > UTM(655, 1000) = DONTKNOW
> >
> > From these outputs we can determine *without running the programs*
> > 1/ program 999 does not halt
> > 2/ program 1000 halts with probability of error 1/16.
>
> That would be an heuristic, *not* a general solution to the Halting Problem.
look up heuristic, then look up solution.
anyone else want to actually disprove NHalt2 can exist?
Atleast now we know why everyone here is so stubborn. YOU'VE GOT 2 FACTS!!
1/ theres a proof that halt has a contradiction
AND
2/ NO ONE'S WRITTEN A HALT FUNCTION
must be true, when 1 fails see 2
Herc
Simon G Best
> "Simon G Best" <s.g....@btopenworld.com> wrote in
>
>>|-|erc wrote:
>>
>>>"Simon G Best" <s.g....@btopenworld.com> wrote
>>>
>>>>|-|erc wrote:
>>>>
>>>>>"Simon G Best" <s.g....@btopenworld.com> wrote in
>>>>>
>>>>>>|-|erc wrote:
>>>>>
>>>>[...]
>>>>
>>>>>>No, we are *not* "safe to assume" that. A lack of proof *does not* mean
>>>>>>that it's "safe to assume" the opposite.
>>>>>
>>>>>If we *label* HypotheticalFunction() as an assumption then we can assume it.
>>>>
>>>>Certainly an assumption is an assumption. That does not contradict what
>>>>I said.
>>>
>>>fraid so.
>>>
>>>if you have NOT proven x, i may assume !x T/F
>>
>>And that still doesn't mean it's a "safe" assumption.
>
> You mean I *can assume* halt exists, but it's NOT *safe to assume* halt exists
> in this domain of discourse??
Indeed - an assumption may turn out to be incorrect, and a lack of
disproof of such an assumption does not itself mean that it's unlikely
to be incorrect.
> You are splitting a fine hair between what is formally correct for me to write
> and one particular colloquial meaning of "safe".
So, what did you mean by "safe"?
> <unsnip>
> but how do you prove one program cannot recognise the other?
>
> it is your burden to show they can't. otherwise we are safe to assume
> a COMPLETE ALL KNOWING halt program can be written
> </unsnip>
Such an assumption would be wrong, as it's already been proven that no
such program (for a Universal Turing Machine) could be written. How
would such a wrong assumption be "safe"?
>>[...]
>>
>>>>Do you see the contradiction now?
>>>
>>>i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
>>>only one result of the halt function, to determine the opposite (does not halt)
>>>you have to trial infinite n.
>>
>>That doesn't work. A Turing Machine using that method will never halt,
>>because it will never "trial infinite n" in any finite amount of time.
>>Surely this is just utterly obvious?
>
> The halt machine runs for 1 microsecond and outputs
> "program 922 halts with probability 0.999999999999999"
Which would be wrong. Either the probability of program 922 halting is
one, or it is zero. After all, Turing Machines are completely
deterministic.
> On a second trial, after 1 second it outputs
> "program 922 halts with probability 0.9999999999999999999999999999999999"
Which would again be wrong, for the same reason.
> After 10 minutes it outputs
> "program 999 halts with probability 0.999999999999999999999999999999999
> 99999999999999999999999999999999999999999999999999999999999999
> 99999999999999999999999999999999999999999999999999999999999999"
And, again, wrong.
> The halt machine runs for 100 microseconds on another input,
> "program 833 does not halt"
>
> and again
> "program 99484 does not halt"
Those two would be right.
> The halt machine does halt for one output value, and gives accurate information for the other.
Nope. The information it gives "for the other" is always wrong.
> The infinite run allows it to
> 1/ still give perfectly useful results
> 2/ evade ANY contradiction
Running it forever, and waiting an infinite amount of time for its final
results, is no better than just running the Turing Machine in question,
on the input in question, and waiting to see whether or not it halts
before an infinite amount of time has passed. We don't need your
'solution' for that!
>>[...]
>>
>>>>But, for all functions f, for all inputs a, where f does not halt on a,
>>>>your 'solution' never determines that f does not halt on a.
>>>>
>>>>It's no better than just running the UTM on (f, a) and waiting to see
>>>>whether or not it ever halts.
>>>>
>>>>Indeed, that is really all your 'solution' is!
>>>
>>>not at all, that was just a trivial *example* of the solution using clumsy UTMs.
>>>the idea works for an infinite set of smart phalt functions, or the opposite! an
>>>infinite set of nohalt functions.
>>
>>But it *doesn't work*.
>
> assumption
No. It is not an assumption, it's already been proved that no Turing
Machine can solve the Halting Problem for all Turing Machines, for all
inputs.
[...]
>>
>>Except that you haven't provided a way to actually list the elements of
>>NHalt2. Indeed, no Turing Machine can list the elements of NHalt2, the
>>proof being fairly similar to the proof I quickly sketched for the
>>nonexistence of a Turing Machine that could list the elements of AllHalt.
>
> assumption
No, again, it's not an assumption.
Here's a quick sketch of a proof that no Turing Machine can list the
elements of NHalt2:-
Let's assume that there exists a Turing Machine, N, which lists the
elements of NHalt2.
Given N, we can easily construct another Turing Machine, H, which takes
the pair (f, a) as input, and does the following.
First, it simulates f(a) for a finite number of steps. If, by the end
of that simulation, f(a) has halted, H outputs 'halts', and halts. If,
instead, f(a) hasn't halted, H simulates N for enough steps for N to
give one element of NHalt2, n_1. It then simulates n_1(f, a). If
n_1(f, a) outputs 'does not halt', H outputs 'does not halt', and halts.
Otherwise, it resumes its simulation of f(a) for a further finite
number of steps. If f(a) still hasn't halted, it resumes its simulation
of N to get the next element of NHalt2, n_2, and simulates n_2(f, a),
and so on.
H keeps repeating this process until either f(a) halts, or an n produced
by N is reached such that n(f, a) outputs 'does not halt'.
If f(a) halts, H will reach that point in a finite number of steps. If
f(a) never halts, it will reach an n produced by N such that n(f, a)
outputs 'does not halt' in a finite number of steps. So, either way, H
will reach a final result in a finite number of steps.
We already have the classic proof that H cannot exist. Therefore, N
cannot exist.
>>Without such a Turing Machine,
a Turing Machine listing the elements of NHalt2, that is,
>>you can't actually have a Turing Machine
>>applying your method.
>
> falicious argument. "The halt program is not written, that proves it doesn't exist."
I never said that, and it certainly wasn't my argument. My argument was
not based on "The halt program" having not been /written/, but on the
/unwritability/ of a program (for Universal Turing Machines) /to list
the elements of NHalt2/.
>>>the program with godel number 1000 is
>>>
>>>10 print 10
>>>
>>>UTM(2, 1000) = DONTKNOW
>>>UTM(6, 1000) = DONTKNOW
>>>UTM(33, 1000) = DONTKNOW
>>>UTM(655, 1000) = DONTKNOW
>>>
>>>From these outputs we can determine *without running the programs*
>>>1/ program 999 does not halt
>>>2/ program 1000 halts with probability of error 1/16.
>>
>>That would be an heuristic, *not* a general solution to the Halting Problem.
>
> look up heuristic, then look up solution.
"*General* solution to the *Halting Problem*" is what I said.
"Solution" in the mathematical sense. "General solution" in the
mathematical sense.
An heuristic is *not* a general solution to the Halting Problem, as
there are cases in which it either fails to yield a solution, or gives
the wrong result.
> anyone else want to actually disprove NHalt2 can exist?
You seem to be confusing sets with Turing Machines that list the
elements of those sets. There certainly are sets that match your
definition of NHalt2 that exist - an infinite number of such sets, in fact!
> Atleast now we know why everyone here is so stubborn. YOU'VE GOT 2 FACTS!!
We've got rather more than just two facts.
> 1/ theres a proof that halt has a contradiction
There are indeed proofs (including the classic 'loop if halts' proof)
that the existence of a Turing Machine that solves the Halting Problem
in the general case (for all Turing Machines, for all inputs) implies a
contradiction, and that therefore no such Turing Machine can exist.
> AND
> 2/ NO ONE'S WRITTEN A HALT FUNCTION
>
> must be true, when 1 fails see 2
Uh?
Simon
|-|erc
I just meant this :
> > it is your burden to show they can't. otherwise we CAN assume
> > a COMPLETE ALL KNOWING halt program can be written
I don't know why you think safe implies absolute truth / guaranteed assumption here.
safe <=> guaranteed ??
I don't see 'safe to assume' being a stronger statement than "we can assume".
"a safe assumption" could be interpreted as something more than an assumption.
>
> > <unsnip>
> > but how do you prove one program cannot recognise the other?
> >
> > it is your burden to show they can't. otherwise we are safe to assume
> > a COMPLETE ALL KNOWING halt program can be written
> > </unsnip>
>
> Such an assumption would be wrong, as it's already been proven that no
> such program (for a Universal Turing Machine) could be written. How
> would such a wrong assumption be "safe"?
because you haven't proven a 3 valued system wont work, everyone here
is assuming it will be wrong most of the time. it may just output 'don't know' on
the vary rare occasions it faces a loop-if-halt type program.
software-can-recognise loop-if-halt construct -> halt function may be entirely possible
>
> >>[...]
> >>
> >>>>Do you see the contradiction now?
> >>>
> >>>i think so, that was the 1st attempt at an infinite set of phalt. now i'm using
> >>>only one result of the halt function, to determine the opposite (does not halt)
> >>>you have to trial infinite n.
> >>
> >>That doesn't work. A Turing Machine using that method will never halt,
> >>because it will never "trial infinite n" in any finite amount of time.
> >>Surely this is just utterly obvious?
> >
> > The halt machine runs for 1 microsecond and outputs
> > "program 922 halts with probability 0.999999999999999"
>
> Which would be wrong. Either the probability of program 922 halting is
> one, or it is zero. After all, Turing Machines are completely
> deterministic.
Back to the probability soln..
you misinterpret. each phalt function declares the halt value with 50% chance
of being correct. if 100 phalt functions all declare 'don't know' then we have
0.5^100 probability of error in the result.
I got the idea from the prime witness algorithm. There is no algorithm (atleast not
last century) to determine if a number is prime in polynomial time. BUT, an
algorithm exists that on every iteration determines if a number is prime within
50% chance of error.
Basically, over half of numbers from 1..p are witnesses to compositeness. A factor
is a basic witness to compositeness, but another defn of witness makes them
more numerous. So, to determine if the number is prime, take a random sample
of numbers from 1..p and do the test. If you test 100 numbers and none of
them are witnesses, then you have 1 - 0.5^100 probability that the number is prime.
A Halt function can work the same, its not a straight forward YES/NO output but
its still a practical soln.
>
> > On a second trial, after 1 second it outputs
> > "program 922 halts with probability 0.9999999999999999999999999999999999"
>
> Which would again be wrong, for the same reason.
Why would such a hypothetical output be wrong? Its just a program spec.
>
> > After 10 minutes it outputs
> > "program 999 halts with probability 0.999999999999999999999999999999999
> > 99999999999999999999999999999999999999999999999999999999999999
> > 99999999999999999999999999999999999999999999999999999999999999"
>
> And, again, wrong.
>
> > The halt machine runs for 100 microseconds on another input,
> > "program 833 does not halt"
> >
> > and again
> > "program 99484 does not halt"
>
> Those two would be right.
>
> > The halt machine does halt for one output value, and gives accurate information for the other.
>
> Nope. The information it gives "for the other" is always wrong.
>
> > The infinite run allows it to
> > 1/ still give perfectly useful results
> > 2/ evade ANY contradiction
>
> Running it forever, and waiting an infinite amount of time for its final
> results, is no better than just running the Turing Machine in question,
> on the input in question, and waiting to see whether or not it halts
> before an infinite amount of time has passed. We don't need your
> 'solution' for that!
You DONT run it for infinite time. The probability of error reduces inverse exponentially,
if NHalt2 existed it would give answers very quickly. The halting proof however
requires an absolute commital, 0.9999999999999999999999999 chance that the
program will always halt is not good enough to get a contradiction.
Right.
A PHalt sequence and an NHalt sequence cannot both be possible. Since
a PHalt sequence can be constructed with UTMs, NHalt is impossible.
Can you disprove a PHalt sequence is computable? Each is a partial halt function
that has 50% chance of stating any given f(a) will halt, otherwise it returns DONTKNOW.
Herc
Simon G Best
follow-ups back to just comp.theory and sci.logic.
|-|erc wrote:
> "Simon G Best" <s.g....@btopenworld.com> wrote
>
>>|-|erc wrote:
>>
>>>"Simon G Best" <s.g....@btopenworld.com> wrote in
>>>
[...]
>>
>>So, what did you mean by "safe"?
>
> I just meant this :
>
>>>it is your burden to show they can't. otherwise we CAN assume
>>>a COMPLETE ALL KNOWING halt program can be written
>
> I don't know why you think safe implies absolute truth / guaranteed assumption here.
I don't. I think "safe to assume" means that we could make whatever
assumption it is, and that assumption is unlikely to be wrong, or, if it
is wrong, it isn't really going to matter that it's wrong. I thought it
was "safe to assume" that that was the sort of thing you meant by "safe".
> safe <=> guaranteed ??
>
> I don't see 'safe to assume' being a stronger statement than "we can assume".
> "a safe assumption" could be interpreted as something more than an assumption.
This is getting silly. Perhaps Kent Paul Dolan's right? Would it be
"safe to assume" that he's right about you? After all, it's certainly
the case that I /can/ assume that he's right about you.
>>><unsnip>
>>>but how do you prove one program cannot recognise the other?
>>>
>>>it is your burden to show they can't. otherwise we are safe to assume
>>>a COMPLETE ALL KNOWING halt program can be written
>>></unsnip>
>>
>>Such an assumption would be wrong, as it's already been proven that no
>>such program (for a Universal Turing Machine) could be written. How
>>would such a wrong assumption be "safe"?
>
> because you haven't proven a 3 valued system wont work, everyone here
> is assuming it will be wrong most of the time. it may just output 'don't know' on
> the vary rare occasions it faces a loop-if-halt type program.
>
> software-can-recognise loop-if-halt construct -> halt function may be
> entirely possible
You said, "a COMPLETE ALL KNOWING halt program", but now you're saying
"it may just output 'don't know' on the vary rare occasions it faces a
loop-if-halt type program." So, you concede that it could not be "a
COMPLETE ALL KNOWING halt program" after all.
The Halting Problem /itself/ is 'two-valued', in the sense that each
Turing Machine (TM) on each input either halts or does not halt. Those
are the only two possibilities.
A general solution to the Halting Problem, therefore, is one which is
also 'two-valued'. If TM M halts on input x, the solution to the
problem of whether or not M halts on x is that it does halt on x. If TM
M does not halt on x, the solution to that same problem is that it
doesn't halt.
A "3 valued system", which ever outputs "'don't know'", is therefore
clearly not a general solution to the Halting Problem.
[...]
>>>
>>>The halt machine runs for 1 microsecond and outputs
>>>"program 922 halts with probability 0.999999999999999"
>>
>>Which would be wrong. Either the probability of program 922 halting is
>>one, or it is zero. After all, Turing Machines are completely
>>deterministic.
>
> Back to the probability soln..
>
> you misinterpret. each phalt function declares the halt value with 50% chance
> of being correct. if 100 phalt functions all declare 'don't know' then we have
> 0.5^100 probability of error in the result.
>
> I got the idea from the prime witness algorithm. [...]
>
> A Halt function can work the same, its not a straight forward YES/NO output but
> its still a practical soln.
Whether or not it would be a practical 'solution', the Halting Problem
is a /mathematical/ problem.
>>>On a second trial, after 1 second it outputs
>>>"program 922 halts with probability 0.9999999999999999999999999999999999"
>>
>>Which would again be wrong, for the same reason.
>
> Why would such a hypothetical output be wrong? Its just a program spec.
It might be /your/ "program spec", but it does *not* match the Halting
Problem. The Halting Problem is itself the specification of relevance
to the Halting Problem.
[...]
>>
>>Running it forever, and waiting an infinite amount of time for its final
>>results, is no better than just running the Turing Machine in question,
>>on the input in question, and waiting to see whether or not it halts
>>before an infinite amount of time has passed. We don't need your
>>'solution' for that!
>
> You DONT run it for infinite time. The probability of error reduces inverse exponentially,
> if NHalt2 existed it would give answers very quickly. The halting proof however
> requires an absolute commital, 0.9999999999999999999999999 chance that the
> program will always halt is not good enough to get a contradiction.
It's the Halting /Problem/ that "requires an absolute commital".
[...]
>>
>>Here's a quick sketch of a proof that no Turing Machine can list the
>>elements of NHalt2:-
>>
[...]
>
> Right.
>
> A PHalt sequence and an NHalt sequence cannot both be possible.
You haven't said what "NHalt" is.
And "A PHalt sequence" certainly does exist, if, by "PHalt sequence",
you mean a list of the elements of AllHalt. But no Turing Machine can
compute that list.
> Since
> a PHalt sequence can be constructed with UTMs, NHalt is impossible.
What do you mean by "a PHalt sequence can be constructed with UTMs"?
Did you mean that a UTM can be used to compute a list of the elements of
AllHalt?
[...]
>
> Can you disprove a PHalt sequence is computable?
I sketched such a disproof in an earlier post.
> Each is a partial halt function
> that has 50% chance of stating any given f(a) will halt, otherwise it returns DONTKNOW.
Not according to your second post in this thread
(news:zc9%c.21947$D7.1...@news-server.bigpond.net.au), in which you said:-
> An algorithm produces a set of godel numbers for pHalt programs.
> AllHalt() = {1, 5, 20, 55, 999, 23838... }
>
> Each of these programs is a partial halt function that behaves correctly
> with the outputs :
>
> 1/ halts
>
> 2/ does not halt
>
> 3/ don't know
You really do need to /clearly/ define things, and *stick* to those
definitions.
Simon
|-|erc
> You haven't said why you cross-posted to sci.math, so I'm setting the
> follow-ups back to just comp.theory and sci.logic.
>
> |-|erc wrote:
> > "Simon G Best" <s.g....@btopenworld.com> wrote
> >
> >>|-|erc wrote:
> >>
> >>>"Simon G Best" <s.g....@btopenworld.com> wrote in
> >>>
> [...]
> >>
> >>So, what did you mean by "safe"?
> >
> > I just meant this :
> >
> >>>it is your burden to show they can't. otherwise we CAN assume
> >>>a COMPLETE ALL KNOWING halt program can be written
> >
> > I don't know why you think safe implies absolute truth / guaranteed assumption here.
>
> I don't. I think "safe to assume" means that we could make whatever
> assumption it is, and that assumption is unlikely to be wrong, or, if it
> is wrong, it isn't really going to matter that it's wrong. I thought it
> was "safe to assume" that that was the sort of thing you meant by "safe".
Personally I think halt is a trivial function, the halting proof is semantically
overloaded and misinterpreted, even incorrect. So if no one here can disprove
a 3 valued halt function, or my probability halt solution I will assume halt can
be programmed.
>
> > safe <=> guaranteed ??
> >
> > I don't see 'safe to assume' being a stronger statement than "we can assume".
> > "a safe assumption" could be interpreted as something more than an assumption.
>
> This is getting silly. Perhaps Kent Paul Dolan's right? Would it be
> "safe to assume" that he's right about you? After all, it's certainly
> the case that I /can/ assume that he's right about you.
i'm just here to point out mathematics its not a personality forum
>
> >>><unsnip>
> >>>but how do you prove one program cannot recognise the other?
> >>>
> >>>it is your burden to show they can't. otherwise we are safe to assume
> >>>a COMPLETE ALL KNOWING halt program can be written
> >>></unsnip>
> >>
> >>Such an assumption would be wrong, as it's already been proven that no
> >>such program (for a Universal Turing Machine) could be written. How
> >>would such a wrong assumption be "safe"?
> >
> > because you haven't proven a 3 valued system wont work, everyone here
> > is assuming it will be wrong most of the time. it may just output 'don't know' on
> > the vary rare occasions it faces a loop-if-halt type program.
> >
> > software-can-recognise loop-if-halt construct -> halt function may be
> > entirely possible
>
> You said, "a COMPLETE ALL KNOWING halt program", but now you're saying
> "it may just output 'don't know' on the vary rare occasions it faces a
> loop-if-halt type program." So, you concede that it could not be "a
> COMPLETE ALL KNOWING halt program" after all.
substitute self-referential for dont-know here and it outputs the correct
value for EVERY program.
>
> The Halting Problem /itself/ is 'two-valued', in the sense that each
> Turing Machine (TM) on each input either halts or does not halt. Those
> are the only two possibilities.
right
>
> A general solution to the Halting Problem, therefore, is one which is
> also 'two-valued'. If TM M halts on input x, the solution to the
> problem of whether or not M halts on x is that it does halt on x. If TM
> M does not halt on x, the solution to that same problem is that it
> doesn't halt.
the standard solution
>
> A "3 valued system", which ever outputs "'don't know'", is therefore
> clearly not a general solution to the Halting Problem.
wrong, self-referential is a perfectly valid output for this domain
>
> [...]
> >>>
> >>>The halt machine runs for 1 microsecond and outputs
> >>>"program 922 halts with probability 0.999999999999999"
> >>
> >>Which would be wrong. Either the probability of program 922 halting is
> >>one, or it is zero. After all, Turing Machines are completely
> >>deterministic.
> >
> > Back to the probability soln..
> >
> > you misinterpret. each phalt function declares the halt value with 50% chance
> > of being correct. if 100 phalt functions all declare 'don't know' then we have
> > 0.5^100 probability of error in the result.
> >
> > I got the idea from the prime witness algorithm. [...]
> >
> > A Halt function can work the same, its not a straight forward YES/NO output but
> > its still a practical soln.
>
> Whether or not it would be a practical 'solution', the Halting Problem
> is a /mathematical/ problem.
this is sheer idiocy. a program can be written to give arbitrary precision to
any confidence interval under 1.0 for the correct output. when did probability
lie outside mathematics? did quantum mechanics fail to qualify as a physical
theory because it used probability? NO it got incorporated as the underlying
mechanism of what is going on.
>
> >>>On a second trial, after 1 second it outputs
> >>>"program 922 halts with probability 0.9999999999999999999999999999999999"
> >>
> >>Which would again be wrong, for the same reason.
> >
> > Why would such a hypothetical output be wrong? Its just a program spec.
>
> It might be /your/ "program spec", but it does *not* match the Halting
> Problem. The Halting Problem is itself the specification of relevance
> to the Halting Problem.
1 Classic halting problem : halt(555, 5) = "true"
2 Possible halting solution : halt(555, 5) = "true", confidence value=99.99999%
The halting problem looks solved here, you cant see the forrest for the trees.
>
> [...]
> >>
> >>Running it forever, and waiting an infinite amount of time for its final
> >>results, is no better than just running the Turing Machine in question,
> >>on the input in question, and waiting to see whether or not it halts
> >>before an infinite amount of time has passed. We don't need your
> >>'solution' for that!
> >
> > You DONT run it for infinite time. The probability of error reduces inverse exponentially,
> > if NHalt2 existed it would give answers very quickly. The halting proof however
> > requires an absolute commital, 0.9999999999999999999999999 chance that the
> > program will always halt is not good enough to get a contradiction.
>
> It's the Halting /Problem/ that "requires an absolute commital".
That a general purpose algorithm can be written that determines the halting
value of any input function. What PROBLEM are you talking about?
>
> [...]
> >>
> >>Here's a quick sketch of a proof that no Turing Machine can list the
> >>elements of NHalt2:-
> >>
> [...]
> >
> > Right.
> >
> > A PHalt sequence and an NHalt sequence cannot both be possible.
>
> You haven't said what "NHalt" is.
NHalt is just NHalt2. PHalt is a set of functions that output values {Halt, DONTKNOW}
NHalt is a set of functions that output {NotHalt, DONTKNOW}
>
> And "A PHalt sequence" certainly does exist, if, by "PHalt sequence",
> you mean a list of the elements of AllHalt. But no Turing Machine can
> compute that list.
You have a strange meaning of exist. This is unsubstantiated.
>
> > Since
> > a PHalt sequence can be constructed with UTMs, NHalt is impossible.
>
> What do you mean by "a PHalt sequence can be constructed with UTMs"?
> Did you mean that a UTM can be used to compute a list of the elements of
> AllHalt?
Its like talking to someone with amnesia, forget Kent he's a moron who
takes antipsychotics all day.
I ditched the 3 valued model 5 posts ago.
----
What I meant to write was :
halt(f, a) -> En, n e AllHalt, UTM(n, f(a))=true
!halt(f, a) -> An, n e AllHalt, UTM(n, f(a))='don't know'
as an example, AllHalt could be an infinite set of Universal Turing Machines,
but they timeout after various amounts of time. If the parameter f(a) halted
then it outputs TRUE, otherwise DONTKNOW. Since the number of these
partial Halt functions is infinite, we should come across one with enough
test cycles to determine if any function halts.
Can you see how a PHalt sequence, (what I labelled as AllHalt) can be constructed?
Similar to G Frege idea of using a UTM for various timeouts to see if it halts.
By itself this is still useless as it only gives one output value, HALTS. But if
each pHalt function has 50% chance of being correct (something more powerful
than the UTM), then determining NOTHALT is a simple probabilistic procedure.
>
> [...]
> >
> > Can you disprove a PHalt sequence is computable?
>
> I sketched such a disproof in an earlier post.
that was the old 3 value model.
>
> > Each is a partial halt function
> > that has 50% chance of stating any given f(a) will halt, otherwise it returns DONTKNOW.
>
> Not according to your second post in this thread
> (news:zc9%c.21947$D7.1...@news-server.bigpond.net.au), in which you said:-
>
> > An algorithm produces a set of godel numbers for pHalt programs.
> > AllHalt() = {1, 5, 20, 55, 999, 23838... }
> >
> > Each of these programs is a partial halt function that behaves correctly
> > with the outputs :
> >
> > 1/ halts
> >
> > 2/ does not halt
> >
> > 3/ don't know
>
> You really do need to /clearly/ define things, and *stick* to those
> definitions.
You have no recollection that I modified the model ??
----
What I meant to write was :
halt(f, a) -> En, n e AllHalt, UTM(n, f(a))=true
!halt(f, a) -> An, n e AllHalt, UTM(n, f(a))='don't know'
try to keep up, its like you completely blanked out and forgot the whole thread
making trivial out of context unnecessary corrections from examining one post.
halt(f, a) -> pHalt2(n) -> P(UTM(n, f(a))='halt') = 0.5
!halt(f, a) -> pHalt2(n) -> UTM(n, f(a))='don't know'
Herc
Simon G Best
|-|erc wrote:
> "Simon G Best" <s.g....@btopenworld.com> wrote in
>
[...]
>
> Its like talking to someone with amnesia, forget Kent he's a moron who
> takes antipsychotics all day.
Well, I just did a bit of a search through some of your recentish posts
(just a few months ago) in comp.theory. Here's what I found, in
news:/1BiKc.5182$K53....@news-server.bigpond.net.au:
> it will be globally public this year that I am Adam, that the government has been
> describing my life to you for decades over media, and the 100s who laughed on
> usenet and never got it will go down in history as the greatest fools.
>
> there's half a dozen x-files expisodes about me, different character each time
> all describing different powers of Adam.
>
> listen to all top 50 songs on MTV this week, half of them are about the REAL SAVIOUR.
>
>
> In a Universe where atheism is true.
>
> A 100 million dollar movie starring a man J.C. in a show called TRUEman SHOW
> shouldn't happen.
>
>
> Herc
> if god was one of us, just a slog like one of us
Seems Kent Paul Dolan was right about you, and that it would just be a
waste of time for me to continue 'discussing' your 'solution(s)' with you.
Simon
|-|erc
sheesh, I don't post a thing all month, I made some mathematical suggestions
and all of a sudden I'm not worth it. You'll learn the pecking order the hard way then.
I don't mind people abusing me but interrupting others to gang up on me is fucking
coward like Kent, you'll find out if I really do have license to kill
Herc
Wally Anglesea
"Simon G Best" <s.g....@btopenworld.com> wrote in message
news:4141519B...@btopenworld.com...
Simon, Herc is a known lunatic. He got arrested for threatening to put
poison in foodstuffs in Australia. He also has a restraining order on him.
He's written threatening stuff left right, and centre. The only people who
know about him in Townsville are the Police, the local booby hatch, and the
welfare offices (he's never actually been employed).
Howard
"|-|erc" <go...@beauty.com> wrote in message
news:iJd0d.25559$D7....@news-server.bigpond.net.au...
>
> I don't mind people abusing me but interrupting others to gang up on me is
fucking
> coward like Kent, you'll find out if I really do have license to kill
>
> Herc
Now, now, dear boy... you know what happens when you make threats like that.
Don't you remember last time? Best take your meds and have a nice nap.
We'll be back to check on you soon...
Kent Paul Dolan
> "Simon G Best" <s.g....@btopenworld.com> wrote:
>> |-|erc wrote:
>>> Its like talking to someone with amnesia,
Too bad Google Groups doesn't have amnesia, and your
long and colorful history of insanity is on display
for anyone to consult to form _their own_ judgement
of your capacity to engage in an intelligent
discussion.
>>> forget Kent he's a moron who takes
>>> antipsychotics all day.
As may be, though they're antidepressants (Welbutrin
and Depacote) and I stopped taking them around May.
My posting history is also on display, those who
think I can or cannot succeed at spotting Usenet
kooks early and accurately are welcome to do the
needed research to find the truth.
>> Well, I just did a bit of a search through some
>> of your recentish posts (just a few months ago)
>> in comp.theory.
>> Seems Kent Paul Dolan was right about you, and
>> that it would just be a waste of time for me to
>> continue 'discussing' your 'solution(s)' with
>> you.
> sheesh, I don't post a thing all month,
Herc, you've been proving your (in)abilities for
_years_, you don't take a month off and come back
sane, as you are proving at this very moment.
> I made some mathematical suggestions and all of a
> sudden I'm not worth it.
This isn't an "all of the sudden" worthlessness,
this is a "you play this game over and over and
over, wasting the time of people with better things
to do than cater to your eternal imbecility" long
term negative worth you have earned by dint of great
exertion.
I merely provided a window through which you could
be seen, I didn't choose the colors you used to form
your image in that window.
> You'll learn the pecking order the hard way then.
Threatening Simon for deciding that "a kook is a
kook is a kook" only reinforces your reputation, but
then you are self-evidently insane and so incapable
of understanding that rather obvious datum.
> I don't mind people abusing me but interrupting
> others to gang up on me is fucking coward like
> Kent,
When you have control of yourself, please do try to
rewrite that into English that parses.
> you'll find out if I really do have license to
> kill
===== selected archival quality quote by, =====
===== about, or appropriate to this author =====
[Edmond Wollmann bites off the big one,
one "xanthian":]
BWAHAHAHAHAHAHAHAHAHAHAHAHA!
You're trying to intimidate a teedotbee oldbie?
Good luck, Eddieeeeee.
Anvils away!
-- Cujo <cu...@petitmorte.net>
xanthian, cracking knuckles backwards with a mad,
familiar grin slowly spreading across his face.
===== selected archival quality quote by, =====
===== about, or appropriate to this author =====
All I have is this keyboard,
enmired in the paws of a raving lunatic...
-- xant...@Zorch.SF-Bay.ORG
|-|erc
>
> Threatening Simon for deciding that "a kook is a
"learn the pecking order" a threat? shows what retards can go for these days
you've got some catching up to do kook apprentice
Results 1 - 10 of about 101 for author:kent author:paul author:dolan kook. (0.65 seconds
Results 1 - 10 of about 1,860 for author:wally author:anglesea kook. (0.38 seconds
Herc
|-|erc
"Wally Anglesea" <wang...@spbigpondammersarevermin.net.au> wrote in
check the recent dates of this retarded kookaburra
Results 1 - 10 of about 1,860 for author:wally author:anglesea kook
Re: Wally the Trolls Style of posting and responding
... history of Wally's demonstrable Trolling posts and responses - notice how he never discusses the topic of any thread - that
makes him a Usenet Troll and a Kook ...
alt.astronomy - 10 Sep 2004 by Wally Anglesea - View Thread (19 articles)
Re: New results from Australian Telescope National Facility
AUK readded, kook. Since you tried to lie. Try again moron, I don't post twice idiot. ... I am sure they won't be giving you the
interview you wish for, kook. ...
alt.astronomy - 9 Sep 2004 by Wally Anglesea - View Thread (12 articles)
Re: Bizarre Matter found in Neutron Star
... is.net.cable.rogers.com... Sociopath now wants to discuss math with me - what a kook troll. HTML fixed. Do you *honestly* think
...
alt.astronomy - 9 Sep 2004 by Wally Anglesea - View Thread (13 articles)
Re: Trolls like to ruin the exchange of ideas
... Do try to keep your lies consistent. Regardless of your name, and whatever new incarnation you morph into, you will always be an
unoriginal parroting kook. ...
sci.astro - 9 Sep 2004 by Wally Anglesea - View Thread (58 articles)
Brian "Yoda" Stirling is Obsessed by me
Looky here. I hace my very own kook obsessing over me! ... Never had to pay full price for kook books. That way I save my money for
the science books. ...
alt.usenet.kooks - 9 Sep 2004 by Wally Anglesea - View Thread (1 article)
Re: Hurricane Frances hits LINE OF SOLLOG
... This one might fit the bill: <http://www.insurgent.org/~kook-faq/whiners.html#raisins> Ahh, a good one. Is it too early to
nominate? ...
alt.prophecies.nostradamus - 9 Sep 2004 by Wally Anglesea - View Thread (39 articles)
Re: DrPostman and the lighing rod
... Those non-existent photogrpahs? The mythical, made up, fake ones that a kook claims exist? ... I already told you, polaroids can
be altered,you babbling kook. ...
sci.astro - 9 Sep 2004 by Wally Anglesea - View Thread (5 articles)
Re: Dr_Postman and the lighing rod
... MAC. 2: You have NO PROOF WHATSOEVER that the alleged photo's evewn exist. No wonder you win so many kook awards. You are an
idiot.
sci.astro - 8 Sep 2004 by Wally Anglesea - View Thread (107 articles)
Re: Meteor sighting resembles fireworks display
... or any of your fantasies. Like any kook, you duck and weave when called on your fantasies. What fantasies? You and Carl should
just ...
sci.astro - 7 Sep 2004 by Wally Anglesea - View Thread (41 articles)
Re: VOTE! Usenet Kook Awards, August 2004
Friendly Neighbourhood Vote Wrangler is full of crap! Let me guess. You didn't get a nomination for the award you *really* wanted.
Now go piss up a rope.
alt.usenet.kooks - 7 Sep 2004 by Wally Anglesea - View Thread (287 articles)
Wally Anglesea
"|-|erc" <go...@beauty.com> wrote in message
news:G9p0d.26145$D7....@news-server.bigpond.net.au...
>
> "Wally Anglesea" <wang...@spbigpondammersarevermin.net.au> wrote in
>
> check the recent dates of this retarded kookaburra
Yeah, I make kooks dance, amongst other things.
By the way, for those looking, about a month ago, Herc got together with a
couple of buddies in an aus. hierarchy newsgroup, and discussed going on a
"tour", disrupting a few newsgroups.
Herc's a dangerous individual who threatened to poison foodstuffs. Was
arrested for it, and has at least one restraining order on him for
threatening behaviour.
He also claims he's the real "truman" and that we are all part of the show.
Apparently, satellites monitor him from space.
All of the above is verifiable.
It seems to all go away when he takes his anti-psychotic drugs, which is
only apparent.
|-|erc
> >
> > check the recent dates of this retarded kookaburra
>
> Yeah, I make kooks dance, amongst other things.
>
> By the way, for those looking, about a month ago, Herc got together with a
> couple of buddies in an aus. hierarchy newsgroup, and discussed going on a
> "tour", disrupting a few newsgroups.
>
> Herc's a dangerous individual who threatened to poison foodstuffs. Was
> arrested for it, and has at least one restraining order on him for
> threatening behaviour.
>
> He also claims he's the real "truman" and that we are all part of the show.
> Apparently, satellites monitor him from space.
>
> All of the above is verifiable.
>
the ONLY news story you have on me was dismissed in Supreme Court.
It has the following leading stories next to my arrest article (no criminal record).
this is from the article
Senior Constable Sean Janes objected to Cooper's application for bail
this is the top feature article
INVESTIGATOR FOUND GUILTY OF DEFAMING
Exactly how newspapers would respond to a dumb policeman who framed
the Truman.
In this section
Investigator found guilty of defaming Versace
Easter protest planned for Woomera
The end of dummy bidders?
Thwaites wants to name lab
Lab still getting Medicare money
Australians deported from China
Govt unmoved by Woomera grave digging
Pap smear lab named
Proposal to limit job-matching subsidies
'A cry for help' from drug abusers
A pensive nude will battle the elements
A century of voting and a hundred years of struggle
Move to renew military ties
Gay couples left out of court shift
Defects double in IVF: study
I am arrested. I am cleared in Supreme Court. The newspapers say
INVESTIGATOR WAS GUILTY
PROTEST PLANNED
GOVERNMENT UNMOVED
You are one stupid investigator Wally if you come to Townsville and can't
find evidence of the Truman. dozens of visitors here have already posted so
on usenet.
Herc
Wally Anglesea
Except that's NOT the story, is it, you babbling kook?
That is an ENTIRELY different story, it just happens to be on the same page.
>
>
> I am arrested. I am cleared in Supreme Court.
You were NOT cleared, you buffon.
>The newspapers say
> INVESTIGATOR WAS GUILTY
> PROTEST PLANNED
> GOVERNMENT UNMOVED
>
> You are one stupid investigator Wally if you come to Townsville and can't
> find evidence of the Truman.
Yeah, I *was* in Townsville, so why did you claim IU wasn't?
And the ONLY people who know about you are the Police, the local booby
hatch, and the welfare offices.
When will you ever get a job?
|-|erc
> > this is the top feature article
> > INVESTIGATOR FOUND GUILTY OF DEFAMING
> >
> > Exactly how newspapers would respond to a dumb policeman who framed
> > the Truman.
>
> Except that's NOT the story, is it, you babbling kook?
>
> That is an ENTIRELY different story, it just happens to be on the same page.
>
Do you think the newspaper knows how to put bikini ads next to the fishing section?
lawnmower ads in the gardening section? Rex Hunt was in the age the other month,
look up the leading story next to him being held by police story. The neighbouring
story next to the celebrity voices THE NEWSPAPERS OPINION. For him they
wrote ".... calls for fair hearing". Basically they wanted him charged so they'd get
more footage.
Look at a newspaper Wally, over half of the articles are juxtapositioned. My arrest
article had 2 main neighbouring articles. THE POLICE F*CKED UP, and
PROTESTS ARE PLANNED.
> >
> > You are one stupid investigator Wally if you come to Townsville and can't
> > find evidence of the Truman.
>
> Yeah, I *was* in Townsville, so why did you claim IU wasn't?
>
We agree on one thing.
Herc
Wally Anglesea
> "Wally Anglesea" <wang...@spbigpondammersarevermin.net.au> wrote
>> > this is the top feature article
>> > INVESTIGATOR FOUND GUILTY OF DEFAMING
>> >
>> > Exactly how newspapers would respond to a dumb policeman who framed
>> > the Truman.
>>
>> Except that's NOT the story, is it, you babbling kook?
>>
>> That is an ENTIRELY different story, it just happens to be on the same
>> page.
>>
>
> Do you think the newspaper knows how to put bikini ads next to the fishing
> section?
> lawnmower ads in the gardening section? Rex Hunt was in the age the other
> month,
> look up the leading story next to him being held by police story. The
> neighbouring
> story next to the celebrity voices THE NEWSPAPERS OPINION. For him they
> wrote ".... calls for fair hearing". Basically they wanted him charged so
> they'd get
> more footage.
>
> Look at a newspaper Wally, over half of the articles are juxtapositioned.
> My arrest
> article had 2 main neighbouring articles. THE POLICE F*CKED UP, and
> PROTESTS ARE PLANNED.
Having made you present your evidence of your kookiness,I will now leave it
to the intelligent people in the newsgroups you decided to troll to
recognise what a moron you are.
Thanks for playing Herc.
Why not show everyone the front page of the newspaper detailing your court
appearance?
Rob Duncan
"Kent Paul Dolan" <xant...@well.com> wrote
> >> Well, I just did a bit of a search through some
> >> of your recentish posts (just a few months ago)
> >> in comp.theory.
>
> >> Seems Kent Paul Dolan was right about you, and
> >> that it would just be a waste of time for me to
> >> continue 'discussing' your 'solution(s)' with
> >> you.
>
> > sheesh, I don't post a thing all month,
>
> Herc, you've been proving your (in)abilities for
> _years_, you don't take a month off and come back
> sane, as you are proving at this very moment.
I realize its fun to "poke the monkey," but if you believe what you say...
dont provoke him. Thats unkind.
Rob
Acme Diagnostics
I respect your valid opinion. I think Dolan did two or three
flames, and I remember thinking that was one too many. But I
wouldn't want to argue that judgement call because I think he was
killing two birds with one stone, and he has a lot more context
and experience than I.
However, just for the record, I want to make sure nobody
misinterprets my sci.logic post. Poster "Simon" who is firmly
entrenched in theoretical context (as is appropriate in
sci.logic) was having a tough time with Herc's real-world
"solution" which introduced probability into a three-valued
scheme, a nifty idea for us dumbo software builders, but
irrelevant in theoretical context. Someone should have advised
Simon. If Dolan didn't, I probably would have, though probably
just trying to kill the one bird.
So there are five distinctions about Dolan's flame compared to
the posters from AUK:
1. He has more experience in this subject than all the AUK
posters put together.
2. He had at least one useful purpose, probably more.
3. When his purpose was achieved, he stopped.
4. He is a regular poster in the above groups, so has context.
5. It was creative and entertaining because off-topic, because
he's not being paid for his trouble, because he can, because
he's a ham like me, etc. Anyway, it wasn't boring.
Larry
Kent Paul Dolan
> I realize its fun to "poke the monkey," but
> if you believe what you say...
> dont provoke him. Thats unkind.
Doesn't matter. In my ethics, being unsane,
as I also happen to be, isn't an excuse for
misbehavior. Herc richly earns every bit of
derision he receives.
xanthian.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Rob Duncan
"Kent Paul Dolan" <xant...@well.com> wrote in message
news:6e269b0aaeab0331358...@mygate.mailgate.org...
> "Rob Duncan" <robd...@gbronline.com> wrote:
>
> > I realize its fun to "poke the monkey," but
> > if you believe what you say...
> > dont provoke him. Thats unkind.
>
> Doesn't matter. In my ethics, being unsane,
> as I also happen to be, isn't an excuse for
> misbehavior. Herc richly earns every bit of
> derision he receives.
>
> xanthian.
Herc doesnt 'misbehave,' he behaves differently than you want him to. On
the net we all have the right to post whatever drivel pleases us. (sans a
bonefied threat of physical violence) Which I dont think he has done in
reality.
Rob
Kent Paul Dolan
> Herc doesnt 'misbehave,' he behaves differently
> than you want him to.
You and I have vastly different concepts of what
constitutes acceptable behavior in human society
(of which Usenet is a subset). Herc's behavior is
far outside the limits I (and apparently many
others) find appropriate.
> On the net we all have the right to post whatever
> drivel pleases us.
The concept of newsgroup charters seems to have
escaped your attention. We have no such rights.
Doing so evokes the "tragedy of the commons".
That claim that Usenet is without rules or
boundaries is the form of mental illness indulged by
David Hayes and his vandalous minions.
> (sans a bon[i]fied threat of physical violence)
> Which I dont think he has done in reality.
Someone also commenting on his behavior claims Herc
was in point of fact _arrested_ for threatening
violence, and Herc's "rebuttals" seem instead to
confirm that claim. I can't independently verify the
claim, I wasn't participating where and when it
happened.
Peter Olcott
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
The primary benefit of solving the Halting Problem was to
detect programs that failed to halt, thus were incorrect.
Pathological self-reference can also be viewed as a form
of error. If the Halting Problem is redefined (which does not
refute anyone), then this redefined problem can be easily
solved.
Now we have three possible correct results:
(a) Halts
(b) Does Not Halt
(c) Pathological Self Reference to Halt
Compared to my prior claims, this one seem trivial and
obvious. Possibly this claim adds a slight nuance to the
problem that has not been widely discussed before.
If we construe pathological self-reference as another
error condition, then this does remove the impossibility
of creating a useful tool.
Robert Low
Peter Olcott <olc...@worldnet.att.net> wrote:
>Now we have three possible correct results:
>(a) Halts
>(b) Does Not Halt
>(c) Pathological Self Reference to Halt
>
>Compared to my prior claims, this one seem trivial and
>obvious. Possibly this claim adds a slight nuance to the
>problem that has not been widely discussed before.
>If we construe pathological self-reference as another
>error condition, then this does remove the impossibility
>of creating a useful tool.
What *are* you gibbering about?
Casey Hawthorne
database (of TM states/symbols on the tape) of program patterns that
you have -- at some point there will be an input test program with
it's data that is not in your database - at this time you will have to
execute that input test program one step at a time -- so, if the input
test program does not halt then neither does the analyzing program
return with an answer.
--
Regards,
Casey
David C. Ullrich
<olc...@worldnet.att.net> wrote:
>The Liar Paradox can be shown to be nothing more than
>a incorrectly formed statement because of its pathological
>self-reference. The Halting Problem can only exist because
>of this same sort of pathological self-reference.
>
>The primary benefit of solving the Halting Problem was to
>detect programs that failed to halt, thus were incorrect.
>Pathological self-reference can also be viewed as a form
>of error. If the Halting Problem is redefined (which does not
>refute anyone), then this redefined problem can be easily
>solved.
>
>Now we have three possible correct results:
>(a) Halts
>(b) Does Not Halt
>(c) Pathological Self Reference to Halt
fascinating, a day or so of desperate attempts to sound
rational, followed by this...
ok, fine. if we allow those three answers then the problem
can easily be solved. so solve the modified problem, and
then tell me whether
def divides(a, b):
return (b%a)==0
def perfect(n):
s = 0
for d in range(1,n):
if divides(d,n):
s = s + d
return s==n
def findOddPerfect():
n = 3
while 1:
if perfect(n):
return n
n = n + 2
findOddPerfect()
halts, does not halt, or involves pathological
self-reference to Halt.
>Compared to my prior claims, this one seem trivial and
>obvious.
only to you. examples like the above make it clear to
everyone else that nobody has any idea how to do it.
so tell us the trivial and obvious solution.
>Possibly this claim adds a slight nuance to the
>problem that has not been widely discussed before.
'nuance' is not the right word. it's gibberish until
you give a precise definition of pathological
self-reference. but never mind that. -you- know what you
mean. tell us what the simple solution returns for the
15 lines of python above.
>If we construe pathological self-reference as another
>error condition, then this does remove the impossibility
>of creating a useful tool.
>
************************
David C. Ullrich
sorry about the inelegant formatting - typing
one-handed for a few weeks...
The Ghost In The Machine
<mtx...@linux.services.coventry.ac.uk>
wrote
on 5 Sep 2004 16:53:49 GMT
<chfgat$m62$2...@sunbeam.coventry.ac.uk>:
Somehow, I don't think a TM can determine whether it's
simulating a variant of itself; it's too stupid. :-) Even
an idealized von Neumann computer might have trouble, for
there are many methods of encoding the machine instructions
(as everyone in computer fields well knows; do we use an
x86, a 680x0, ARM, PPC, Alpha, s390, ...?)
And then there are the trivial permutations: SUB R0,R0
and XOR R0,R0 for MOV #0,R0, or LSH #1,R0 or MUL #2,R0
for ADD R0,R0. Or one can replace
MUL #10,R0
with a sequence
LSH #1,R0 ;R0 = A * 2
MOV R0,R1
LSH #2,R1 ;R1 = A * 8
ADD R1,R0 ;R0 = A * 10
Or one can do even sillier things, like implementing
multiplication using addition and shifting:
MUL R1,R0
might transmute into:
MOV #0,R2 ; accumulator
J+ R1,Start; if R1 is positive, skip adjustment
NEG R1 ; make R1 nonnegative
NEG R0 ; and flip R0 as well
Start:
J0 R1, End ; if no more bits, break out
RSH R1 ; get rightmost bit into C
JNC Skip ; no bit
ADD R0,R3 ; account for C
Skip:
LSH #1,R0 ; prep for next add
JMP Start
End:
MOV R2,R0 ; move accumulator into final result
If R1 or R2 is needed afterwards, of course, it can be saved
and restored using PUSH and POP -- assuming the machine
supports such.
So how does WillHalt() detect that it's running itself?
Especially since the emulated computer is in a completely
different address space from the emulat*ing* computer?
Of course, a routine might be able to detect whether
it's called itself by threading through the stack,
assuming that:
[1] the stack has sufficient information
(usually, a frame pointer) to allow reliable threading,
[2] nobody's corrupted the stack in the meantime,
[3] the routine knows when to stop looking.
Of course, not all programs are this well-behaved... :-)
--
#191, ewi...@earthlink.net
It's still legal to go .sigless.
news...@comcast.net
Sigh.... two steps forward, one step back....
Even if you could sensibly and unambiguously define what you mean by a
"pathological self reference to halt", it wouldn't do you any good.
There's no program that can "solve the halting problem" by simply
trying to eliminate these self-referencial cases -- you still couldn't
give the correct halts/doesn't-halt answer in all the other cases.
But I'm not getting into this again. Read those books you ordered and
learn what you can.
--
That's News To Me!
news...@comcast.net
Simon G Best
defied kookery and been "cured of CrackPottery" (or, at least, that you
were taking steps in the right direction). It seemed a reasonable thing
for me to do, after having cross-posted to alt.usenet.kooks to document
your kookery there.
But now there's this:
Peter Olcott wrote:
> The Liar Paradox can be shown to be nothing more than
> a incorrectly formed statement because of its pathological
> self-reference.
Define "reference".
> The Halting Problem can only exist because
> of this same sort of pathological self-reference.
Define "reference" appropriately for Turing Machines.
> The primary benefit of solving the Halting Problem was to
> detect programs that failed to halt, thus were incorrect.
> Pathological self-reference can also be viewed as a form
> of error. If the Halting Problem is redefined (which does not
> refute anyone), then this redefined problem can be easily
> solved.
"If the Halting Problem is redefined"? It's just a different problem,
*not* a redefinition of the Halting Problem.
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
We can split this problem into two problems. The first is the
"Pathological Self Reference" problem; the second is the halting problem
for Turing Machines and inputs that are found not to have the property
of "Pathological Self Reference to Halt".
A general solution to your problem can be used as the basis for a
general solution to the "Pathological Self Reference" problem. So, we
can start by looking at just the "Pathological Self Reference" problem.
If we find that there is no general solution to it, we will have found
that there is no general solution to your problem. If, instead, we do
find a general solution to the "Pathological Self Reference" problem, we
can then move on to the halting problem for Turing Machines that do not
have the property of "Pathological Self Reference to Halt".
However, you still need to define "Reference" in terms of Turing Machines.
> Compared to my prior claims, this one seem trivial and
> obvious.
To you, maybe, but not to most of us. The key word is "seem". You
should have discovered by now (as you just have with the Halting
Problem) that how things "seem" is not necessarily how they actually are.
> Possibly this claim adds a slight nuance to the
> problem that has not been widely discussed before.
Define "nuance".
> If we construe pathological self-reference as another
> error condition, then this does remove the impossibility
> of creating a useful tool.
No. Construing "pathological self-reference as another error condition"
*does not* "remove the impossibility of creating a useful tool." In
exactly the same way, construing non-haltingness "as another error
condition" *did not* "remove the impossibility of creating a useful tool."
Hmmm, it does seem that your admission that the Halting Problem is
unsolvable (by Turing Machines) was too good to be true after all :-(
Simon
Peter Olcott
<news...@comcast.net> wrote in message news:ybK_c.298530$eM2.241548@attbi_s51...
I am not talking about solving the halting problem.
There are three possible cases for the Halt Analyzer
to report:
(1) Halts
(2) Does Not Halt
(3) I Don't Know
Simply treat "I Don't Know" as another form of error,
as if it was "Does Not Halt". Although there could be
some cases where "I Don't Know" is not an error,
all the cases where "Halts" is reported can be correct.
Will Twentyman
The only programs that we can guarantee to halt or not halt are the ones
that correspond to primitive recursive functions. Any TM that
corresponds to a partial recursive function (ie, has a WHILE loop) has
no known guaranteed method for determining if it halts or not.
Pathological self reference to halt is not the only way to be
unanalyzable, just the easiest to construct.
--
Will Twentyman
email: wtwentyman at copper dot net
Tim Peters
> The Liar Paradox can be shown to be nothing more than
> a incorrectly formed statement because of its pathological
> self-reference.
I think that's true.
> The Halting Problem can only exist because of this same sort of
> pathological self-reference.
But that part is simply wrong. There are many proofs of the insolvability
of the halting problem, in many formal contexts. You've labored for a long
time over a specific kind of proof, in which it's easy to confuse the formal
construction with "pathological self-reference" (although this *is* a
confusion -- you don't "get it" wrt that part yet -- resemblance to the Liar
Paradox here is superficial, not deep). But there are other proofs in which
you'd have to work very hard to fall into that confusion.
Read the books you ordered, and maybe one will spell out other proofs. In
recent times, Chaitin gave what I think is a particularly informative proof,
showing the impossibility of solving the halting problem as a consequence
*of* the impossibility of an effective procedure for determining whether an
arbitrary program P is the *smallest* program that produces the same output
as P. He proved that there are only finitely many programs P for which we
can prove that P is the smallest program producing P's output. The proof of
that contains no steps that "look like" self-reference. The impossiblity of
solving the halting problem follows from it.
If you persist, you'll eventually discover that, in a real sense (which can
be made formal), there's no non-trivial property of program behavior that's
effectively decidable. "Does it halt?" is just one of them.
> ...
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
>
> Compared to my prior claims, this one seem trivial and
> obvious. Possibly this claim adds a slight nuance to the
> problem that has not been widely discussed before.
It doesn't help, because-- still contrary to your slightly better current
intuition --the impossibility of solving the halting problem isn't due to
self-reference. It's deeper than just that.
> If we construe pathological self-reference as another
> error condition, then this does remove the impossibility
> of creating a useful tool.
That's a different question entirely. To be *useful*, a tool doesn't have
to solve the halting problem. Which is a good thing, because no tool can.
*Useful* tools in this area include gimmicks as simple as a compiler
spitting out a warning message if a conditional expression (one used to
affect flow control) evaluates to a constant; e.g., complaining about
while ((unsigned int)i >= 0) { ... }
in C. The rules of the language guarantee the expression always evaluates
to true, so it's good to point out silliness like that. It can catch some
infinite loops in this way. It can also complain about correct programs
(e.g., perhaps the body of the loop contains a call to function that in turn
calls exit()). A useful tool doesn't have to be perfect.
Michael Mueller
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
This is completely irrelevant.
There are many other proves to show that there
is no algorithmic solution to the halting problem.
There are many other problems which also cannot
be solved by an algorithm.
And there must be problems which cannot be solved
by an algorithm because there are much more problems
than algorithms.
And finally:
To show that a problem can be solved by an algorithm,
you have to write down that algorithm
- this is the only acceptable way to do.
To discuss that one of the many proves is
possibly wrong, leads you nowhere.
Michael Mueller
Abdulaziz Ghuloum
> I am not talking about solving the halting problem.
What are you talking about then?
> There are three possible cases for the Halt Analyzer
> to report:
> (1) Halts
> (2) Does Not Halt
> (3) I Don't Know
>
> Simply treat "I Don't Know" as another form of error,
> as if it was "Does Not Halt". Although there could be
> some cases where "I Don't Know" is not an error,
> all the cases where "Halts" is reported can be correct.
Hmmm. So, is the following code a valid Halt Analyzer function:
HaltResult Analyze(Program code){
return I_DONT_KNOW; // always reporting case (3) above
}
To me, it seems perfectly valid (according to your definition) and
completely useless.
G. Frege
<aghu...@c-s-remove-dashes.indiana.edu> wrote:
> >
> > There are three possible cases for the Halt Analyzer
> > to report:
> >
> > (1) Halts
> > (2) Does Not Halt
> > (3) I Don't Know
> >
> > [...]
> >
> Hmmm. So, is the following code a valid Halt Analyzer function:
>
> HaltResult Analyze(Program code){
> return I_DONT_KNOW; // always reporting case (3) above
> }
>
Sure.
>
> To me, it seems perfectly valid (according to your definition) and
> completely useless.
>
Right. But that's not *necessarily* the case, there m a y be Halt
Analyzers which a r e useful.
For example, it should be possible to write a Halt Analyzer (for the
language C) which is able to determine "Does Not Halt" if it encounters
(for example) the code
:
while 1;
:
F.
G. Frege
>
> For example, it should be possible to write a Halt Analyzer (for the
> language C) which is able to determine "Does Not Halt" if it encounters
> (for example) the code
>
> :
> while (1); <--- corrected
> :
>
Ah, right, it's C. :-)
F.
Kent Paul Dolan
[Oh, joy, here we go for another 3500-odd postings
of Olcott drivel.]
Peter, in the movie _The Princess Bride_, the Six
Fingered Man, one of the villains, says to Inigo
Montoya, one of the heros, "Oh, dear. Are you still
trying to win?". Montoya pulls the dagger out of his
gut and proceeds to out-duel and slaughter the Six
Fingered Man, as an answer in the affirmative.
That is a fantasy, this is real life; you are not
Inigo Montoya, your arguments are all stabbed
through the gut, firmly and forever dead, yet you
are still trying to "win". It will never happen.
This attempt is ill-advised, as I will go on to
demonstrate [since you continue to insist on making
enough of a fool of yourself that even a lightweight
like me can point out your errors].
> The Liar Paradox can be shown to be nothing more
> than a incorrectly formed statement because of its
> pathological self-reference.
This is a falsehood. The liar paradox is simply a
tool to show that in two valued logic systems,
statements can be constructed which cannot be
evaluated to either logic value. There is nothing
the least bit "pathological" about it. That is a
value judgement arising from your false world
concept that faith can replace logic.
> The Halting Problem can only exist because of this
> same sort of pathological self-reference.
That is a falsehood, as I will go on to demonstrate.
> The primary benefit of solving the Halting Problem
> was to detect programs that failed to halt,
The primary benefit of a universal Halting Problem
solver, had it been possible to construct one, which
it was not, would have been a way to find out by
a finite-duration analysis that a program would not
halt, rather than finding out by running it for
infinite time to discover the same information, an
impractical alternative.
> thus were incorrect.
That is a falsehood. There is nothing "incorrect"
about programs that fail to halt. They fail to be
useful, but that doesn't mean that they fail to be
correct. "Write an endless loop" is a common
beginning computer programming assignment, and that
specification results in a correct program which
does not halt.
> Pathological self-reference can also be viewed as
> a form of error.
That is a falsehood, unless, of course, one is
palpably insane, as you are.
> If the Halting Problem is redefined
You can redefine it to be an exercise with tinker
toys, if you want, but that doesn't make your
redefinition the least bit useful or intellectually
important.
> (which does not refute anyone),
That is a meaningless noise.
> then this redefined problem can be easily solved.
That is nonsense. The writing of a universal Halting
Problem analyzer is beyond the capacity of
humankind, not in the least because it is impossible.
The "solving" of an Olcott "I wish I could tell you
if this program would halt" analyzer may be as
simple as "always answer no, and take your lumps on
the minority that do halt", but to be useful would
require at least the equivalent effort of all the
PhD theses that have gone into creating analyzers
that solve the Halting Problem for some tiny subset
of all possible Turing machine programs and
associated input data. That doesn't satisfy any
normal person's definition of "easily solved".
No one is interested in the creation of a less than
universal Halting Problem solver, since it is
guaranteed to _fail_ almost universally, an easy
proof left as an exercise for the reader.
> Now we have three possible correct results:
> (a) Halts
> (b) Does Not Halt
> (c) Pathological Self Reference to Halt
No, you don't. Quick proof:
If it is possible to write one halting analyzer,
it is possible to write another that produces
exactly the same results, but shares no common code.
[Subproof: For example, this is done in computer
practice every day; it is called "reverse
engineering". For another example, the manned
space missions use independently developed code
sets run in parallel to control launch, so that
failures in one code do not occur in the other
code, More to the point, there isn't any (known)
computer algorithm that cannot be rewritten
completely to produce the same results, so any
purported universal Halting Problem analyzer A
can be patched algorithm by algorithm to produce
a completely unrelated new purported universal
Halting Problem analyzer B.]
Now feed one purported halting analyzer, plus
disproof wrapper, to the other one, and vice versa.
Both will be unable to produce an answer, yet in
neither case will it be because there was some
"pathological" (semantic freight due to your baby
bedtime boogie-men) Self-Reference to Halt, neither
case would involve self-reference.
This still constitutes a proof that producing the
first one is a contradiction in logic.
> Compared to my prior claims, this one seem trivial
> and obvious.
You are continuing to make "claims", despite having
contended just a few postings ago that your
invincible ignorance was "cured, neener, neener".
What does this tell us about your veracity?
What does this tell us about your mental health
status?
Your claims seem "trivial and obvious" to you only
because you fail to invest an erg of intelligent
thought in checking their correctness or even
reasonableness, perferring to waste the time of
others to point out the stupidity you are employing.
> Possibly this claim adds a slight nuance to the
> problem that has not been widely discussed before.
This is a falsehood. 3552 postings refuting exactly
this drivel from you, I contend, constitutes "widely
discussed"; painfully so.
There is no "slight nuance" involved; you are still
spouting utter counterfactual nonsense, easily
demonstrated to any informed participant, a set of
which you unfortunately fail to be a member.
> If we construe pathological self-reference as
> another error condition, then this does remove the
> impossibility of creating a useful tool.
This is a falsehood, and a demonstration that your
invincible ignorance is still in full flower, as
demonstrated above.
xanthian, dueling on sheerly for the love of
swordplay, not for any hope of curing even one
victim of his "invincible ignorance".
Bryan Olson
> I am not talking about solving the halting problem.
> There are three possible cases for the Halt Analyzer
> to report:
> (1) Halts
> (2) Does Not Halt
> (3) I Don't Know
>
> Simply treat "I Don't Know" as another form of error,
> as if it was "Does Not Halt". Although there could be
> some cases where "I Don't Know" is not an error,
> all the cases where "Halts" is reported can be correct.
We've been over this long ago. We can build a Turing machine
that, when it answers, is always correct, and always answers
'halts' on instances that do in fact halt. Unfortunately, for
some instances, our machine itself does not halt.
If your machine always answers, possibly with "I don't know",
then it can no longer answer correctly for all halting
instances. Equivalently, for any Turing machine that accepts
Halts, there is some input for which that machine does not halt.
--
--Bryan
Abdulaziz Ghuloum
Just because there is a while(1); in the program does not mean that it
"does not halt". Sure, main(){while(1);} does not halt, but analyzing
trivial cases hardly qualifies as useful. The problem of whether the
execution path of the program will reach the while(1); statement is
undecidable (unless Peter wants to "prove" otherwise) and there are many
forms of infinite loops other than while(1);.
I don't buy that a halt analyzer that is permitted to return "I don't
know" is useful.
Aziz,,,
G. Frege
<aghu...@c-s-remove-dashes.indiana.edu> wrote:
>
> Sure, main(){while(1);} does not halt, but analyzing
> trivial cases hardly qualifies as useful.
>
But that "shows" that halt analysis (in the restricted Olcott sense) is
possible in principle.
>
> ...there are many forms of infinite loops other than while(1);.
>
Right. Hence a "useful" halt analyzer has to be able to "see" at least
SOME of them. (The more the better.)
Well, "useful" isn't that well defined, but I would consider a tool
useful which catches some "trivial" errors one might introduce as a
programmer (not being aware of them).
But I concede that these things m i g h t only be of a theoretical
interest.
>
> I don't buy that a halt analyzer that is permitted to return "I don't
> know" is useful.
>
Certainly much better than just looping forever (in that cases), won't
you think so?
F.
Abdulaziz Ghuloum
For me, the usefulness of this halt anayzer diminishes exponentially
with every time it answers "I don't know". How many times are you going
to accept "I don't know" for an answer before deciding on the silliness
of the ides.
Marc Goodman
> For me, the usefulness of this halt anayzer diminishes exponentially
> with every time it answers "I don't know". How many times are you going
> to accept "I don't know" for an answer before deciding on the silliness
> of the ides.
I have a code base that uses OLE automation to drive MS Word, Excel,
Powerpoint, Access, Outlook, Lotus Notes, and some other apps.
It would be _very_helpful_ to me if I had some way of telling whether
these programs were infinite looping or _just_taking_a_REALLY_long_time.
I'd be pretty happy, even if it didn't work for, say, LoopIfHalts.
So, in the real world, I'd be willing to take "I don't know" for an
answer sometimes.
--
I have found that the supernatural power of faith can overcome
great obstacles: Apparently analytical truth is not one of them.
- Peter Olcott on comp.theory
Pete Olcott
http://LiarParadox.org/Provability_with_Minimal_Type_Theory.pdf
--
(Γ ⊨ _FS A) ≡ (Γ ⊢ _FS A)
Peter Percival
> On 9/5/2004 11:21 AM, Peter Olcott wrote:
>> The Liar Paradox can be shown to be nothing more than a incorrectly
>> formed statement because of its pathological self-reference. The
>> Halting Problem can only exist because of this same sort of
>> pathological self-reference.
>>
>> The primary benefit of solving the Halting Problem was to detect
>> programs that failed to halt, thus were incorrect. Pathological
>> self-reference can also be viewed as a form of error. If the
>> Halting Problem is redefined (which does not refute anyone), then
>> this redefined problem can be easily solved.
>>
>> Now we have three possible correct results: (a) Halts (b) Does Not
>> Halt (c) Pathological Self Reference to Halt
>>
>> Compared to my prior claims, this one seem trivial and obvious.
>> Possibly this claim adds a slight nuance to the problem that has
>> not been widely discussed before. If we construe pathological
>> self-reference as another error condition, then this does remove
>> the impossibility of creating a useful tool.
>>
>>
>
> Now (thirteen years later) I have created a branch of mathematics
and indeed unable, to answer any questions about MTT.
> called [Minimal Type Theory] (MTT) to formalize the notion of
> {Pathological Self Reference}.
>
> http://LiarParadox.org/Provability_with_Minimal_Type_Theory.pdf
>
--
to me what you really mean.
I think I had better not, Duchess. Nowadays to be intelligible is
to be found out. -- Oscar Wilde, Lady Windermere's Fan
Kaz Kylheku
> Now (thirteen years later) I have created a branch of mathematics
> called [Minimal Type Theory] (MTT) to formalize the notion of
> {Pathological Self Reference}.
>
> http://LiarParadox.org/Provability_with_Minimal_Type_Theory.pdf
trisecting angles with a straightedge and compass.
Pete Olcott
My single-minded focus is to provide the mathematical foundation for the above system.
Once the Cyc Project has a complete mathematical foundation reverse-engineering the design of the automated process to complete the population of the Cyc knowledge ontology will be possible.
The foundations of this design are:
(1) The mathematics of sub atomic semantic compositionality. (Exactly and precisely how do all of the tiniest pieces of meaning fit together?).
(2) Minimal bootstrap knowledge ontology. (The minimum meta-knowledge (knowledge about knowledge) required as the initial basis).
We need to find the definition of the absolute minimum bootstrap knowledge ontology because the criterion measure derived for this absolute minimum will provide deep insight into the design of the process:
It will provide a list of the types of elements required and exactly how these elements fit together, basically a further elaboration of sub atomic semantic compositionality.
olcott
mall Omaha NE.
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
It turns out that inputs having pathological self-reference can be
decided to be non-halting. The invocation of a halt decider that is
based on simulating the execution of its input can be decided to be
infinitely recursive in the above case.
Within the x86 based execution trace of the above user code:
H_Hat() calls the same function from the same machine address with the
same inputs a second time with no other control flow instructions
inbetween.
The above program meets the criteria of a program with infinite
execution: Any program that would not halt unless its simulation was
stopped is a program with the property of infinite execution.
--
Copyright 2004 and 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Richard Damon
The definition of infinite execution is that it continues to execute
forever.
The fact that a Halt Decider based on simulation has to stop the
execution to meet its requirement to answer is NOT proof of infinite
execution of the program that called that Halt Decider. In fact a call
to a Halt decider can be shown by definition (a semantic tautology) to
be non-halting as long as the decider succeeds at being a decider. Thus
by inspection, H_Hat can be seen to be halting as long as Halts is a
decider that decides it is non-halting.
The actual fact of the matter is that Halts, as you have defined it, is
unable to properly decide on self-referential machines, which puts the
flaw in the halt decider. At each cycle in the recursion, there IS a
conditional controlled by Halts, so there is NOT an unconditional
recursion that forces infinite execution.
If you want to come up with a different statement of the halting
problem, on that uses a criteria other than does the actual machine come
to an eventual halt, feel free, just realize that different question
means different problem.