Skip to content

Turing Machines & Programmability

Basics of Turing Machines

img

Church's Thesis

Church’s Thesis states that: Every discrete function computable by any realisable machine is computable by a Turing Machine.

In other words, A turing machine can be made to replace any machine that already exists in general.

A function is computable if an algo can be made to do the job of the function.

The halting problem

The Universal Function

\(f_U (K,j) = T_K(j)\)

This means that a Turing Machine that runs \(U\) is a Turing machine that is capable of simulating an arbitrary Turing machine (with spec. \(K\)) on arbitrary input (\(j\)). This is called a Universal Turing Machine.