Nitpick: strictly speaking, a computer is not a universal Turing machine because it has a finite amount of memory and is therefore a finite state machine (and in particular can therefore only run finitely many programs). When we say that computers are universal Turing machines we are talking about an idealized version of a computer that acquires more memory as necessary.
Regarding the problem of determining whether a Turing machine is universal, this is undecidable by Rice’s theorem, which asserts more generally that any nontrivial property (in the sense that at least one Turing machine has it and at least one Turing machine doesn’t have it) of Turing machines is undecidable. The best you can do is an algorithm which returns “is a UTM” on some Turing machines, returns “is not a UTM” on others, or doesn’t halt (or outputs “unknown”). For example, it might search through proofs that a given Turing machine is or is not universal (possibly up to some upper bound).
Yes, that was sort of the point—you can’t make a function for “is a Turing machine” that works in all cases, and you can’t make a “is a non-person” function that works in all case either. Further, the set of things you can rule out with 100% certainty is to small to be useful.
Don’t see how that relates to my suggestion of a probabilistic answer though. Has anyone proven that you can’t make a statistically valid statement about the “Is a Turing machine” question?
Nitpick: strictly speaking, a computer is not a universal Turing machine because it has a finite amount of memory and is therefore a finite state machine (and in particular can therefore only run finitely many programs). When we say that computers are universal Turing machines we are talking about an idealized version of a computer that acquires more memory as necessary.
Regarding the problem of determining whether a Turing machine is universal, this is undecidable by Rice’s theorem, which asserts more generally that any nontrivial property (in the sense that at least one Turing machine has it and at least one Turing machine doesn’t have it) of Turing machines is undecidable. The best you can do is an algorithm which returns “is a UTM” on some Turing machines, returns “is not a UTM” on others, or doesn’t halt (or outputs “unknown”). For example, it might search through proofs that a given Turing machine is or is not universal (possibly up to some upper bound).
Yes, that was sort of the point—you can’t make a function for “is a Turing machine” that works in all cases, and you can’t make a “is a non-person” function that works in all case either. Further, the set of things you can rule out with 100% certainty is to small to be useful.
Don’t see how that relates to my suggestion of a probabilistic answer though. Has anyone proven that you can’t make a statistically valid statement about the “Is a Turing machine” question?