18
$\begingroup$

I am starting read a book about Computational Complexity and Turing Machines. Here is quote:

An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical encoding.

This assertion is provided as a simple fact, but I can't understand it.

For example, if I have an algorithm which takes $x$ as input and computes $(x+1)^2$ or:

int function (int x){
   x = x + 1; 
   return x**2; 
}

How that can this be represented as string using alphabet $\{0, 1\}^*$?

Improve this question
$\endgroup$
9
  • 38
    $\begingroup$ You do not know the absolute minimum required knowledge to understand how text is encoded. Today is a great day to learn! joelonsoftware.com/2003/10/08/… $\endgroup$
    – Eric Lippert
    Apr 6, 2018 at 1:40
  • 1
    $\begingroup$ I think OP might be coming at this from a different point of view based on an ambiguity in the quoted text. I guess OP means 'how can the whole machine and algorithm be built as a bit string,' not the input to the Turing machine itself. The quoted text implies that the whole algorithm can be self executed, but a utf encoded bit of c language says nothing about how a machine would actually act on that string. $\endgroup$
    – Sentinel
    Apr 6, 2018 at 8:20
  • 3
    $\begingroup$ ...I think everyone here is misunderstanding the source and taking the joke too far, at the expense of Roma's inexperience. Most of these comments and answers are talking about encoding the text for arbitrary transmission, while the quote is talking about encoding the algorithm for consumption by a turing machine. The (currently) accepted answer at least touches on it in the second sentence. $\endgroup$
    – Izkata
    Apr 6, 2018 at 12:37
  • 2
    $\begingroup$ @Izkata I’m not sure if you’re aware that, due to universality, these two statements are equivalent. $\endgroup$
    – Konrad Rudolph
    Apr 6, 2018 at 14:04
  • 15
    $\begingroup$ The funny thing is that in order for me to be able to read your coded algorithm it necessarily had to be turned into a sequence of bits as soon as you typed it. It never was represented differently -- all the way from your keyboard to my monitor. It had a non-binary representation only in our minds; and on the physiological level, when you look at synapses, even that is debatable. $\endgroup$
    – Peter - Reinstate Monica
    Apr 6, 2018 at 16:23

8 Answers 8

Reset to default
45
$\begingroup$

The most naive and simple answer to your question is that the code provided (and compiled machine code) are in-fact represented as syntactic strings of {0,1}*. Additionally, since you are talking about turing machines, the programs they run are a linear list of operations/instructions, there is no reason these cannot be represented as bits/bytes.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How exactly do you represent Turing machine as a list of instructions? The usual definition is something like this. $\endgroup$
    – svick
    Apr 8, 2018 at 21:28
  • $\begingroup$ @svick As mentioned in my answer below, you use a universal TM, which takes the description of a TM as input (encoded in a suitable fashion) $\endgroup$
    – dseuss
    Apr 9, 2018 at 3:35
  • $\begingroup$ @svick A programming language with simple instructions to move a pointer accross a tape? I believe an example of such could be the esoteric programming language Brainfuck. Example code $\endgroup$
    – LukStorms
    Apr 10, 2018 at 11:26
  • $\begingroup$ @LukStorms I don't think you can call that a "Turing machine" anymore. $\endgroup$
    – svick
    Apr 10, 2018 at 13:38
52
$\begingroup$

You already have a representation of that function as text. Convert each character to a one-byte value using the ASCII encoding. Then the result is a sequence of bytes, i.e., a sequence of bits, i.e., a string over the alphabet $\{0,1\}^*$. That's one example encoding.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Exactly. And as I said above, it happened while Roma wrote it. Even the glyphs I see on my monitor are b&w pixels, i.e. binary information, sent over a binary data connection from a binary memory connected to a binary network through binary controllers. Is it possible to represent every algorithm as a bit string? More than that: it's unavoidable unless you limit yourself to analog media and face-to-face communication. $\endgroup$
    – Peter - Reinstate Monica
    Apr 6, 2018 at 16:30
  • $\begingroup$ @PeterA.Schneider Using analog media or face-to-face does not necessarily imply that there is no embedded discrete encoding. Using a natural language is not far away from using a discrete encoding, isn't it? $\endgroup$
    – Jean-Baptiste Yunès
    Apr 7, 2018 at 6:57
