Understanding The Importance of Decidability and Turing Machines in Computer Science Theory

Decidability Decidability CSCI 432 Computer Science Theory CSCI 432 Computer Science Theory

Recap of last two weeks Recap of last two weeks Turing Machines are powerful enough to implement any algorithm. TMs can implement any machine level functions of a modern computer. Because high-level languages can be translated into assembly code, any program written in a high-level language can be run on a TM. Any algorithm that can be carried out by a Human can also be run by a TM (Church-Turing)

Thus Thus 1. We do not have to draw out a TM to show the problem can be solved. It is sufficient that we can describe the algorithm. 2. Also, there are some problems that are not solvable. o There exist no TM that solves the problem. "Algorithm" - can be rendered as a TM that halts on all inputs.

Not Decidable Set of All Languages Turing Recognizable Decidable Languages Context Free Languages regular languages

Languages Languages Decidable Language There exist a TM that, when given any input string w, will 1. always halt 2. accept w that is in L 3. reject w that is not in L "Decidable" = "Recursive", "Computable" and "Solvable"

Languages Languages Turing Recognizable Language There exist a TM that, given any input string w, 1. when w is in L, the TM will accept and halt 2. when w is not in L, the TM will either a) reject and halt, or b) loop infinitely "Recognizable" = "Recursively Enumerable", "Partially Decidable", or "Semi-Decidable"

Languages Languages Not Turing Recognizable Language For the best TM for that language: 1. when w is in L, a TM will either a) accept and halt, or b) loop infinitely 2. when w is not in L, a TM will either a) reject and halt, or b) loop infinitely "Not Recognizable" = "Not R.E." or "Not Partially Decidable" or "Undecidable Language"

Purpose of TMs Purpose of TMs 1) "decides" a language if the language is decidable 2) "recognizes" a language if the language is Turing Recognizable 3) "computes" functions "totally computable function" defined for all inputs and halts "partially computable function" undefined on some inputs

Universal Turing Machines Universal Turing Machines Since a TM can compute anything that is computable, there are Turing Machines that can preform computations on other Turing Machines. A Universal Turing Machine executes operations on another Turing Machine. the UTM is like hardware the TM that is being operated on is like software

Universal Turing Machines Universal Turing Machines To input a TM (M) into a UTM (U), M's tape, states, and transitions must be encoded. that encoding format is similar to the method we used to represent transitions in PDAs Implementation of U is usually done as a 3-tape TM. tape 1 - M's tape tape 2 - M's transitions tape 3 - current state of M

The Halting Problem The Halting Problem Given a TM, will it halt when run on some particular input? There is no generalized algorithm that can tell us ahead of time whether or not an algorithm will halt. The best we can do is run the program and observe whether it halts or loops infinitely. So For programs in general, halting is undecidable.

Halting Problem Halting Problem Given a TM (M) and input (w), we do not know if {M,w} is decidable. o Will {M,w} halt if w is accepted or if w is rejected? o We don't know until we run it. Proof: Assume {M,w} is decidable. Create a function H that accepts M and w and outputs either "halts" or "does not halt". o H is a "decider" and thus must always halt. o Spoiler Alert: H cannot exist.

Proof continued: Create another TM (D) that calls H as a subroutine. But, o if H outputs "halts" have D loop forever o if H outputs "does not halt" have D halt. Now, call D with D as its input. So D must decide (by halting) if D halts or does not halt. So, if D determines D(D) halts, D runs forever because it is looping forever it never stops to give us an answer if D determines D(D) does not halt, then it halts but it can't halt because we forced it to loop forever.

Halting Problem Halting Problem Conclusion: There cannot exist a function (H) that can examine a TM (M) and input (w) and determine by examination that M halts on w. H(M,w) does not exist. Thus, we must run M on w to determine if it halts.

Vocabulary Note Vocabulary Note The "Turing Test" has nothing to do with Turing Machines The "Turing Test" is an AI problem. Can we create a machine that is impossible to distinguish from a human?

Next Class Next Class P vs. NP Does there exist an efficient algorithm to solve my problem? if your problem is sorting, then yes if your problem is routing delivery trucks, then we don't know