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!

  • 1
    $\begingroup$ What is $R$ In your question? $\endgroup$ – mrp Jan 1 '17 at 10:50
  • $\begingroup$ @mrp, I thought it is trivial - the set of all decidable languages. $\endgroup$ – Galc127 Jan 1 '17 at 10:51
  • $\begingroup$ @Galc127 Not every text uses the same notation. $\endgroup$ – Noah Schweber Jan 5 '17 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.

  • $\begingroup$ Great answer! thanks a lot (+1) $\endgroup$ – Galc127 Jan 9 '17 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.

  • $\begingroup$ It is not clear to me why $\delta<1000$ and don't I need to look at the encoding of turing machine? $\endgroup$ – Galc127 Jan 4 '17 at 19:04
  • 1
    $\begingroup$ $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. $\endgroup$ – wythagoras Jan 6 '17 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.