Table of Contents
III. Theory and Mathematical Background – 40%
B. Automata and language theory
3. Decidability
a. Definition: A machine cannot solve some problems. If the machine can solve it, then we say it is decidable on that machine.
b. Some problems cannot be solved by an algorithm. For example, it is impossible to create a program that will always know whether all programs will always halt on all inputs. On the other hand, some problems (languages) are decidable.
c. All CFL are decidable. And some languages used on Turing machines are decidable.
d. A language is decidable if and only if it and its complement are recursively enumerable (Turing-recognizable).
e. Some important undecidable problems
i. Accepting Turing machine: We cannot calculate if a certain Turing machine will accept a given input.
ii. The halting problem: It is impossible to decide if a given Turing machine will halt on a certain input.
iii. Empty Turing machines: It is impossible to decide if a certain Turing machine will accept any input at all.
iv. DFA equivalent: It is impossible to compute if a given Turing machine has a DFA equivalent.
v. Equivalent Turing machines: We cannot calculate if two Turing machines recognize equivalent languages.
