Claim about Turing machines

Question

I am trying to tackle the following question:

A researcher claims that he has detected for every alphabet $\Sigma$ a finite set of important Turing Machines that can decide any decidable language over $\Sigma$.

1. Prove that he is wrong.
2. Let A be the set of languages decided by Turing Machines that have at most $1000$ states and at most $1000$ type symbols (in addition to the symbols of $\Sigma$ and $\sqcup$). Prove that $A\ne R$.

Part $(1)$ is pretty easy - any Turing Machine decide only one language. Let $\sigma\in\Sigma$, then the set of languages $\{\sigma^i\mid i\in\Bbb{n}\}$ is infinite, thus there is no finite set of Turing Machines that decide any decidable language over $\Sigma$.

In part $(2)$ I understand that I need to show that the set of "Turing Machines that have at most $1000$ states and at most $1000$ type symbols" is finite, hence according to part $(1)$ there are decidable languages over $\Sigma$ that can't be decide by this set, i.e there are languages in $R$ which are not in $A$, thus $A\ne R$. Unfortunately, I could not manage to show it.

Any hint/help will be appreciated, thanks!

Answer 1

I do not understand how to show (2), but I can help you with this part of your question:

I understand that I need to show that the set of "Turing Machines that have at most 1000 states and at most 1000 type symbols (in addition to the symbols of $\Sigma$ and $\sqcup$)" is finite

Every Turing machine can be described with a tuple, as described here:

• $Q$, a finite, nonempty set of states. There are at most 1000 possibilities for $Q$ (one for every amount of states between one and 1000).
• $\Gamma$ is a finite, non-empty set of tape alphabet symbols: There are at most 1001 possibilities for $\Gamma$, namely one for every amount of symbols in addition to the symbols of $\Sigma$ and $\sqcup$ between zero and 1000.
• The blank symbol $b$ is here simply $\sqcup$.
• $\Sigma$ is the set of input symbols, which is given here.
• $\delta : (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is the partition function. There are at most $|Q \setminus F| |\Gamma| \leq 1000 \cdot (1001+|\Sigma|)$ elements in the domain and $|Q|\cdot |\Gamma|\cdot 2 \leq 2000 \cdot (1001+|\Sigma|)$ elements in the codomain, so $$(1000 \cdot (1001+|\Sigma|))^{2000 \cdot (1001+|\Sigma|)}$$ possibilities in total. Because $|\Sigma|$ is a finite constant, this is finite.
• $q_0 \in Q$ is the initial state. At most 1000 possibilities.
• $F \subseteq Q$ are the accepting states. There are at most $2^{1000}$ possibilities.

Now, the amount of possibilities is the product of five finite numbers and hence finite.

Answer 2

First, the decidable languages of $\sum$ are the recursive subsets of all words in $\sum$. The researcher claims he found a finite number of Turing machines that output all the recursive subsets. It would be enough to show that for total computable functions $f(x):f(x)=1$ if $x \in L; f(x)=0$ if $x \notin L$ and $g(x):g(x)=1$ if $x \in L';g(x)=0$ if $x \notin L'$ and $L≠L'$, then $f \ne g$. This is pretty simple:

Assume $f=g$ (to show contradiction). Let a be a word in $L$ that is not in $L'$ (or the other way around if $L$ is a proper subset of $L'$). Then $f(a)=1$ and $g(a)=0$. Therefore $f\ne g$, a contradiction. The assumption is false: therefore, $f\ne g$.

That is a sketched proof that a turing machine decides only $1$ language, or it decides $0$ languages.

To show that there are finite Turing Machines (TMs) with $1000$ states and $1000$ symbols:

Every Turing machine is defined by a $7$-tuple, as explained on wikipedia here. How many $7$-tuples $(a,b,c,d,e,f,g)$ are there if $a,b,c,d,e,f,g<1000$? The answer is $1000^7$. Not all of those are TMs, but all TMs of $<1000$ states and $<1000$ symbols are included. Therefore there are less than $1000^7$ such TMs.