FIT2014 Lecture Notes - Lecture 15: Universal Turing Machine, Turing Machine, Regular Language
29 Jun 2018
School
Department
Course
Professor
Lecture 15
Variation on Turing Machines:
- Direction: stay still, as well as left or right
- Two way infinite tape
- Multiple tape
- Separate input output tape, work tape
Turing Machines for computing functions:
So far Turing machines just accept/ reject. TM can also compute function
Successor: using the unary code for natural numbers build a Turing Machine that represents the function f(n)=
n+1
Universal Turing Machine
Input a b
Tape a b #
Start State 1 and Accept 2
Conditions to check
- Check whether there is a row with a 1 in the From column.
- Check that there is no row with a 2 in the From column.
- Check there are no two rows with the same numbers in the From and the same letter in the Read column.
Code Word Language (CWL)
CWL is the regular language (a+ba+b (a ∪ b)5)*
Words which encode a TM belong to CWL.
• * outside mean s number of rows and inside the () is a row
• + is at least one
• A is the number from and to
• Not all words in CWL encode a TM
An Universal Turing Machine (UTM)
A Turing machine can run any TM on any input data
Document Summary
Direction: stay still, as well as left or right. Successor: using the unary code for natural numbers build a turing machine that represents the function f(n)= n+1. Check whether there is a row with a 1 in the from column. Check that there is no row with a 2 in the from column. Check there are no two rows with the same numbers in the from and the same letter in the read column. Cwl is the regular language (a+ba+b (a b)5)* Words which encode a tm belong to cwl. * outside mean s number of rows and inside the () is a row. + is at least one: a is the number from and to, not all words in cwl encode a tm. A turing machine can run any tm on any input data. Importance of universal turing machines theoretical model of one computer simulating another. Enables us to ask whether various problems about computers can be solved algorithmically.
