Turing Machine

Table of Contents

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

> Prove: Nondeterministic TM equals to Deterministic TM

Use three tape to simulate the non-deterministic TM.

Will refill with the next string in standard string order.

> RE <=> NTM recognize it

> REC <=> NTM decide it

> RE <=> some enumerator enumerates it

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:

RE is closed under(no complementation)

> REC <=> some enumerator enumerates it in standard string order

  1. if L is finite: just compare with all strings in L
  2. 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 ```

  1. For every 1 after X, change to X
  2. 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