Re: functions that halt

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

Date: Sat, 10 Apr 2004 09:59:27 +1000

"Stephan Schulz" <schulz@sunbroy2.informatik.tu-muenchen.de> wrote :
> >
> >
> > thats conjecture. noone in industry what so ever writes programs
> > that don't halt.
> > why are mathematicians allowed this freedom?
>
> Well, if you are very finicky, all our computers are just finite
> automata, and the Halting Problem is decidable. Even in that case:

wrong

>
> Counterexample 1: Any UNIX d(a)emon.
>
> If you allow for the usual abstraction (unlimited resources), you get
> better counterexamples:

the other example was Microsoft Word where someone doesn't type Exit.

For interactive dogma we can just define the program as having gone into
cycles of temporal productive operation. Daemons are halted all the time
it doesn't mean they never computed anything because they didn't finish.

The busy wait state is the finish state, and activation from that state is multiple
runs of the program.

>
> Counterexample 2: Any program that tries to find special solutions to
> generally undecidable programs, e.g. theorem provers for first or
> higher-order logic (plug: check www.eprover.org) or model finders.
>

In practice they have a stop button and halt.

> Note that there is no (computable) syntactic characterisation for the
> class of all programs that always halt (simple diagonalisation
> proof).
>

none known, diag. relies on the definition of programs halting or not, so
that's wrong.

> Bye,
>
> Stephan
>
> --

don't come back
Herc
> -------------------------- It can be done! ---------------------------------

Quantcast