Model of computation

A computation model is a formal way of representing abstract computation. Most models aim to represent –more or less faithfully – computations done by an actual physical machine abstracting away technicalities and providing hints on the inner cost in the model of performing a given computation.

Classical models of computation are discrete machines, their internal states can be describe by a finite amount of information. Other types of model exists, like analog computer story (not in the scope of this lecture).

Alphabet and words

An alphabet \(\Sigma\) is a finite set of symbols. For example, \(\{a,b,c,d\}\), \(\{0,1\}\) etc. A word \(w=u_1,\dots,u_k\) on \(\Sigma\) is a finite sequence of elements of \(\Sigma\). We denote by \(\Sigma^*\) the set of words on \(\Sigma\). For example \(001100\) is an element of \(\{0,1\}^*\), that is, a word on \(\{0,1\}\).

Turing machines

Turing Machines are one of the most classical model of computation. It is not especially practical nor elegant but it has a huge historical importance and is the basis of classical Complexity theory.

A (Deterministic) Turing machine is a tuple \((Q, \Sigma, q_0, q_a, q_r, \delta )\) where:

• \(\Sigma\) is a finite set of letters (an alphabet). We denote also by \(\Gamma=\Sigma\cup\{\_\}\) the working alphabet with \(\_\) a fresh blank symbol not in \(\Sigma\).
• \(Q\) is a finite set of states,
• \(q_0\), \(q_r\), \(q_a\) are states (element of \(Q\)), respectively called the initial state, the rejecting state and the accepting state,
• \(\delta\) the transition function, that is a function \(Q \times \Gamma\to Q \times \Gamma \times \{-1, 0, +1\}\).

Memory model

This computational model is equipped with a bi-infinite tape (i.e. a function from \(\mathbb{Z}\to \Gamma\)) representing the memory. The machine has a head that moves on the tape reading and writing values. At a given time, we use the information of the head and the current state to lookup in the transition function the action to perform. That is, the symbol to write as the current position, the new state to reach and the head movement (left, right or stay).

To be a valid memory configuration, we add the extra constraint that the content of the bi-infinite tapes must absolutely be of the form \(\_^\infty u \_^\infty\) with \(u\in \Sigma^*\). That is, we never have a blank symbol except on the sides. Thanks to this constraint we can call \(u\) the tape content, which is well defined and finite.

Configurations

Given a Turing machine \(M=(Q, \Sigma, q_0, \delta, F)\), a configuration of \(M\) is a tuple \((q, u, i)\) where \(q\) a state, \(i\) is an integer called the head position and \(u\) is a word of \(\Sigma^*\) called the tape content.

Given a configuration \(c=(q, u, i)\) of \(M\) with \(q\not\in\{q_a, q_r\}\), we define \(d=(p,v,j)\) to be:

• \((p, \sigma, b) = \delta(q, u_i)\),
• \(v_t=u_t\) if \(t\neq i\) and \(v_i = \sigma\)
• \(j=i+b\).

We say that \(d\) is the next configuration after \(c\) by \(M\). We abuse notation and denote it by \(\delta(c)\).

Executions

Given a word \(u\in \Sigma^*\), we denote by \(I(u)=(q_0, u, 0)\) the initial configuration of \(M\) with the tape initialized with the word \(u\) written from position \(0\) of the tape. We say in this case that \(u\) in the input of the Turing machine.

The execution of \(M\) on input \(u\) is the sequence of configurations \((c_i)\) defined by: \(c_0=I(u)\) and \(c_{i+1} = \delta(c_i)\) if the state of \(c_i\) is not \(q_a\) nor \(q_r\) and \(c_{i+1}=c_i\) otherwise.

The Turing machine \(M\) accepts the word \(u\) if there exists \(i\) such that \(c_i\) has state \(q_a\). \(M\) rejects the word \(u\) if there exists \(i\) such that \(c_i\) has state \(q_r\).

Given a Turing machine \(M\), the language \(A\) accepted by \(M\) is the set of words it accepts. The language \(R\) rejected by \(M\) is the set of words it rejects.

If \(A = \Sigma^* \setminus R\), that is, if for every word \(u\) of \(\Sigma^*\), \(M\) reaches state \(q_a\) or \(q_r\) at some points, we say that \(M\) decides \(A\), and we denote this language by \(L(M)\).

Given any language, we say it is Turing-Computable if there exists a Turing machine that decides it.

If the set of words accepted by \(M\) is \(L\) but the set of words rejected by \(M\) is not \(L^c\) we say that \(M\) semi-decide \(L\). Remarks that it can happens when the Turing Machine reaches an infinite loop.

Examples

• Examples: \(\{a^nb^n \mid n\in\mathbb{N}\}.\)
• Exercise (Palindromes): \(\{u\mid u=\text{miroir}(u), u \in \{a,b\}^*\}\)

Turing-Computable

There exist languages which are not Turing-Computable. By a simple counting argument: The set of subset of \(\Sigma^*\) is not countable but the amount of Turing machine is countable.

Alternate model of computation

Turing variations

• Infinite tape only (restriction): the Turing machine can use a tape infinite only on the right.
• Multiple tapes: the Turing machine can use several tapes instead of only one.
• Model with outputs: the Turing machine has an output tape and instead of only accepting words it outputs the content of this tape.

More details in reference books.

Non-Turing variant

We have seen that Turing Machines are simple to describe but not really close to the actual way computations are performed by computers. Computers are closer to the Von Neumann architecture with a different memory model where memory cells can be accessed without moving slowly to it but by jumping at a given address.

It makes huge a difference in practice since, for instance, Turing machine cannot perform dichotomy search efficiently in a sorted array.

A closer to reality model has been formalized: it is the RAM (Random Access Memory) model. It is the canonical model on which complexity theory is built on, but it is complicated and full of caveat.

Many other alternative models of computations exists to take into account various notions of computability and their associated cost analysis.

Python as a model of computation

Unlike compiled programming language, Python is executed through a virtual machine, that is a model of computation simulated by computers. It is an intermediate model of computation with its own machine-like definition, memory models, etc.

We can access the machine code of a Python function directly within Python:

import dis
def hello_world():
  print("Hello World")
for i in dis.Bytecode(hello_world):
  s = i.opname
  if i.argrepr:
    s += f" ({i.argrepr})"
  print(s)

RESUME
LOAD_GLOBAL (NULL + print)
LOAD_CONST ('Hello World')
PRECALL
CALL
POP_TOP
LOAD_CONST (None)
RETURN_VALUE

Compiled the: mar. 21 janv. 2025 22:04:06 CET