5 - Universal Turing machines and undecidability

• uncomputable


  not even semideicdable
• • reg = regular
  • dec = decidable
  • s-dec = semidecidable
• #

  roadblock symbol
• Bit encoding of tuples

  
• ternary alphabet

  {0,1,#}
• Q, alphabet, tape alphabet -> finite sets of symbols

  can store : Q of length N --> bitstrings of length log_2(N) +1

  tuple elements q_0 , q_accept, q_reject
• we want every bitstring to represent some TM so that it immediately halts and outputs reject for any output
• every TM is represented by infinitely many string :
• Turing number : There is a many-to-one correspondence between natural numbers and Turing machines such that (i) the bit encoding in

  {0, 1}∗ of each n encodes exactly one TM and (ii) every TM is represented by (bit encodings of) infinitely many natural numbers.

  We write M = n
• it is possible to devise a universal Turing machine that is capable of simulating the execution of any other TM M for any possible input x.
• Universal turing machine

  A) exists

  B) halts

  C) halts

  D) Turing number

  E) proportional

  
• Let M~ be a TM that uses k independent tapes and runs for T steps. Then we can simulate this computing process by a single-tape TM M that runs for at most 5kT^2 steps.
• TMs are designed to answer decision problems.
• The language accept is semidecidable
• Complement of a language is comprised of all strings that do not belong to the language.

  A) \Accpets

  
• the language halt is semidecidable
• the languages accept and halt are undecidable
• language is uncomputable if it is not even semidecidable
• The language co-Accept , co-Halt is uncomputable
• Suppose that a language and its complement are both semidecidable, then A must be decidable
• liar's paradox

  I am never telling the truth
• Godels incompleteness theorem states that no consistent system of axioms combinable by an algorithm is capable of proving all truths about the arithmetic of natural numbers.
• Endscheidungsproblem

  find an algorithm to determine whether a given sentence of predicate logic is valid