1
$\begingroup$

What is the point of non-binary printed letters on a turing machine? I understand that these need to be omitted to get a computable number, but why are they used in the first place?

Improve this question
$\endgroup$
7
  • $\begingroup$ You mean, why a TM could have an alphabet other than $\{0, 1\}$. $\endgroup$
    – Karolis Juodelė
    Commented Jan 23, 2014 at 17:17
  • 1
    $\begingroup$ Because TMs are a formalism to think about computation, and sometimes having more symbols than $0$ and $1$ makes thinking about problems easier. They are not a blueprint for hardware. $\endgroup$
    – G. Bach
    Commented Jan 23, 2014 at 17:21
  • $\begingroup$ @G.Bach Together with an example, this would make a fine answer, I think. $\endgroup$
    – Raphael
    Commented Jan 23, 2014 at 18:10
  • 1
    $\begingroup$ Why even give a TM as an example? It seems sufficient to point out that the "point" of having more than two letters in the English alphabet is more or less the same as the "point" of allowing more than two letters in a TM's tape alphabet. The answer could range from "it's convenient" to "that's just how it ended up", with everything in between being equally as valid. Really, the question should be why computer hardware relies on binary representations, not vice versa. Another interesting question might discuss unary alphabets. The answer to this question, as asked, is "because!" $\endgroup$
    – Patrick87
    Commented Jan 23, 2014 at 19:09
  • 2
    $\begingroup$ By the way, for most interpretations of I understand that these need to be omitted to get a computable number I can imagine, your understanding is wrong. $\endgroup$
    – Patrick87
    Commented Jan 23, 2014 at 19:11

2 Answers 2

Reset to default
4
$\begingroup$

Turing Machines are an abstract model of computation, their purpose is to define in a mathematical way what problems are theoretically computable and which are not.

It is true that a binary alphabet is enough to reach the full expressive power of Turing Machines. However, when playing with them "in practice" to prove theorems and to communicate these proofs, it can be more convenient to use more symbols, instead of encoding everything in binary. We could always go back to binary if it's absolutely needed.

An extreme example of the same sort would be "why are we still using 26 characters to write texts, now that we know that two are enough? It would save time when learning the alphabet!".

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ You are also much better off with a blank symbol. Otherwise everything has to be coded in unary. $\endgroup$
    – Yuval Filmus
    Commented Jan 23, 2014 at 20:39
1
$\begingroup$

Turing machines with many symbols can be simulated by Turing machine with two symbols. The idea is to consider groups of bits as representing one symbol, in the same way that files are stored in the computer byte by byte. In that sense, having more symbols gives you no more power than a single symbol. Moreover, the simulation has "constant throughput" — it only slows down the machine by some constant.

There is a fine point regarding input encodings. Usually inputs are blank-separated or blank-terminated. If you have only two symbols and are using this convention, then everything has to be encoded in unary — $1^n0$ for the number $n$. This has a strong effect on input length and so on running times (making them appear much faster), so either you use an unconventional encoding (say encode "characters" in groups of two symbols), or you need to have at least three symbols (including the blank symbol).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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