🚀 go-pugleaf

In article <STEPHEN.91May9022258@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes:

>Let me try one more time. PRACTICAL computers are FSMs and not fully
>general turing machines because PRACTICAL computers are finite. The
>fact that PRACTICAL computers are finite is an important THEORETICAL
>property of PRACTICAL computers and may need to be addressed before
>certain ideas are dismissed. And this is true even if you include all
>the input they're ever going to get as state space.

PRACTICAL computers may be FSM's but programming languages are not.  Nowhere
in the ANSI C standard does it give a maximum amount of memory that a C
program can run in.  Thus your program checker must assume that the program
that it is analyzing will never run out of tape, which means that the analyzer
must assume that the program will run on a Turing Machine, and the 
undecidability theorem applies.

>
>...I feel a bit like you're telling me that it's impossible to code a
>correct sort, because you never know when your input is going to be
>an infinite stream and the function just might not terminate....

Of course some simple argorithms may be proven, like a sorting algorithm,
but not >ALL<
-- 
David Gottner
davgot@auto-trol.COM                           Auto-trol Technology Corporation
{...}ncar!ico!auto-trol!younam                 12500 North Washington Street
(303) 252-2321                                 Denver, CO 80241-2404