Understanding Church-Turing Thesis and Computability with Turing Machines
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.
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
CMSC 281 W Church Turing Thesis Computable = Computable by a Turing Machine
Church Turing Thesis Computable = Computable by a Turing Machine By definition.
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.
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.
Turing Machine Coding Tricks Remember a symbol scanned
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
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 .
Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape
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.
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
Turing Machine Coding Tricks Remember a symbol scanned Remember a position on the tape Multiple tracks
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
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)
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
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
Universal Turing Machines There is a very specific task that we can have a Turing machine do: Simulate any other Turing machine!
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.
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.
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.
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!
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.
