Re: What is the Result from Invoking this Halt Function?

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 08/24/04 

Date: Tue, 24 Aug 2004 05:14:55 -0500

On Tue, 24 Aug 2004 03:19:24 GMT, "Peter Olcott"
<olcott@worldnet.att.net> wrote:

>
>"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message news:gl9ei0l0j7ibjp3aq88pbsu1qjk6r3cn0f@4ax.com...
>> On Sat, 21 Aug 2004 03:11:41 GMT, "Peter Olcott"
>> <olcott@worldnet.att.net> wrote:
>>
>> >
>> >"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message news:2imbi0p20o42ubh20bosrciekr2sver8ha@4ax.com...
>> >> On Fri, 20 Aug 2004 02:30:41 GMT, "Peter Olcott"
>> >> <olcott@worldnet.att.net> wrote:
>> >
>> >> >> > uh, right. i'll let somone who knows C decide whether this
>> >> >> > works [the fact that there's only a single loop makes me
>> >> >> > doubt it...] the point was to make it as simple to
>> >> >> > understand as possible.
>> >> >>
>> >> >> It's not quite right but it's close.
>> >> >>
>> >> >> int main() { int i,j,k; for(i=j=k=1;--j||k;k=j?i%j?k:k-j:(j=i+=2)); return 0; }
>> >> >>
>> >> >> The main problem with C is that 'int' is a fixed precision, which
>> >> >> means it may not solve the desired problem that it's coded for.
>> >> >> However, the question is still a mildly interesting one;
>> >> >> all I've done is reframed it properly, and now I can compile it. :-)
>> >> >>
>> >> >> >
>> >> >> > does it halt or not?
>> >> >
>> >> >This one would not halt.
>> >>
>> >> ah. how do you -know-? [hint: -proving- it doesn't halt gives
>> >> a solution to a very old problem that nobody knows how to solve.
>> >
>> >I know that it does not halt in this case, and the answer is very
>> >easy. I will let you think about it for awhile, and answer on your
>> >next reply, if you haven't yet figured it out by then.
>>
>> i haven't figured it out. just like no other mathematician since
>> euclid has figured it out. so give us the easy answer already.
>
>Someone else already guessed it the next day. Did you notice that
>C uses fixed length integers? I am sure that it is already known that
>it will not halt up to the limit of the fixed length integer. As soon as
>it gets there is begins to loop through the same sequences all over
>again.

well duh. if we're talking about actual C on a physical machine then
-every- program halts for similar reasons. -hence- when someone asks
whether a routine halts in a context like the present the question
is about an abstract routine, using arbitrary-size integers on a
machine with infifitely much memory.

>> >> so you should really explain how you know it doesn't halt, lest
>> >> people assume that you're just guessing. note that since a
>> >> correct answer is going to make you famous, nobody is going to
>> >> believe any weaseling about how you'd just rather not say...]
>> >
>>
>>
>> ************************
>>
>> David C. Ullrich
>>
>> sorry about the inelegant formatting - typing
>> one-handed for a few weeks...
>

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

Relevant Pages