Understanding Church-Turing Thesis and Computability with Turing Machines

Slide Note
Embed
Share

The Church-Turing Thesis states that every computable function can be computed by a Turing Machine. This concept, pioneered by Turing, revolutionized the way we understand computability and algorithms. By breaking down the process into primitive operations, we can express complex algorithms in an understandable manner using Turing Machines.


Uploaded on Sep 28, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. CMSC 281 W Church Turing Thesis Computable = Computable by a Turing Machine

  2. Church Turing Thesis Computable = Computable by a Turing Machine By definition.

  3. Church Turing Thesis Computable = Computable by a Turing Machine By definition. More precisely, this is not something we can prove we can only provide pragmatic arguments why this is something reasonable. This is what Turing proceeded to do.

  4. Computable = Computable by a Turing Machine Turing did something new (for the time) he started to write code for Turing machines. We will do the same: except in a more SE way than Turing did: We will sketch code for primitives which we can then use to implement other primitives, which we can then use to implement other primitives, which we can then use to implement other primitives, which we can then use to implement other primitives, and then we can express algorithms in an understandable manner.

  5. Turing Machine Coding Tricks Remember a symbol scanned

  6. Turing Machine Coding Tricks Remember a symbol scanned Useful to solve Exercise: Suppose the input to a Turing Machine is of the form ay where a is a symbol from the alphabet, and y is a string of symbols. Accept the input if a occurs in y

  7. Turing Machine Coding Tricks Remember a symbol scanned Trick: Increase the set Q of states to ? {? #} where S is the set of symbols and # is a new symbol, meaning no character .

  8. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape

  9. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Useful to solve Exercise: Determine if the first and last character in a string are the same.

  10. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Trick: Enlarge the tape alphabet. For each symbol a, instead of the original character, have two versions, marked and unmarked: + and a a

  11. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks

  12. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks Trick: same as used in the previous marked symbol . Enlarge the alphabet to consist of k-tuples of symbols, for the k-tuple of tracks

  13. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks Multiple tapes Obs.: the number of tapes is a constant, k. Each tape has its own head. The transition function is modified appropriately into tuples (state, symbol1, symbolk, newstate, newsymbol1, newsymbolk, head1move, headkmove)

  14. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks Multiple tapes Constant number of registers Register is just another tape

  15. Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks Multiple tapes Constant number of registers We use more powerful models to argue what machines can do, but often argue about simpler models in proofs

  16. Universal Turing Machines There is a very specific task that we can have a Turing machine do: Simulate any other Turing machine!

  17. Universal Turing Machine There is a very specific task that we can have a Turing machine do: Simulate any other Turing machine! Turing machine M given by list of 5-tuples. Input x to M given. Universal Turing Machine U, on input M, x simulates each step of M on x, until M reaches the YES or NO states of M.

  18. Universal Turing Machine Universal Turing Machine U, on input M, x simulates each step of M on x, until M reaches the YES or NO states of M. Some technical details: States of M are given as q0, q1. qn (numbers written out in binary) Symbols of the alphabet are given as s0, s1, sm M and x are given as a single string M#x, where # is a new symbol.

  19. Universal Turing Machine Universal Turing Machine U, on input M, x simulates each step of M on x, until M reaches the YES or NO states of M. To simulate one move: U has a register, containing the current state of the simulated M. U has a register, containing the current symbol of the simulated M. U has a tape with the (encoded) contents of M s tape, including M s current head position, as well as the 5-tuples defining the moves of M U needs to find the appropriate 5-tuple and execute its move.

  20. Universal Turing Machine Universal Turing Machine U, on input M, x simulates each step of M on x, until M reaches the YES or NO states of M. To simulate one move: U has a register, containing the current state of the simulated M. U has a register, containing the current symbol of the simulated M. U has a tape with the (encoded) contents of M s tape, including M s current head position, as well as the 5-tuples defining the moves of M U needs to find the appropriate 5-tuple and execute its move. We have all the tricks to do so!

  21. Universal Turing Machine (p, a, q, b, movement ) There is a Turing Machine U that given as input the description of a Turing Machine M, and of the input x to M, will produce the same output as M does when given input x U(M,x) = M(x). (more precisely, U has input <M,x> an encoding of M and x) Proof: write the code.

Related


More Related Content