Up: Notes on the ``Impenetrable
The relevant theorems are:
- There is no TM M such that given any TM and string u,
M can determine whether accepts u.
- There exists a certain fixed TM such that
no TM M can determine, given an input string u, whether
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)!
Thu Apr 25 14:15:16 EDT 1996