14+15 Flashcards
What is the language Halt?
The language halt takes in a machine and a word and accepts if the machine halts on the word, it doesn’t accept if the machine never halts.
How can we prove the language halt is not recursive?
Imagine we have a TM, that halts on all input and accepts the language HALT. Then produce an anti-halting machine, this will run a machine and word by first running halt on it. If it halts and rejects then AH halts, if it halts and accepts AH loops infinitely.
Now produce a machine with takes a machine as input and doubles it(feeding the machine to itself), it then feeds this to AH. If we run our doubling machine on itself it will loop forever if it would halt or halt if it would loop forever. This is a contradiction, our only assumption was that Halt was recursive. As such Halt is recursively enumerable, but not recursive.
What is turing reducibility?
If we have two languages L and K, we say the L is ruting reducible to K, writing L
TR −→ K if a TM exists which always halts and on input w leaves some other word on the tape so that w is in L if and only if the new word is in K.
If L is undecidable then K must also be undecidable. We can show a language is undecidable by turing reducing HALT to it.
What is the heirarchy of languages?
Finite languages > regular languages > context free languages > recursive languages > recursively enumerable languages.
