Claim about Turing machines 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$.

*

*Prove that he is wrong.

*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!
 A: 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.
A: 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.
