Turing Machine
Table of Contents
- `FSA`: finite state automata. A small amount of memory.
- `PDA`: push-down automata. Unlimited memory, usable only in LIFO.
- `RE`: recursively enumerable language. Turing Recognizable.
- `REC`: recursive language. Turing Decidable.
Multi-tape turing machine: The transfer function contains the states and actions of all tapes.
> Prove: Multi tape TM equals to Single tape TM
Add new symbol # to separate the different tapes. Use upper dot to denote the current position of every tape.
> Prove: doubly infinite TM equals to TM
=>: Mark the beginning<=: Use two tape, first the right half, second the left half.
> Prove: Nondeterministic TM equals to Deterministic TM
Use three tape to simulate the non-deterministic TM.
- original tape. As a record, never modified.
- simulation tape. The worker.
- address tape. Contains the instruction of how to perform on tape2 when encountering with multiple choice.
Will refill with the next string in standard string order.
> RE <=> NTM recognize it
> REC <=> NTM decide it
> RE <=> some enumerator enumerates it
- <=: M="On input w: 1. run E, compare with w"
- =>: E=Ignore input:
for i in {1,2,3}
Run M for i steps on each string s1,s2,...,si in standard string order
Any accept, output.
The string will repeat multiple times.
REC is closed under:
- union
- complementation
- concatenation
- intersection
- star
RE is closed under(no complementation)
- union
- intersection
- concatenation
- star
> REC <=> some enumerator enumerates it in standard string order
=>: easy<=:
- if L is finite: just compare with all strings in L
- if L is infinite:
On input w: use E to generate all strings until bigger than w in standard string order if w appears, accept. Otherwise reject
1 How to get the middle of a string?
Move two blank from left and right to the middle. When the two blank meet, it is the middle.
> Describe a NTM for L={0n1y | y = x2 mod n}
- Non-deterministic guess x: 1, 2, 3, …
- calculate x2
- calculate y mod n
- calculate x2 mod n
- compare the previous two results
> infinite RE has infinite subset that is REC
E for RE, run E, output the string in increasing order.
> L={n | at least n consecutive 3s in decimal expansion of PI}
It is decidable.
Two possibilities:
- for every n, there exists
- There's a max N0.
They are complementary to each other. We don't know which one is right at a time, but one of them is guaranteed to be true. Both of them are decidable.
> unary-to-binary
``` 1111 1X111 10XX11 11XXX1 100XXXX ```
- For every 1 after X, change to X
- Go backward, change all 1 to 0 until encounter a 0, change it to 1
> binary-to-unary
``` 101 100X 011XX 010XXX 001XXXX 000XXXXX ```
For every 1 from right, change 0 after it to 1, then add a X