3
$\begingroup$

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!

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

2 Answers 2

1
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Great answer! thanks a lot (+1) $\endgroup$
    – Galc127
    Commented Jan 9, 2017 at 9:24
1
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Jan 4, 2017 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
    Commented Jan 6, 2017 at 7:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .