What's going on?
I'm still hung-up on the idea that the angle-bracket encoding scheme is important.
Pointing out the error in the proof below would make me happy.
3/12/06: Jim found a flaw in the argument yesterday, but not one that got to the
heart of the problem. I've patched-up the hole to give a weaker theorem, but one that still directly contradicts Sipser (and the rest of the world).
Theorem(?!)
Uncountably many languages are Turing-recognizable.
Proof
Let
be the set of all infinite languages with infinite complement.
is uncountable [exercise!].
Let L be a language in
, T be the set of all Turing machines and W be the set of all words. The three sets L, T and W are countable, as is
T \times W.
Define the set A as follows:
A = {(M,w):M accepts w}
A is a subset of T×W
and hence is also countable. In particular, we can find a
bijection f from A to L.
Define the angle-bracket encoding by setting ⟨M,w⟩
to be f((M,w))
. Complete the encoding scheme by encoding objects not of the form (M,w) as elements of the complement of L (this is possible as the complement of L is infinte).
Now, ATM = {⟨M,w⟩:M accepts w} = L
and
ATM
is Turing-recognizable. Therefore our language L is Turing-recognizable.
Hence all languages in the uncountable set {\mathcal L}
are Turing-recognizable.
My thoughts
Here's my suggested way around the problem. All of our theorems should actually begin "For any fixed angle-bracket encoding scheme..." This would mean that the trick in the above proof could not be played.
However, this would mean that choosing a different encoding scheme would mean that the set of Turing-recognizable languages would change. This seems to be a problem - shouldn't this set be independent of encoding scheme?
hmmmmm
-Matt
An Answer
The proof of the fact that
ATM
is recognizable
requires that we construct a universal turing machine
U
which
takes
⟨M,w⟩
and simulates
M
on
w
. To do this,
U
needs to be able to implement
f − 1
. For an arbitrary language
this is not possible:
f
encodes an infinite number of arbitrary relations, and Turing
machines are finite beasts. (I admit that the last line of reasoning
isn't a formal proof, but am confident that it could be tightened up.)
Intutitively, when I say that a language
is inherently Turing recognizable, I want to mean that there's
enough of a pattern in there for some specific machine
to describe. The mapping
f
of machines
and words to strings that Matt posits
above, on the other hand, is "magic" : we can show
that such a mapping exists, but we cannot explicitly
describe or construct it. In particular, I can't imagine
how a Turing machine would take one of the apparently
random strings of an arbitrary
and produce the appropriate Turing machine simulation.
When Sipser first sets up the angle bracket notation
(pg 145, section 3.3, "The Definition of an Algorithm"
in the 1st edition) he says "Strings can easily represent
polynomials, graphs, grammars, automata, and any combination
of these objects. A Turing machine may be programmed to
decode the representation so that it can be interpreted
in the way we intend."
So the angle bracket scheme is important, and does need
to have restrictions, which Sipser implies but doesn't
specify in detail. But I think it's clear that the
angle bracket is part of the whole notion of a universal
turing machine, and that depends the mapping f
being something that a Turing machine can simulate.
- Jim on March 12
