Turing Machine


### The most general computing model
## TMs

[Turing Completeness](https://texonom.com/turing-completeness-c600eeb9053b4ba08fbabc74de04dd58)


[Busy Beaver](https://texonom.com/busy-beaver-8ebb169dba53498aa6633937b7ae0a1c)

> <details><summary>
> 
> `math: M = (Q ,\Sigma, \Gamma, \delta, q_0, B, F)`</summary>

> 1. Q is finite set of control states
> 2. `math: \Sigma `is finite set of input symbols
> 3. `math: \Gamma \supseteq \Sigma `is a finite set of tape symbol
> 4. `math: q_0 \in Q `is the start (initial state)
> 5. `math: B \in \Gamma `is the blank symbol
> 6. `math: F \subseteq Q `is the set of final  (accepting) states
> 7. `math: \delta : Q \times \Gamma → Q \times \Gamma \times\{L, R\} `is transition function which describe finite control by control stage and symbol
> </details>
> 

> <details><summary>
> 
> Property</summary>

> - Initially, the tape head is at the leftmost cell of the input right of B
> - Since we have **infinite table**, so we cannot apply high level description for finite table
> - since we have reusability we can call other subroutines by another Turing machine
> </details>
> 

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fbe15114a-5593-475c-bc00-c7676dd9f2e5%2Ftemp.jpg?table=block&id=f39b32f9-609b-4edf-9c7b-2880f83c7066&cache=v2)

> - **δ(q,X) = (p,Y,D) - overwrite X with Y in q**
> <details><summary>
> 
> Based on the “scanned” symbol and the current state of the ﬁnite control, the macine does the following **in one move**</summary>

> (a) Change its state 
> (b) Overwite a new symbol on the tape cell being currently scanned; it could rewrite the same symbol that was read 
> (c) Move the tape head left or right
> </details>
> 



### Tape
1. finite length symbol input is placed on the tape
2. special symbol called the blank B which is tape symbol, not input symbol
3. all other tape cells, extending infinitely, which are all initialized to be hold B



## ID(instantaneous description)
contains all the information to exactly capture current state of the computation scanning ith symbol - **ignore B**
$$ID: X_1X_2 \cdots X_{i-1}qX_i \cdots X_n$$
4. current state q
5. position of the tape head: will change Xi
6. contents of all the tape cells between the leftmost and rightmost non-blank symbol. this is finite many cells. those symbols are only made up by tape symbol except q in ID
> \vdash^* is the reﬂexive, transitive closure of \vdash




## Acceptance
$$iff \,\, q_0w \vdash^* \alpha_1q\alpha_2$$
L(M) = {w | M accepts w}. We call L a **recursively enumerable language** (or RE in short)
**where q ∈ F and α1,α2 are some strings**. 
> - Note that the machine **may not** read all the symbols in w.
> - It may pass back and forth over some symbols of w many-many times.



## Language property
- Halting : \deata(q,x) is undefined
- Convention : We will always consider TMs that halt when they reach an accepting state.
> - Semi-decidable : L is semi-decidable if there is a TM M such that L = L(M).\
>> 1. So on strings w ∈ L, M reaches a ﬁnal state and halts
>> 2. on string w / ∈ L **M either halts without reaching aﬁnal state or it never halts**
- Decidable/Recursive : L is decidable/recursive if there is a TM that halts on every input and L = L(M)
all process decidable, halting problem is undecidable



## Functions - normal FM
TMs can be seen as computing (partial) functions f : N → N as follows:
7. If M does q00i `∗ qh0j, where qh is a special halting state of TM, then value of function on i is j. Namely, f(i) = j (other format can be also)
8. Number i represented as 0i. How is 0 represented? 
9. Function is undeﬁned on i, if M on input 0i does not haltor halts without proper conventions, i.e., halts in a state other than qhor halts with tape contents not consisting just of 00s, et



# Programming Technique for TMs
**All by these do not improve computation power but these tricks make easy programming**
> - **Storage in the state**
>> We just think of the state as a tuple—No extension to the TM model
>> The machine remembers the ﬁrst symbol read in its state
> - **Multiple tracks**just useful structure
> - **Multiple tape (**n-TM or `math: M_n`)
>> Can Use States to remember
>> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F86009ef1-ff00-48bd-8df1-50b9ddf198aa%2FUntitled.png?table=block&id=d1e780dd-2796-41d8-8e00-eab74fb3e023&cache=v2)

> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F6b36a225-0fea-4650-ac52-7641c7640ecc%2FUntitled.png?table=block&id=e86ecae3-f873-4682-b0ce-b8188a7bf30f&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F5818466a-0bbf-4a9b-a24c-54e046788425%2FUntitled.png?table=block&id=a2d77e55-d7bb-42ea-8c5d-2676b4304144&cache=v2)
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F8d995139-e0a1-4abf-b99a-3e5d63db10bf%2FUntitled.png?table=block&id=022193c6-a27e-4a68-b386-2bfbaee179aa&cache=v2)

> Computation power of Convention TM is not different but number of state Big-O is different




## **Subroutines - Convention TM**
Convenient to think of TMs as a collection of interacting components or “subroutines”; M1 calls M2 by passing control to the start state of M2.
<details><summary>

General Subroutines</summary>

Before returning read the return address into ﬁnite control, and transfer back to the right state; may have to erase things on the tape.
</details>




# Simulating M_n with M
<details><summary>

Conﬁgurations M2</summary>

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fe61ecbdd-eced-4ab4-a8b0-37a81d7aa055%2FUntitled.png?table=block&id=55eac4c9-0b40-458b-8f3f-b558c7c5e8b0&cache=v2)
</details>

<details><summary>

Simulating Transition M2</summary>

</details>

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fd5a323c2-b25b-4b26-bb7c-5c608babb33c%2FUntitled.png?table=block&id=1491a0c6-bde2-4e3c-bad8-75d2fd6a9ee9&cache=v2)


**Claim: We can simulate a k-tape TM using a single-tape TM M.**
<details><summary>

proof : </summary>

Deterministic: At each step, there is one possible next state, symbols to be written and direction to move the head, or the TM may halt.Nondeterministic: At each step, there are ﬁnitely many possibilities. 1. δ : Q×Γ → 2(Q×Γ×{L,R}). For instance, δ(q,X) = {(p1,Y1,D1),...,(pk,Yk,Dk)} 2. `deﬁned like for deterministic TM. X1X2···Xi−1qXi···Xn` X1X2···pXi−1Y ···Xn, if (p,Y,L) ∈ δ(q,Xi); case for right moves is analogous 3. Nondeterministic TM accepts w iﬀ there is a sequence of moves leading to an accepting state, i.e., q0w `∗ αqβ, where q is a ﬁnal state
</details>

Claim: If L is accepted by an NTM N, then there is a DTM M such that L = L(M).
<details><summary>

proof:</summary>

Note: Clearly, the converse of the above result holds since DTMs are “special forms” of NTMs.Rough Idea for proof: M tries to keep track of all possible “conﬁgurations” that N could possibly be in at any time.
1. Works for regular languages because we only need to keep track of the states of the NFA, which is a ﬁnite set
2. Does not work for PDAs, because we need to keep track of the various possible stack contents
3. Is not convenient for TMs either because each choice leads to various possible tape contents, head positions, etcM simulates each possible sequence of computation steps that N may try!
</details>

> empty completeness?




<details><summary>

**Deterministic Turing Machine**</summary>

<details><summary>

Observation: If N accepts w in n steps, then there is a sequence of n nondeterministic choices, i1,i2,...,in, that cause N to accept w.The DTM M will search for such a sequence of nondeterministic choices:</summary>

1. Given the sequence of choices that N makes, M can simulate N
2. Don’t know what the right choices are. So simulate N for each possible choice!
3. Don’t know how many steps N takes to accept w. Simulate N on sequences of all possible lengths!
4. Essentially, do breadth ﬁrst search on NTM’s “computation tree”
</details>



<details><summary>

Deterministic Simulation: DetailsDTM M uses 3 tapes to simulate NTM N</summary>

1. Tape 1 always holds input w
2. Tape 2 is used as N’s tape when simulating N on a sequence of nondeterministic choices
3. Tape 3 stores the current sequence of nondeterministic choices.M uses a subroutine that generates the “next” sequence of choices, after a simulation of N is complete 1. Subroutine generates sequences in {1,2,...r}∗ in lexicographic order, i.e., 1,2,...,r,11,12,...,1r,111,112,...
4. Given a sequence (say 111) on Tape 3, the subroutine will write the next sequence (112) on Tape 3
</details>



<details><summary>

Deterministic Simulation: Implementation</summary>

1. Initialize: Tape 3 to the string 1
2. Copy contents of Tape 1 onto Tape 2
3. Simulate N using Tape 2 as its tape(a) At the next step of N, if state is q, Tape 2 and 3 contain X and i respectively, then simulate the ith possibility in δ(q,X). (b) After changing state, Tape 2 contents, and head position on Tape 2, move Tape 3’s head to the right. If Tape 3 is now scanning B, then goto step 4 (c) If N accepts, then accept and halt. Otherwise, goto step 3(a) to simulate the next step of N
4. Write the next sequence on Tape 3, erase everything on Tape 2 and goto step 2.
</details>



<details><summary>

Deterministic Simulation: Correctness</summary>

1. M simulates N over and over again, for diﬀerent sequences, and for diﬀerent number of steps
2. If N accepts w, then there is a sequence of choices that will lead to acceptance. M will eventually have this sequence on Tape 3, and then its simulation N will accept
3. If N does not accept w then no sequence of choices leads to acceptance. M will therefore never halt!
</details>

</details>




<details><summary>

**Non-Deterministic Turing Machine**</summary>

Let r = maxq,X |δ(q,X)|. So N has at most r possible choices in each step. Possible runs of N can be organized as a tree.
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F56d771c9-04df-49e4-98e4-e1337f355d23%2FUntitled.png?table=block&id=92469092-ef59-410d-ae7a-f71c6e741d64&cache=v2)
IDi1i2···in = The instantaneous description of N if it choses to take choice i1 in step 1, choice i2 in step 2, and so on.Note that the r choices after each step are not the same! At each step, there are at most r choices
</details>



semi decidable - recognizable
polynomial design


# Church-Turing Thesis
anything solvable via mechanical procedure cna be done on a Turing machine - not mathmatical statement to prove

Evidence: Most extensions to the TM model like multi-tape, non-determinism, multi-dimension, etc can be simulated on a TM. In addition, λ-calculus, random access machines, general recursive functions, general grammars, π-calculus, ﬁrst order reasoning, ... are all equivalent to TMs



## Variant of Turing Machine




