On Mon, 7 Aug 1995, Futplex wrote:
No crypto/privacy relevance, delete or flame now....
Nathan writes:
This is why the "not a Turing machine" assertion that the "Professor" is important. We know that Turing machine is undecidable, so if we want to limit behavior, we can't have one. BUT---we don't know that being a Turing machine is equivalent to having "unpredictable" behavior. Furthermore, a "proof" of the "not a Turing machine" assertion is going to have to be done by--you guessed it--a computer. And this computer is running a program which definitely IS a Turing machine, if it is capable of "proving" that other (suitably non-trivial) programs are not Turing machines.
I think this is a bit misguided. The Turing machine (TM) is an extremely general abstract model of computation. The gargantuan hunk of code that runs the Space Shuttle can be viewed as a Turing machine, as can a "Hello world" program written in Visual BASIC. So, there's not really a question about whether or not we're talking about Turing machines (unless perhaps you want to discuss quantum theorem provers and QTMs :)
If a statement is vacuous, it needs refining :-). If I were to state that "Program X is not a Turing Machine", I would be stating that program X does not model all Turing machines throught its input. It is the ability of some Turing machines to model all Turing machines through their input that makes them undecidable.
Now, Rice's Theorem says that all non-trivial properties of TMs are undecidable. If I pick a "non-trivial" property, I can't conceivably build a TM ("write a program", if you like) that, upon input of the specification of an arbitrary TM, can tell whether or not that TM exhibits the property I picked. This does not mean that I can't decide whether some particular TMs have that property or not -- I can. I just can't write down a procedure that handles the general case.
The problem here is that it is the interesting cases with which we are concerned. If someone wants to write a computer program to "verify" my proof of the RSA algorithm, fine. But I have to be convinced that there program does what they claim before I care. And since their program takes mathematical theorems as input, it is already demonstrating near-Turing ( :-P) behavior.
Also, this theorem clearly hinges on the meaning of "trivial". From what I've seen, a very strict interpretation is largely appropriate; nearly everything except the least exciting of trivial low-level properties of TMs seems to come out to be "non-trivial" in this regard. The proof of the theorem is more precise about this, naturally, but I've found this useful as a working colloquial definition.
I'll buy that.
-Futplex
Nathan