3 - Turing Machines

• Palindrome


  string which backwards reads the same as forwards
• for odd palindromes we are allowed to choose the symbol in the very center of the string.
• Palindrome contraints :

  • even : n/2
  • odd : (n-1)/2
• the total number of binary even-length palindromes grows exponentially in the length n
• counting argument

  when disputes can be settled by counting the number of possibilities
• DFA's can't identify palindromes --> the palindrome structure only manifests itself after we have processed half of the string (only if it has at least 2^(n/2) distinct internal states --> exponential growth of states)
• DFA struggle to identify palindromes :

  • they must process input symbols sequentially from left to right in one go
  • they can only read input symbols (no memory)
• square symbol

  empty paper
• Identify a palindrome by an iterative checking procedure. Will be n/2 iterative application of this one-sided tests.

  N(k) = 2k+3 for k in {0,2,4,6, .. n } . At most N = 0.5n^2 + 5/2 n 

• worst case number of steps (palindrome) scales quadratically
• Turing machine model components :

  1. the finite state control (each instant == 1 state)
  2. the tape (consists of tape squares)
  3. the tape head (current position)
• In which optic are DFA similar to a turing machine

  1. finite resources are enough to specify
  2. can perform computations on a input strings with varying length

  difference :

  1. They can loop back and forward -> longer run times
• halting states

  accept, reject states, if the machine enters either of these it stops immediately
• Turing machine (TM)

  A) finite

  B) internal states

  C) input alphabet

  D) tape alphabet

  E) transition

  F) start

  G) accept

  H) reject

  
• Turing machine

  A) accepts or rejects

  B) read/write

  C) internal states

  D) input alphabet

  E) tape alphaebt

  F) transition

  G) start

  H) accept

  I) reject

  
• Transition function TM $\delta$(p,a) = (q,b,D). WHere p,q are states and a,b are tape alphabet symbols
• $\delta(p,a) =$$(q,b,D)$

  • p,q are states
  • a,b are tape alphabet
  • D the direction of the tape

  A) a,b,D

  
• a computing step is determined by the content of the tape and the transition function
• TM are deterministic models of computation