revisit halting problem
- From: mainargv@xxxxxxxxx
- Date: 26 Feb 2007 03:38:11 -0800
hi
I just looked at several halting problem proofs, and it seems there is
a little ambiguity.
bool would_it_stop( char * program, char * input ) {
if( something terribly clever ) {
return TRUE;
} else {
return FALSE;
}
}
There is an implicit assumption here: "would_it_stop stops in (say) n
seconds" or some "waitable" seconds
bool try_this( char * program ) {int i;
if( try_this( program, program ) ) {
while( 1 ) {i++;}
} else {
return TRUE;
}
}
try_this(try_this,try_this) and wait 2n seconds.
now the rest of argument only proves that either would_it_stop is
impossible or buggers, OR it it didn't meet time constraints (ie, the
program didn't stop in time.)
Now the question: what if would_it_stop is possible, but its running
time is simply not known. (there are two cases here: not known but
finite, or not known but infinite.) and that's say we are only
interested in "not known but finite". In this case, the usual way of
proving halting problem is not going to work. thanks for any input.
.
- Follow-Ups:
- Re: revisit halting problem
- From: mainargv
- Re: revisit halting problem
- Prev by Date: Re: Do Write Once TM's Halt?
- Next by Date: Re: revisit halting problem
- Previous by thread: An efficient way of sequencing streams of integers
- Next by thread: Re: revisit halting problem
- Index(es):