Next:
Turing Machines briefly defined
Up:
Decidability Truth
Previous:
Contents
Background for Decidability
Turing Machines briefly defined
Procedures and Functions
Procedures equivalent to TM's
More functions than procedures
Problems
A problem is a yes-no question
Reducibility
A reducible to B means A at least as hard as B
Encoding and Algorithms
Problem instances as strings, problem as language
root
6/10/1998