"Strong typing vs. strong testing"

[Pascal J. Bourguignon]

RG <rNOSPAMon at flownet.com> writes:
>> The main example of a sensible program that can't be written in a
>> non-complete language is an interpreter for a Turing-complete language.
>> But presumably a high-assurance application should never contain such a
>> thing, since the interpreted programs themselves then wouldn't have
>> static assurance.
>
> There are only two possibilities: either you have a finite-state 
> machine, or you have a Turning machine.  (Well, OK, you could have a 
> pushdown automaton, but there are no programming languages that model a 
> PDA.  Well, OK, there's Forth, but AFAIK there are no static type 
> checkers for Forth.  Besides, who uses Forth? ;-)
>
> If you have a finite state machine everything is trivial.  If you have a 
> Turing machine everything is generally impossible.  This is an 
> oversimplification but not far from the fundamental underlying truth.


All our computers are FSA: they don't have infinite memory.

Even if we developed a robot able to crunch stellar matter and use it
as memory, it would still NOT be a Turing Machine, since the universe is
finite, has finite matter and energy.  

Therefore it's trivial.  (Indeed, the answer is 42).



Now the problem is rather our minds.  We use the notion of mathematical
infinite, and of Turing Machines vs. DFA, because beyond a certain size,
a DFA is not manageable any more by our little minds, and also,
computationnaly.  While it's finite, computing its most of its
properties will require more time than the universe (which is also
limited in time).   So we need another conceptualization to reduce the
complexity of big DFAs.  Turing Machines are much simplier, they just
slip the complexity under the infinite tape (which conceptually is
rather simple, as long as you don't try to reach the end of the tape, or
you don't try to use it to weave an infinite rug...



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/