🚀 go-pugleaf

yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

>In article <R73812w164w@mantis.co.uk> mathew@mantis.co.uk (mathew) writes:
>>rockwell@socrates.umd.edu (Raul Rockwell) writes:
>>> David Gudeman  []
>>> [] Strong typing: the feature that an operation cannot return an
>>> [] undefined result because it did not know the typing of one of its
>>> [] operands.
>>> 
>>> Strong typing also means that the function will terminate.
>>
>>I beg your pardon?!
>>
>>Last I heard, the Halting Problem was still insoluble.
>>
>>Is there some new theoretical result you'd like to share with us?

>The halting problem does not really apply to actual programming languages
>(i.e. those that are compiled or interpreted into machine code).
>The sooner computer scientists begin to understand the actual meaning
>of the undecidability and complexity results, the better off the filed
>will be.

Trivially, this is true.  We can always run the program on the machine
and look for a cycle in the total state (all memory, all register, all
etc.)  Then we wait for on the order of 

	2 ^ ( 2 ^ wordsize * ( memorysize + registercount ) ) 

cycles (corrected for any non-binarity of the machine) and if we don't
get a repeat, the program never halts.  The approximate length of time
for my workstation (2^23 8-bit bytes, and arbitrary count of 8
registers, the number really doesn't matter), if it didn't have any
disk, and assuming 2^24 operations/sec, is 2^8388584 seconds ~=
2^8388559 years, or something like 10^2,800,000 years.  Net bandwidth
considerations demand exponential notation for numbers of this size.
Any even near-reasonable postulated speed increase will have no
noticible effect on this number (it will still exceed the lifetime of
the universe by an unreasonable factor).

I would say that this is close enough to insoluble for government
work, as the saying goes.  Am I missing something in your post?  I'd
love for the field to be better off . . . .

	Mike Beede




-- 
Mike Beede         SCTC
beede@sctc.com     1210 W. County Rd E, Suite 100           
			Arden Hills, MN  55112
                         (612) 482-7420