Turing Machines and Decidable Problems
Turing Machines
Material
here
More thoughts:
intro to Turing Machines
|
Example TM: 0^n1^n
|
Example TMs: equal 0s and 1s
Variations of Turning Machines:
Material
here
More thoughts:
TMs as transducers
|
Example Transducer: Computing 2^x in unary
|
Changing TMS
|
Church's Thesis
Decidable Problems and Recursive Languages:
Material
Part1
and
Part2
More thoughts
Closure properties
|
Decidable Problems
|
Some comments on decision problems
Summary from book
here
Extension/Revision Questions:
Turing Machines
and
sols
Decidability and Recursive Languages
and
sols