Re: revisit halting problem

On Feb 26, 3:38 am, maina...@xxxxxxxxx wrote:
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 ) ) {

sorry that should be "if( would_it_stop( 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.


.