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

From: Owen Jacobson (angstrom_at_lionsanctuary.net)
Date: 08/21/04 

Date: Sat, 21 Aug 2004 04:18:44 GMT

On Sat, 21 Aug 2004 03:11:41 +0000, Peter Olcott 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:
>>
>> > (Lost attribution)
>> >
>> >> 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. :-)
>> >
>> > 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.

Does it halt if i, j, and k are, instead of fixed-size ints (for which we
can simply exhaustivly test all values for any give size of an int), some
suitable bignum type that can represent arbitrarily-large numbers at the
expense of increasing memory usage? 

-- 
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.

Relevant Pages