Computer Science Notes

This is a collection of computer science related definitions and terminology.

Turing Machine

Firstly introduced by Alan Turing in 1936, a Turing Machine is a concept, which was used to describe the computability of certain problems. It's made up of:

• An infinitely long tape consisting of sequentially aligned fields, filled with symbols from a predefined alphabet (e.g. numbers and or letters).
• A head that can read and write symbols on the tape and is always on one field at a time.
• A program made up of states that control the head, containing start and final states.

The head moves along the tape in a stepwise manner. Each step is initiated by reading the symbol on the current field. Then, according to the current state of the machine and the symbol read, the field is rewritten and the machine moves either one field to the right or left. This process is repeated, until one of the final states is reached.
Here is a very primitive example of a Turing Machine, with an alphabet of $\{0,1\}$:

Tape	Program
	State Tape symbol Write symbol, Move Tape Next state Notes A 0 1 0, R 0, R A B start state B 0 1 0, R 0, R C B C final state

All this Turing Machine does, is overwrite a single sequence of $1$s, after which it terminates.

Extended Backus-Naur form

The Extended Backus-Naur form (EBNF) can be used to express the syntax of programming languages. It is composed of terminal symbols, which remain unchanged, and non-terminal symbols described by production rules. The EBNF according to ISO-14977 has the following rule set:

• Quotation marks (" " or ' ') mark terminal symbols.
• Equal signs are used to define production rules, which are separated by semicolons, e.g. blank = " ";.
• Commas concatenate terminal or non-terminal symbols, e.g. C scale = "C", "D", "E", "F", "G", "A", "B";.
• Alternatives are denoted by "|", e.g. digit without zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";.
• Symbols in curved brackets are repeated – possibly zero times, i.e. they can also be left out. A special case of this are squared brackets, which tag symbols that are written once or completely left out. Example:
  digit = "0" | digit without zero;
integer = "0" | ["-"], digit without zero, {digit};
• As a counterpart to "|", the EBNF also supports exceptions with the use of minus signs. The exceptions can be grouped in standard brackets to include several at once, e.g.
  natural numbers without zero = integer - ("0" | "-", digit without zero, {digit}).
• Special sequences, indicated by question marks, can be utilized to describe something, which can not be captured by other means of the EBNF notation:
  meaning of universe = "4","2" | ?This is the meaning of the universe?.
• (* This is a comment in EBNF. *)