Re: functions that halt

From: |-|erc (contactvia_at_wwwadamskingdom.com)
Date: 04/06/04 

Date: Tue, 6 Apr 2004 09:36:19 +1000

"Will Twentyman" <wtwentyman@read.my.sig> > >>
> >>>There was a post in sci.math last year about the class of functions
> >>>that are constructed upwards and are guaranteed to halt.
> >>>
> >>>How powerful would they be?
> >>>
> >>>There was no formal answer but the consensus was they would be trivial
> >>>functions.
> >>>
> >>>Is this necessarily true?
> >>>
> >>>The halting proof started out as a system to check for errors in programs.
> >>>
> >>>We assume that 'programs' either halt or they don't (good assumption given
> >>>our practices).
> >>>
> >>>From that definition, no program can determine if a general function halts or not.
> >>>
> >>>But what if we assume all programs halt? This doesn't contradict the halting proof,
> >>>merely denies its construction since it depends on an infinite loop being programmed.
> >>
> >>It is trivial to construct a program that does not halt. There are
> >>plenty of times when a loop is constructed for which it is far from
> >>obvious if it will halt. The loop may even be infinite for some input
> >>and finite for other input.
> >>
> >>"What if we assume all programs halt?" We can then prove anything,
> >>since it is not true.
> >>
> >
> > What function can your program with an infinite loop calculate that a
> > special class of programs without infinite loops not calculate?
>
> It's not a matter of having an infinite loop, it's a matter of having a
> *potentially* infinite loop. It is very easy to construct problems that
> are O(e^n) or larger because of recursive function calls, and these
> occur in everyday life. Add to it the possibility of not knowing if it
> halts, or even when you can be sure it won't halt, and you have problems.
>
> My point is simple: you cannot assume all function halt. I'm not saying
> anything about whether they are practical, or if we'd have the patience
> to wait around and find out. I'm saying some functions do not halt, and
> speculating about all functions halting is not helpful.
>
> Your question strikes me as being as profound as asking, "What if the
> sky were green with purple polka dots? Wouldn't that mess with
> microwave transmissions?" You can ask it, explore it, but in the end,
> you do not make progress towards understanding how things actually work.
>

thats conjecture. noone in industry what so ever writes programs that don't halt.
why are mathematicians allowed this freedom?

Herc

Relevant Pages

  • Re: Should compilers elide errors when possible?
    ... Well, with an obvious definition, SLEEP has "no side effects". ... I'd be pretty unhappy if the compiler elided that call to SLEEP. ... it should replace it with (error "infinite loop detected"). ... The only piece of code in a system which has a right to halt by means ...
    (comp.lang.lisp)
  • Re: functions that halt
    ... >>It's not a matter of having an infinite loop, it's a matter of having a ... >>halts, or even when you can be sure it won't halt, and you have problems. ... then locks the room, will Word halt? ...
    (comp.theory)
  • Re: Implausibility continued (in C)
    ... It's all math, Glenn. ... We are predicting what the computer will do when we step though the ... sufficiently large number and seeing if the program is in the halt state. ... still running must be in an infinite loop. ...
    (talk.origins)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... program B as input and goes into an infinite loop if B exits, ... then the next copy of program A must infinite loop. ... for the above proof that _all_ programs A halt on input B ... Youre counterproof does not refute this, ...
    (sci.math)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... program B as input and goes into an infinite loop if B exits, ... then the next copy of program A must infinite loop. ... for the above proof that _all_ programs A halt on input B ... Youre counterproof does not refute this, ...
    (comp.theory)