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!

• What is $R$ In your question?
– mrp
Commented Jan 1, 2017 at 10:50
• @mrp, I thought it is trivial - the set of all decidable languages. Commented Jan 1, 2017 at 10:51
• @Galc127 Not every text uses the same notation. Commented Jan 5, 2017 at 16:08

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.

• Great answer! thanks a lot (+1) Commented Jan 9, 2017 at 9:24

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.

• It is not clear to me why $\delta<1000$ and don't I need to look at the encoding of turing machine? Commented Jan 4, 2017 at 19:04
• $a,b,c,d,e,f,g$ here are not all numbers, so they aren't all smaller than 1,000. In fact, there are a lot more than 1000 possibilities for $\delta$, see my answer. Commented Jan 6, 2017 at 7:18