07 Turing Machine

Last Updated: 2 years ago2023-01-25 ; Contributors: AhmedThahir

Cromsky Hierarchy

Turing Machine

NFA + Read/Write Capability

• Read/write happens from/to an ‘infinite tape’
• Read-write head can move left and right

• Initially, all cells of the tape have special blank symbol $\square$, except where the input string exists

• FSMs always halt after $n$ steps, where $n$ is the length of the input. At that point, they either accept or reject.

• PDAs don't always halt, but there is an algorithm to convert any PDA into one that does halt.
• Turing machines can do one of the following
• Halt and accept
• Halt and reject
• Not halt If a turing machine loops forever $\implies \not \exists$ algorithm to solve the problem

Symbol	Meaning
$Q$	Finite set of states
$\Sigma$	Finite set of input alphabet
$\Gamma$	Finite set of tape alphabet, such that $\square \in \Gamma$ $\Sigma \in \Gamma$
$q_0$	Start state
$q_\text{acc}$	Accepting state
$q_\text{rej}$	Rejecting state
\(\delta\)	Transition function \(Q \times \Gamma \to Q \times \Gamma \times \text{\{L, R\}}\)

Transition in Expression form

$\delta(q_0, a) = (q_1, b, L)$ represents a transition with

• Current state $q_0$
• $a$ is current tape input character
• New state $q_1$
• $b$ is new tape input character
• $L$ is the direction that read-write head moves

Transition in Diagram Form

<tape_input>/<tape_write>, <direction>

Uses

• Language decider/recognizer
  • Yes/No output
  • Halts for correct input
  • May not halt for wrong inputs
• Compute functions
  • Reverse string
  • Computing systems

Hailstone Sequence

For example, for a starting number of 7, the sequence is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, .... Such sequences are called hailstone sequences because the values typically rise and fall, somewhat analogously to a hailstone inside a cloud.

Suppose we have

(Code not required to be studied)

#include <stdio.h>
int main()
{
  unsigned int n;        
  printf("Pl. enter no :");    
  scanf("%d", &n);    

  while ( n > 0 )
  {
    printf( "%d ", n);
    if (n == 1)
      break;
    if (!(n & 1))
      n /= 2;
    else
      n = 3*n + 1;
  }    

  printf("Done \n");
  return 0;
}

Is there any n for which the program does not terminate, ie does not converge to 1? It is inconclusive, as we do not know.

Hence, the turing machine may not halt for this problem.

Questions

\(0^n 1^n, n \ge 1\)

\(w w\)

Kinda complicated

\(w w^r\)

Kinda complicated

Balanced Parantheses

We first look for closing bracket; The opening bracket for a given closed bracket is always the first one on its left; converse statement is not true.

\(w\#w: 011\#011\)

Add \(b\) to match \(a\), such that \(a^n b^n\)

Convert \(w \to w w^r\)

Pretty complicated

Multiplication

Pretty complicated

Comments