I am learning about Turing machines. I understand the alphabet set of symbols and the states a machine can be in. However, I do not understand how the transition function works.

I come from a maths background and functions always follow a simple input output. The table of transtions seems out of place.

How does a computer read a table as a function?

  • 2
    $\begingroup$ Discrete functions can be represented by a table. $\endgroup$
    – user16034
    Mar 11, 2023 at 20:36
  • 1
    $\begingroup$ I don't see a table as "out of place" in mathematics. We learn multiplying by memorizing a 10x10-table and when we are adult we switch to group tables. Truth tables. Databases. Adjacency matrices. $\endgroup$ Mar 12, 2023 at 14:13

1 Answer 1


You can think of a function $f:S\times \Sigma \rightarrow S$ as a "table", where the rows are elements of $S$, the columns are elements of $\Sigma$, and the cell's contents is the result $f(s,\sigma)\in S$ of the $s$ of the current row, and the $\sigma$ of the current column.

This is just a more convenient way to write complex transition functions and doesn't have a real semantic meaning.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.