1

There are many questions like this but I couldn't find what I was looking for in them. I already know that the set of all Turing machines is countably infinite but I couldn't find a proof of this, also it doesn't make sense to me intuitively. So, my question goes like this: In the book it says that we can encode Turing machines as strings and somehow this makes it countable. I understand that this statement is true if the alphabet of those strings is finite or countably infinite(I am not really sure about this one). what happens if the alphabet is uncountably infinite? or why can't it be so?

DavidDvali
  • 11
  • 2
    A turing machine has finite many states and finite many symbols. Hence there are only countable many turing machines. – Peter Jul 05 '21 at 16:53
  • Machine has an alphabet for input and also for the tape. Can't these alphabets be uncountably infinite? – DavidDvali Jul 05 '21 at 16:56
  • 1
    The number of symbols is not bounded, but always finite. So no, the alphabet cannot be uncountable, not even infinite. – Peter Jul 05 '21 at 16:57
  • I didn't mean an alphabet for one specific machine. For example if we have a Turing machine that recognizes the language that consists of words: a, aa, aaa ... and so on. – DavidDvali Jul 05 '21 at 17:05
  • then we can have the same type of machine for all the other symbols – DavidDvali Jul 05 '21 at 17:06
  • 2
    Let $T(m,n)$ be the set of all machines which have exactly $m$ states and whose alphabet has exactly $n$ symbols. Each $T(m,n)$ is a finite set because there are only $mn^{2mn}$ possible transition functions. Every Turing machine is in one of the $T(m,n)$ sets. The set of Turing machines is therefore contained in the union of the $T(m,n)$. This is a countable union of finite sets, and so is at most countable. Therefore the set of all Turing machines is contained in a countable set and is countable. – MJD Jul 05 '21 at 17:16
  • 2
    Same proof in different language: a Turing machine is a computer program. A computer program is a string, which is a finite sequence of characters. For each number $n$, there is only a finite number of programs of length $n$. So the total number of programs is a countable union of finite sets, and the set of Turing machines is a subset of this. – MJD Jul 05 '21 at 17:19
  • I think it makes some sense :D , thank you. – DavidDvali Jul 05 '21 at 17:40
  • A concrete way to find a bijection to the natural numbers is the method of Gödelization. This is a very general concept, see also maybe https://cs.stackexchange.com/questions/6883/g%C3%B6delization-in-turing-machine. – k-rational Jul 05 '21 at 19:29
  • With an uncountable language you can write uncountably many Turing machines, but each program will be written uncountably many times (using different symbols each time), and there will be only countably many distinct machines. – Sam Jul 08 '21 at 03:57

0 Answers0