next up previous
Next: Explanation Up: Notes on the ``Impenetrable Previous: Turing-Acceptability

The Relevant Theorems

The relevant theorems are:

  1. There is no TM M such that given any TM and string u, M can determine whether accepts u.
  2. There exists a certain fixed TM such that no TM M can determine, given an input string u, whether accepts w.

Note that these two theorem are not interderivable. In the ``Florida story" involving Welty and Shapiro, I idiotically tried to get the second of these from the first --- and then realized that was impossible, something I should have remembered from elementary computability theory (see below)!

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