functions that halt
From: |-|erc (contactvia_at_wwwadamskingdom.com)
Date: 04/02/04
- Previous message: Alex Simpson: "CFP: LICS 2004: Call for Short Presentations"
- Next in thread: Will Twentyman: "Re: functions that halt"
- Reply: Will Twentyman: "Re: functions that halt"
- Reply: Patrick Powers: "Re: functions that halt"
- Maybe reply: The Ghost In The Machine: "Re: functions that halt"
- Maybe reply: Barb Knox: "Re: functions that halt"
- Maybe reply: |-|erc: "Re: functions that halt"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 2 Apr 2004 10:55:19 +1000
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.
Herc
--
\ oo
\____|\mn
/ /_/ /\ \_\
/ K-9/ \/_/ - www.YeOldeCoffeeShoppe.com -
/____/_____\
--------------
- Previous message: Alex Simpson: "CFP: LICS 2004: Call for Short Presentations"
- Next in thread: Will Twentyman: "Re: functions that halt"
- Reply: Will Twentyman: "Re: functions that halt"
- Reply: Patrick Powers: "Re: functions that halt"
- Maybe reply: The Ghost In The Machine: "Re: functions that halt"
- Maybe reply: Barb Knox: "Re: functions that halt"
- Maybe reply: |-|erc: "Re: functions that halt"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
