Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more

High-performance Computer Systems for Research, Education & Industry!


Under the General term "Computer" we see a calculator which transforms an amount of input data in a certain amount of output data. Usually the data represent a specific problem, which can be solved thus by the computer. If a specific set of input data results always in the same kind of output, we speak of a deterministic Turing machine, which is named after the British mathematician and computer scientist Alan Mathison Turing (1912-1954). Turing became famous, among other important achievements, by the code crack of the German Enigma encryption machine, which meant a valuable contribution to the defense of the country for the United Kingdom in World War II.

Alan Turing
Alan Turing, 1951 – in the public domain

You can see how a Turing machine is generally structured in the following block diagram:

(Non-) Deterministic Turing Machine
Turing machine, Georg Gesek

The Turing machine consists of a register of conventional bits, which can be directly fed from external source of symbols (input set of symbols), and then interpreted by the machine as program instructions or data. The language is fairly easy, there are commands to move the memory band (read / write - tape) connected to the register, as well as commands for writing or reading the symbols on this band. The individual positions on the tape are well defined, in computer terms, this is called "addressable". Each process step of the computer program is temporally separated from the other by means of a clock (cycle). Apart from the program commands to move, read and write the tape on arbitrary positions, the arithmetic & logic unit (ALU) of the Turing machine has implemented all necessary mathematical functions, in order to perform all kinds of operations.

This is where the so-called deterministic Turing machine differs from the non-deterministic. While the deterministic version has only functions available, which can produce only one specific output from a certain input, the non-deterministic version also has the possibility of a relation, which is therefore able to produce several versions of output from only one set of input. Which one of the possible results is selected is purely random, determined by a non-predictable, stochastic source. The so-called non-deterministic Turing machine (NDTM) therefore is not the opposite of the deterministic (DTM) variant, but has to be understood as relational extension to it.

Site Notice  |  Terms of useGeneral terms and conditionsprivacy policy | © Novarion Systems GmbH 2020

Fields marked with * are required.