date: 2024-12-27
title: 10-TOC-UTM
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- TuringMachine
publish: True
TOC-Universal Turing Machine
A TM can be defined as a 7-tuple.
The input of a TM is a string.
But the input of an algorithm can be any well-defined mathematical object.
If TM and algorithm are equivalent, we need to describe the input of an algorithm as a string.
The description is an encoding of the input.
Suppose the input is
We also assume that each
M can be designed on high-level.
M = "On the input
The simulation uses a multi-head 2-D tape TM
Suppose
M has 5 computation heads which do the following operations.
Initially:
With the encoding of
A Universal Turing Machine
The definition of a universal Turing machine captures the true meaning of Church-Turing Thesis.
TM is a universal computation model, which is the foundation of computers.