Universal Turing machines, the fetch-decode-execute cycle, and Turing completeness

Introduction

Universal Turing machines

Rather than have the algorithm be part of the Turing machine, the algorithm is included in the input.

This allows a universal turing machine to simulate any other Turing machine, given the algorithm as an input.

The computer program is stored in memory on the tape.

Introduction

The fetch-decode-execute cycle

control unit does: + fetch instruction + decode instruction + execute instruction

Regular Turing machines do not need to do this, as there is no program to fetch.

Turing completeness

Introduction

A computer which can simulate any Turing machine can, by the Church-Turing thesis, compute any effective method on the natural numbers. Such a machine is Turing complete.

As the universal Turing machine can simulate any Turing machine, it is Turing complete.