Notes - Pages 200-end

Decidability (Ch 4)

  • Simulate on a Turing Machine the previous chapters concepts, FA/PDA
  • if the TM finishes on a halting state, accept or reject, i.e. it is decidable.
  • Decidable languages / machines and their constructions...
  1. Simulate a DFA by encoding the machine on the tape with the input string to run it on
  2. Simulate a NFA by converting it to a DFA, repeat 1.
  3. Simulate a regular language by building the NFA, encode it on the TM tape and input string to recognize
  4. Emptiness TM checks if a FA accepts any strings at all, if it ever accepts then reject, otherwise accept
  5. Test if two DFAs are equal, construct a DFA s.t. the recognized language is the symmetric difference of the two input DFAs. If this DFA is empty then the two input DFAs are equal.
  6. Both CFG and CFLs are decidable, but same technique to test equality of grammars fails.

Undecidablity

  • Simluating a TM on a TM is not decidable, but is recognizable. Half the halting problem, only accept halt state.
  • A decidable language and its complement are turing recognizable, therefore the language of TM does not have a turing recognizable compliment.

Reducibility (Ch 5)

  • TM equivalents of 1-4 above are undecidable due to halting problem.
  • A linear bounded automaton is a TM that has only the memory equal to its input which can be padded, due to this it has a finite number of configurations and thus is a decidable turing machine.
  • Map reducible turing machines relate two turing machines through a function applied to the reconigzed string of one machine as a recognized string of the second machine.
    • un/decidability maps to the reduced machine

Chapter 6

  • recursion theorem - a TM can read its own description, load itself, run, and repeat the process.
  • definition of information - smallest possible representation, the author constructs a TM encoded on a tape that when ran leaves only the information on the tape

Chapter 7 & 8

  • P is solvable/decidable in polynomial time on a deterministic turing machine
  • NP is solvable in polynomial time in a non-deterministic turing machine
    • It is easy to verify the solution on a deterministic turing machine in polynomial time, but solutions on a deterministic turing machine as a model for a computer it takes exponential time
  • NP Complete
    • The set of NP problems that the non-complete problems can be reduced to.
    • Solving on of these in polynomial time on a deterministic turing machine would prove P = NP
  • Chapter 8 looks at space limitations with similar taxonomy