Week 8 and 9 - Decidability Flashcards
A decision problem is said to be decidable when…
There is some program, such that when given an argument it always returns true or false. (i.e the program will always halt)
Church’s thesis
any decision problem on words that can be solved by an algorithm can be solved by a Turing machine.
A decision problem is said to be semi-decidable
There is some program, such that when given an argument it returns true otherwise it runs forever.
Any property that is decidable must also be…
semi-decidable
If a property is semi-decidable and the negation of the property is also semi-decidable then
the property is decidable
What is the halting problem?
That it is undecidable to distinguish if a nullary program (a program with no arguments) halts or hangs.
What does it mean to reduce problem A to problem B?
We take the input for A, and convert it into a suitable input for the algorithm that solves B. Then run the algorithm on that converted input and convert the output into a suitable output for problem A.
If we have reduced problem A to problem B then if B is decidable, then…
A is decidable
If we have reduced problem A to problem B then if A is undecidable, then…
B is undecidable
How can we test if the property of a program is decidable?
Reduce the property to the halting problem. If the halting problem is decidable then the property of the program is too.
What is a semantic property of a program?
Properties that are visible to an external user
According to Rice’s theorem, every semantic property of a program is…
Undecidable (except for 2)
Rice’s theorem
Any semantic property of code that holds is some case and fails to hold in some case is undecidable.
A semantic property that never holds is…
decidable
A semantic property that always holds is…
decidable
