Version 0 of mathematical foundation of computers and programs

Updated 2003-04-08 14:27:27

'page by' Theo Verelst

Of course, I run the risc of doing a phd in ee somehow with this stuff, which I was near to doing in maybe a few other areas and don't think is realy necessary, but I think this page will be compact and relevant enough. As always comment and add (in seperate enuogh way) at will, as is rule in these wikis.

Mainly, the mathematical concept or model which underlies most (though strictly speaking not all) of modern computers is the von Neumann machine architecture. Such an architecture of logical components is based on or can (again, mostly) be based on the finit state machine model, which can be mathematically modelled as a turing machine case. That machine should be on a page, but the exact definition I'd need to think about a bit or look up to define a bit decently.

The idea is that such a machine has inputs and outputs and memory, and that one can predict any output sequence by knowing the input sequence and the initial memory state. Which is important for predictability or importantly more to put the machine to work: verifiability. Which starts by allowing that one in general even can define all possible input sequences and memory states, and define that each one of them has exactly one well defined output sequence of the machine as a result.

Practically this model is narrowed down of course by defining the machine behaviour in a general way which leaves us options to define the result of human understanding input sequences and memory states, and their humanly speaking hopefully logical outcome.

A Finite State Machine is a model which makes a turing machine effectively and simply seperates the memory and the logic or machinery or function which determines the new state of the memory from the old one, together with the current input. And another function to determine the ouput pattern from the input and the state.

As logic designers know or should be aware of, most digital machines are defined or definable as a finite state machine somehow or literally. The existence of a BIST connection to modern pentium chips is good proof of this: such input/output allows a digital tester to enter a (almost complete) state into the pentiums' internal memory cells, apply one (or more) finite state progression steps (clock cycles), and read out the resulting state (serially).

Apart from such unpredictable events as communication bus conflicts, the whole unrolling of events which happens in a PC or workstation is exactly defined by the combination of all system and user programs and states of the machine. One can simply emulate what a pentium chips does with the machine code it is executing, and know exactly what goes on in the machine, from now to infinity.