Equivalence of UTM

78 Views Asked by At

What is the cardinality of the set of languages accepted by an Universal Turing Machine?

Is it $\aleph_0$ or $\aleph_1$?

What is the cardinality of the set of languages accepted by a Turing Machine?

Are any two Turing machines equivalent?

Are any two Universal Turing machines equivalent (what does it mean to be equivalent)?

1

There are 1 best solutions below

8
On

It's $\aleph_0$ since the cardinality of the set of all Turing-machines is $\aleph_0$ and with each Turing-machine we can associate exactly one language that it accepts.

Now, it is perfectly possible for two different Turing-machines to accept the same language, in which case we can call them equivalent. But what is true is that there are at most as many languages as there are Turing-machines.

To show that the set of languages is actually $\aleph_0$, you would therefore have to do a bit more work, but you can easily show that for any $n$, there is a Turing-machine that accepts the language $\alpha^n$ with $\alpha$ a symbol. So, you have as many languages that can be accepted by Turing-machines as there are natural numbers, so the set of language is at least $\aleph_0$, and since we already established that it is at most $\aleph_0$, it is $\aleph_0$.

As far as Universal Turing machines go:

There are multiple reasonable ways to represent Turing-machines and their input on a tape, so you could have many different Universal Turing-machines that would not be considered equivalent since the 'language' they accept would differ according to the convention used. If you fix the convention, however, then while there can still be multiple Universal Turing-machines, their overall input-output behavior will be the same, and hence they accept the same language, and are equivalent.