TOC-Church-Turing Thesis and TM Variants

Church-Turing Thesis

+ Church-Turing Thesis

Any real-world computation can be translated into an equivalent computation involving a Turing Machine.

Turing Complete

Turing completeness is the study to describe the computability of a computation model, or the expressability of a language.

TM Variants and Equivalence

Stay - Option TM

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:

+ Def: Stay - Option TM

A stay-option TM is a 7-tuple $(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{\text{accept}},q_{\text{reject}})$, where:

• Each component is the same as a standard TM except for the transition function:$$>\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R,S\}$$Here, $S$ represents the "stay" option, allowing the head to remain on the same tape cell.

Equivalence between TM and Stay-Option TM

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 $q_s$.

Stay-option TM transition:

$$q_i\stackrel{a\to b,S}{\to }{q}_j$$

Simulated standard TM transitions:

$$q_i\stackrel{a\to b,L}{\to }{q}_s\stackrel{◻\to ◻,R}{\to }{q}_j$$

Where $◻$ represents an arbitrary symbol in $\mathrm{\Gamma }$ (the tape alphabet).

Semi-infinite tape TM

Multitape TM

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:

$$\delta :Q\times {\mathrm{\Gamma }}^k\to Q\times {\mathrm{\Gamma }}^k\times \{L,R,S{\}}^k$$

The expression

$$\delta (q_i,a_1,\cdots ,a_k)=(q_j,b_1,\cdots ,b_k,L,R,\cdots ,L)$$

means:

• $q_i$: The current state of the TM.
• $a_1,\cdots ,a_k$: The current tape symbols pointed to by each head.
• $b_1,\cdots ,b_k$: The new tape symbols written by each head.
• $L,R,\cdots ,L$: The movement direction of each head ($L$ for left, $R$ for right, $S$ for stay).

2D-tape TM

Nondeterministic TM