date: 2024-11-21
title: 09-TOC-TM Variants
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TM
- TOC
publish: TrueTOC-Church-Turing Thesis and TM Variants
Any real-world computation can be translated into an equivalent computation involving a Turing Machine.
Turing completeness is the study to describe the computability of a computation model, or the expressability of a language.
A stay-option Turing Machine (TM) is the same as a standard TM except that the head can stay on the same tape cell in some transitions. Formally:
A stay-option TM is a 7-tuple
Simulating a standard TM on a stay-option TM is trivial, as it simply avoids using the "stay" option.
For the inverse (simulating a stay-option TM on a standard TM), we only need to simulate the transitions that stay at a tape cell. This is achieved by introducing an artificial state
Where
A multi tape Turing machine is like a standard Turing machine with k tapes for a constant k.
Each tape has its own head for reading and writing.
Initially , the input is on tape 1.
The transition function allows the Turing Machine (TM) to read, write, and move the heads on some or all of the tapes simultaneously. Formally, it is defined as:
The expression
means: