Multi-tape Turing machines, Turing equivalence and Turing completeness

Introduction

Introduction

Multi-tape Turing machines

Turing equivalence

If two machines can simulate each other they are Turing equivalent.

Turing completeness

If a machine can simulate any Turing machine, it is Turing complete.