34
$\begingroup$

I can't resist...

⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂
⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀
⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀
⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀
⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆
⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

⢱⠀
⢸⠁
⠊

(The dots above represent ones, the blanks zeroes).

Improve this answer
$\endgroup$
7
13
$\begingroup$

Your computer stores everything as sequences of 0 and 1, including the question you typed to ask how it does it. For instance, each letter and symbol is represented by 8-bits (I am talking about how things used to be, nowadays it's 16-bits, and more complicated). You can see them here. Well, they are not showing the bits, but rather the hexadecimal and octal codes. Do you know how to convert a number to its digital representation?

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ It's 16 bytes only on Windows and in some libraries like Qt or ICU, which use UTF-16. And not even all letters take a single code unit in general, even in UTF-32, so they may be longer. So I think it's better to stick to ASCII in this discussion, bringing Unicode here will lead to quite a complication. $\endgroup$
    – Ruslan
    Apr 6, 2018 at 6:32
8
$\begingroup$

The fundamental hypothesis behind this concept is the Church-Turing thesis. It may be hard to see that any algorithm can be represented as a string of bits, because the term "algorithm" may be thought of in very informal terms. In the Church-Turing thesis, they use a very rigorously defined concept of what an algorithm is (and even then there have been a few questions about words). However, their terminology has gotten so much sway that it is sometimes argued that these definitions for words like "algorithm" are so effective that we simply accept them as the definition.

Church-Turing states that every algorithm can be implemented as a computation on a Turing Machine. Given that the description of a Turing Machine is a finite set of values, it is trivial to see how to map this description into a sequence of numbers, and then into a sequence of 0's and 1s.

As the other answers have mentioned, it's trivial to represent your example algorithm by using ASCII encoding or other encodings.

I think the reason why your book gives this statement as a fact stems from the fact that many simply use the Church-Turing thesis as the basis for their definition of an algorithm. If you use such a definition, it is as obvious of a fact as is "5 is a number" because you basically defined it as such.

Improve this answer
$\endgroup$
8
  • 9
    $\begingroup$ The Church-Turing thesis is not a theorem and it doesn't involve any definition for the concept of algorithm, which is an informal one. I also don't see the need to invoke the Church-Turing thesis for this. The "deep" reason why some objects can be represented as finite strings and some cannot is that some sets are countable and some aren't. $\endgroup$
    – quicksort
    Apr 5, 2018 at 20:06
  • $\begingroup$ I'm seeing "an algorithm can be encoded as a string if we specify an injection between the components of the machine specification and the set of strings in a language." OP does this in his example, taking the machine represented by "\$(x+1)^2\$" and re-representing it as a string in the language of well-formed C (or BCPL, C++, et al.) functions. $\endgroup$
    – Eric Towers
    Apr 6, 2018 at 0:02
  • 1
    $\begingroup$ @EricTowers Which does require the Church-Turing thesis. Otherwise one cannot be certain that there exists a machine specification of an algorithm for all algorithms. $\endgroup$
    – Cort Ammon
    Apr 6, 2018 at 0:16
  • 1
    $\begingroup$ I assert that an "algorithm [that] requires an uncountably infinite number of symbols to express" cannot be expressed. Such an expression must use uncountably many symbols, otherwise, it can be expressed in a smaller sublanguage. Further, any (non-silly) expression over an infinite alphabet has an infinite amount of entropy in almost all of its symbols, so defies expression (i.e., cannot actually communicate to a recipient). All finitary logics refuse to operate on such infinite strings and I am not aware of an infinitary logic that will permit working on uncountable strings. $\endgroup$
    – Eric Towers
    Apr 6, 2018 at 1:34
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W. ♦
    Apr 6, 2018 at 16:45
4
$\begingroup$

This statement is based on the existence of universal TMs. These are basically programmable TMs that can simulate any other TM with at most poly overhead. Therefore, your program is simply part of the input encoded as zeros and ones.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @Discretelizard, I don't follow you. Any algorithm is expressible as an input to a universal TM. Languages can be computable or uncomputable; I'm not familiar with any standard notion of computability for algorithms, so I'm not sure what you're getting at. What would it mean to have an uncomputable algorithm? Perhaps you're thinking of algorithms that don't necessarily terminate? But a universal TM can still run such algorithms. $\endgroup$
    – D.W. ♦
    Apr 6, 2018 at 16:42
  • $\begingroup$ @Discretelizard I don't follow you, either. Being runnable on a Turing machine is essentially the definition of an algorithm. I suppose you could talk about an "algorithm" for, say, a Turing machine with an oracle for the halting problem but, normally, "algorithm" means "thing you can do on a Turing machine." $\endgroup$
    – David Richerby
    Apr 6, 2018 at 17:14
  • $\begingroup$ @DavidRicherby True, the actual definition of algorithm is more strict, I suppose. But this question regards is about why we impose a much more lenient restriction and saying that there is an even stronger restriction isn't very instructive, in my opinion. $\endgroup$
    – Discrete lizard ♦
    Apr 6, 2018 at 17:25
4
$\begingroup$

Well, let's talk about algorithms that cannot be represented as a finite bit-string for any kind of encoding.

Let me type out such an algorithm for you... Ah, but if I do that, I can represent that algorithm with the encoding of my typed text.

How about representing my algorithm using some 'analog means', say by the position of a few coins on my desk. Although the position of those coins can be modeled by some real numbers (which could in some encodings be impossible to finitely represent), this entire description can again be considered an representation of my algorithm and can be encoded to a bit-string again!

I hope that these examples make it clear that if some algorithm cannot be represented by a finite bit-string we have no means of describing this algorithm at all!

So, why would we consider the existence of something we cannot speak of? Perhaps interesting for philosophy, but not for science. Hence, we define the notion of algorithm such that it can be represented by a bit-string, as then we at least know that we are able to talk about all algorithms.

Although the above answer the question asked, I think the confusion about the example given is mostly due to the fact that a representation only needs to uniquely represent some algorithm. The manner of representation doesn't need to involve the actual computations invoked by the algorithm! This is very useful, as it means we can also represent uncomputable algorithms!

Improve this answer
$\endgroup$
7
  • $\begingroup$ " if some algorithm cannot be represented by a finite bit-string we have no means of describing this algorithm at all! " -- That's not quite true. One might say: "For every real number $r$, consider algorithm $A_r$ as ...". Then most of those algorithms can't be written down but, somehow, we still have expressed them all. $\endgroup$
    – Raphael ♦
    Apr 6, 2018 at 15:45
  • 1
    $\begingroup$ $A_r$ is clearly a representation of that algorithm and for all algorithm you wish to represent, simple pick a symbol to represent a value from $\mathbb{R}$. So, the algorithm can be represented. Note that this is only a one-way implication, the other way around need not hold. $\endgroup$
    – Discrete lizard ♦
    Apr 6, 2018 at 16:10
  • 1
    $\begingroup$ Yes! Lovely! Wittgenstein! "Wovon man nicht sprechen kann, darüber muss man schweigen." $\endgroup$
    – Peter - Reinstate Monica
    Apr 6, 2018 at 16:34
  • $\begingroup$ @Discretelizard You'll run out of symbols for $r$ quickly. $\endgroup$
    – Raphael ♦
    Apr 6, 2018 at 23:45
  • $\begingroup$ @Raphael Yes, and? It should be no surprise that writing down an uncountable number of algorithms isn't possible. And again, you claim that you "express" some algorithms that cannot be written down. I don't understand what you mean by "express", but it seems to at least imply representation. As my claim starts with the assumption that an algorithm is not being represented, I fail to see how this contradicts my claim. $\endgroup$
    – Discrete lizard ♦
    Apr 7, 2018 at 8:13
2
$\begingroup$

Another way to see this is through information theory. All encodings of meaningful/useful information/questions can be made into binary 'sequences'.

Much of the field goes to the question, "what is the way to ask the least average number of questions to communicate a meaningful piece of information?" In practice, this is the same as "what is the optimal approach to asking the least number of yes/no questions to understand what was communicated or said?"

Improve this answer
$\endgroup$

Your Answer

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

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