next up previous
Next: About this document Up: Notes on the ``Impenetrable Previous: The Relevant Theorems


Let denote the encoding of TM M, and let denote the encoding of string u. It is known that the language

is not Turing-decidable. From this, however, is doesn't follow that if we index the machine-input strings to a paticular machine M the resulting set

is not Turing-decidable. However, we do know that is not Turing-decidable, where is a TM accepting . Our second theorem above follows from this fact. (Make sure you can verify it.)

Selmer Bringsjord
Thu Apr 25 14:15:16 EDT 1996