-2
$\begingroup$

enter image description here

enter image description here

I am unable to understand why do we need to encode turing machine at all? I heard that we are trying to build a programmeable turing machine but can't relate how encoding it will make this programmeable.

Please share some insights. PS I have seen different encoding in different slides, are all encodings fine?

https://slideplayer.com/slide/6019689/

here is different encodings.

here is again different encodings-:

https://www.cs.usfca.edu/~galles/cs411/lecture/lecture15.pdf

$\endgroup$
8
  • 1
    $\begingroup$ How would you emulate the workings of a Turing machine without describing the Turing machine? An "encoding" is just a way of unambiguously describing the TM. $\endgroup$
    – rici
    Nov 17 '21 at 6:42
  • 1
    $\begingroup$ Could you not post lots of images and slides, and instead try to formulate your question as text, so that Google search pick it up and people can actually find it? (It's ok to use the images and slides as supplemental material, but the way this question is written is a bit annoying. It starts with a random url, then some screenshots. This isn't Tik Tok, man. $\endgroup$ Nov 17 '21 at 6:59
  • $\begingroup$ google has image search as well man. i mostly use google image search. it is useful than text search imo. easier to understand when images are there. @AndrejBauer $\endgroup$
    – nagkob
    Nov 17 '21 at 7:19
  • 1
    $\begingroup$ You are a new contributor, I have been around for many years. Please take it as friendly advice explaining what this community appreciates. Why do you think your question has -3 votes? $\endgroup$ Nov 17 '21 at 17:32
  • $\begingroup$ sure so I should type rather than using image. alright. will do that. $\endgroup$
    – nagkob
    Nov 17 '21 at 17:59
2
$\begingroup$

It does not matter whether we are thinking about Turing machines or actual computers that you use every day – they all encode information all the time.

A computer can process only sequences of bits $0$ and $1$ (and even $0$ and $1$ are further encoded as electrical signals). It cannot process any text, nor images, nor sound directly. All data that is ever processed by a computer is encoded using $0$'s and $1$'s. I hope that's clear.

Now, a computer may simulate another computer. Here is a ZX Spectrum simulator which simulates my childhood computer on your computer. But of course, you do not think that your computer contains an actual small copy of a 1986 computer, do you? It's clear that there is a program which simulates ZX Spectrum – and that program is made of $0$s and $1$s that encode Spectrum ZX.

The situation is entirely analogous with Turing machines. If you want one Turing machine to simulate another, you must represent it on the tape somehow – because just like ordinary computers work with $0$s and $1$s, so Turing machine work with whatever is written on the tape. When you write down a description of a Turing machine onto a tape, well that is when you encoded it.

$\endgroup$
1
$\begingroup$

The Turing Machine is thought (Church-Turing thesis) to perfectly represent the intuitive idea of computation; that is, for any operation that is computable, a Turing Machine exists. After the Turing Machine is defined and understood, a logical next step for automata theory research is to consider what properties of Turing Machines can be computed by Turing Machines.

The input taken by a Turing Machine is a finite string; therefore in order to be passed as an input, a TM must be rendered into a string that unambiguously describes it. Without establishing the existence of a formal encoding the idea of passing a TM as input would be a poorly-defined procedure.

The slides you have attached show a binary encoding is used with unary values and zero as a separator symbol; this is not the only possible encoding and encodings do not have to be strictly binary, any fixed-size symbol set will do. However, binary is often preferred because of its simplicity, the analogy to real-world binary computers and to show the power of TMs even with very limited symbol sets. Any encoding that uniquely describes any TM with a finite set of symbols works – the important thing is that we know encoding a TM as a finite string is possible.

As for programming: one particularly interesting outcome of encoding Turing Machines is the existence of the Universal Turing Machine: a TM that, for some selected type of encoding, is capable of simulating any thus encoded Turing Machine given to it as an input and determine its state, tape contents and head position after an arbitrary number of steps. This is important for two main reasons: it is the theoretical cornerstone for the idea of a programmable computer, and it is exceedingly useful for almost any theoretical work on the computability of various properties of TMs.

$\endgroup$
-1
$\begingroup$

In a nutshell: Suppose there is no encoding, but the initial specification of the Turing Machine (TM). Then the universal Turing machine (UTM) has in its tape alphabet all the tape symbols of the simulated TM. Since it can simulate any TM, and there is no bound on TM tape alphabet size (though each is finite), the UTM must have an infinite set of tape symbols. This is not permitted as all (U)TM must be finitely specified.

First I should remark that your title is wrong: we do not need to encode universal Turing machines (UTM), but the Turing machines (TM) that we wish to simulate with the UTM.

First we must at least agree on a standard format to represent TMs, so that we can define them precisely, and use them for proofs or hand simulation. This representation must be a string since it is intended to be put on the UTM tape. Basically we use a state alphabet and a tape alphabet plus a few other symbols such as L and R, and a variety of punctuation symbols, so that we can represent each of the transitions. Then we can represent the TM as a long string composed of all the small string representing the transitions, plus various details that may be needed such as the initial state and the list of accepting states, and a few symbols to separate the string components and read them when needed.

Given such a presentation $\xi$ of a TM $M_\xi$, one can simulate by hand its computation on a tape $\tau$ in $\Sigma^\star$.

A universal Turing machine (UTM) is a TM that will do that same simulation of $M_\xi$ when provided with a tape containing the specification of $M_\xi$ and the tape content on which $M_\xi$ is supposed to compute.

As I understand it, the question you ask is why do you have to encode the specification of $M_\xi$ rather than than use directly the original specification $\xi$ with the original alphabets as they were given.

A first reason is very simple. The UTM is supposed to be able to simulate all machines, but its tape alphabet may not contains the symbols used in the TM specification $\xi$. Fortunately, all specifications are defined up to symbol renaming. This allows us to replace any set of symbols (alphabet, state set, ...) by another such set of the same size. Thus we can replace all the symbols in $\xi$ by symbols in the tape alphabet $\Sigma_U$ of the UTM. This may be seen as a very simple encoding. But it is not enough.

The next problem may be that the tape alphabet $\Sigma_U$ is too small, smaller than the number of distinct symbols in $\xi$. Whatever the design of the UTM, this is bound to happen because a UTM must have a finite tape alphabet, but there is no bound on the (finite) size of TMs.

The answer to that is to encode the symbols in $\xi$ not with symbols of $\Sigma_U$, but with a set of strings chosen in $\Sigma_U^\star$. And there is an infinite number of them.

There are other reasons why this encoding is necessary for the TM to be simulated by a UTM, but this at least tells you why you cannot do without it.

The UTM may be seen as a programmable computer that executes a compiled program (the encoded TM specification) produced by a compiler (the encoding process) from a high-level language (the initial TM specification).

$\endgroup$
4
  • $\begingroup$ I'm afraid I don't undestand your "nutshell". Are you imagining that for every TM there is a symbol in the alphabet that corresponds to that TM? Please be more explicit how you view the situation where "there is no encoding". $\endgroup$ Nov 18 '21 at 14:24
  • $\begingroup$ To put it differently: the definition of UTM is that it receives as input both an encoding of a machine $M$ and an input $x$, and it then simulates the working of $M$ on input $x$, so what is your "nutshell" proposing to change, precisely? How will the UTM be instructed which $M$ it should simulate, if $M$ is not encoded on the input tape? $\endgroup$ Nov 18 '21 at 14:27
  • $\begingroup$ I beg to differ, but there are not "many possible definitions of a TM". You can't just change things around ("TM includes the tape content") and still call them Turing machines. Such changes completely modify what's what. You are of course free to develop your own ideas, but then the question will be what these ideas amount to and how they relate to existing concepts (which are used for very good reasons). $\endgroup$ Nov 18 '21 at 21:27
  • $\begingroup$ @AndrejBauer Please, can you remove the comments since that do not relate well to the current version of the answer. $\endgroup$
    – babou
    Nov 20 '21 at 17:08

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.