Version 11 of mathematical foundation of computers and programs

Updated 2012-06-01 03:00:44 by RLE

page by Theo Verelst

Of course, I run the risk 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 really necessary, but I think this page will be compact and relevant enough, because the subject deserves a broad audience. As always comment and add (in separate enough 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 finite state machine model, which can be mathematically modeled 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 understandable input sequences and memory states, and their humanly speaking hopefully logical outcome. Such as that one defines addition instead of some far fetched logical function mapping no one would ever find use for or have useful thought association with, of which there are almost infinitely many, and many more than functions which have logical associations in at least some human brains.

A Finite State Machine is a model which makes a Turing machine effectively and simply separates 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 output 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 pins allows a digital tester to enter a (almost complete) state into the Pentium-s' 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. To visualize this, consider making a complete and errorless disc image from a machine, and put the disc with that copy in similar machine, adjust that machine to preferably have the same serial numbers and battery backed memory contents, and of course let it have the same configuration and peripherals, and start it up. It will do exactly the same if the mouse, keyboard and network interfaces receive the same treatment. Perfect copies. Put the copy on before the original, and one can predict what the original will do. Except for the internet clock service...

That is not exactly true when one connects a network, or some input device, because then one would have to be informed as to what those input devices will feed the computer with, and give a timeframe for that exact information with clock cycle accuracy O(nano seconds), which is often very impractical, though not for an EE in the field.

So when we see a computer as a function, with as it input some starting state (disc content and initial memory content, including CMOS and EEPROMS), and the exact input patterns it finds from the time we switch it on, it is exactly, to the very last bit in every little clock cycle predictable what that machine is going to do. Given that one knows what certain what a designer may call indeterministically opening parts will do, like in an extreme case an electronic noise generator circuit, which one could characterize but hardly predict exactly. And apart of course from when an error occurs, like a memory or disc fault, or a electronic impulse interfering with the machine. Or a nuke melting the thing to unrecognizable shreds in milli (pico?) seconds.

A network, as a historic and valid example an ethernet, can be indeterministic in nature, which means that only an electronics expert with accurate and complex probes and knowledge of the circuit can predict what it will exactly do in certain cases, like when packets collide on the network cable. That is not necessarily problematic, but is strictly speaking containing behaviour which is not projectable on the finite state machine behaviour or a exactly known Turing machine composition.

A von Neuman architecture is where we have a processor 'core' and a memory connected over what one could call the von Neumann bottleneck (communication speed-wise), where instructions and data pass between the core where computations take place and the memory where all is stored, except, in practice, in some smaller registers or memories in the processor core.

And alternative architecture is a parallel architecture, I like the example of the Connection Machine, which contains thousands of cells which contain lists and which can associate and communicate as basic and efficient behaviour. Such a machine can also be modeled as a finite state machine, but is not a von Neumann architecture by nature. All PC's and regular workstations are, except strictly speaking for graphics card instructions and MMX like things.

Important for software design issues is that practically speaking, the finite state machine which is the processor core and memory and interfaces progresses through its states according to relatively limited rules, given the number of possible state progressions which could be defined for each state. As many programmers known and some less have experience with, the lowest level at which we can instruct the course of events in the big computer finite state machine is assembly code, which is a grand simplification of groups of possible state progressions for the duration of a small number of clock cycles, in a form which is more than sensible enough for certain classes of human beings and therefore overseeable and understandable.

Each of such instructions makes the whole finite state machine of the computer traverse its state space a few steps, which are primarily chosen by the instruction which stored in the memory of the von Neuman machine model, which spawns a more or less fixed sequence of actions and therefore state transitions, sometimes just a few, for complex instructions hundreds or so. Older machines, and some special contemporary ones can be micro programmed, which means that each state transition for a certain conventional machine instruction can be programmed, so that one can change the state transitions effectively going on for an instruction with a certain binary coded name.

All compilers, programming languages, operating system routines and programs and all user programs in the end are executed on a normal computer as machine instructions, with completely well defined and accurately predictable behaviour.

As an example, an instruction definition from the Intel Pentium data sheet:

http://82.168.209.239/Wiki/intelpent1.jpg

Its from www.intel.com, that is the people who make the d* chip, in the section for a 1.7 GigaHerz Pentium version.

The instruction to add, in binary form two numbers, from different sources and the result can be stored in different places, either in the main memory or in registers on the chip. The opcodes are the binary values which actually appear in the memory of a program when it is supposed to binary add numbers, and could be seen by inspecting the memory.

The relevance for Tcl programmers or at least thinkers about the language is clear: everything in the end ends up as such instructions in the machine we call a computer. Of course a different machine when one uses another brand and type of computer, for instance a Macintosh, which has a different processor, which also has a different 'opcode' for addition, but most likely also operates on similar operands in comparable variations. For most workstations, the same, except there are RISC chips for instance which probably limit the possibilities per instruction somewhat, and CISC processors which maybe can do more with the concept of the addition type of instruction.

As a bit advanced programmers would know of course, a compiler takes sublists of source code and translates them to lists of machine code, which are then linked together by the linker, which resolves the cross references between various parts of the code.

Often, higher level languages make use of the concept of stack based data passing between what can be seen as parts of code organized as functions, but this already is a convention or method, which is because of that particular higher level language being used.

Not in the picture here, though not strictly outside the FSM model is the occurrence of interrupts, which changes an input to the state machine a certain points in time. Programmingwise that changes the course of what can be called program flow at some not exactly planned point of the processors' running.

Tcl is a natural in its list idea at least in the way that a processors main memory is also easily envisageable as long list of memory places or instructions or data, physically not exactly as a linear list, but as memory chips are, more or less really a list with numbered entries.


DKF: All static (strictly all bounded) arrangements of computing systems can be modelled as FSMs. They've all got states and transitions between them, and that's about all you need. You can even model parallelism within a FSM (nondeterminism is useful for this sort of thing) though you'll tend to get much more compact representations when you use nets of communicating machines.

Things get a bit more complex when you want to model infinite data or infinite numbers of computing elements... ;^)

TV We have the famous problem of the dining philosphers which requires knowledge about the initial event(s) to resolve as a generally interesting problem. A seriously non-deterministic problem is an ethernet. There, we have electronically, that is even in principle unprogrammable collision detection and hold off logic and simultaneous event resolution, which are in principle impossible to determine and predict. Also, in network, and multi tasking OS calls, timing may be practically or in principle unpredictable (because of inaccurate interrupt clocks or practical inpossibility of predicting when it will hit in), and therefore there is an indeterminate factor to be accounted for in a theory which includes models for such cases.

Infinite computing elements in practice is never fully reached with digital computers, they are all turing like machines with discrete and therefore bounded memories, and of discrete number and therefore capable of generating bounded contention or assignment problems. Solving a differential equation and making a continuous and possibly infinitely dimensional state is another story.

A problem of the connected machines idea in strict mathematics is that it is not a given that combinations of finite state machines are themselves automatically stricly decent FSM's. At least the initial input for a round-coupled system is uncertain.

Graphs of connections (strictly mathematical) functions are VERY problematic: two functions with simplistic domains and range connected in a simplistic way will leave you with a resulting 'function' that is no longer a function, but in fact has introduced a state, and unknown output even for certain known inputs. (See the example on the Flip Flop page).