In context of "Computability", I have went over some proofs for Recursion Theorem using Turing Machine description. A TM $M$ stands for a single tape Turing machine and $\langle M \rangle$ is the description of TM $M$. Even some semi-decidable machines such as $A_{\mathrm{TM}} = \{ \langle M, w \rangle \mid \text{TM $M$ accepts $w$} \}$. My question is simple:

What is difference between using $\langle M \rangle,\langle w \rangle$ vs $\langle M , w \rangle$ for a TM description?

A simplistic answer I assume is that it is being a convention in writing formal proof that books follows standard of combining all inputs as a single description (all inputs comes under single brackets as opposed to multiple descriptions)?

My question c

If $M_1 = \{ \langle M , w \rangle \mid \text{TM $M$ accepts $w$} \}$ and $M_2 = \{ \langle M \rangle , \langle w \rangle \mid \text{TM $M$ accepts $w$} \}$

What's the difference between $M_1$ and $M_2$?


$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc.

This serves, for instance, to distinguish between $\{ \langle M \rangle \mid \text{$M$ is a TM} \}$, which contains encodings of TMs (e.g., their Gödel numbers or representations in binary), and $\{ M \mid \text{$M$ is a TM} \}$, which is the set of Turing machines themselves (as mathematical objects). The underlying motivation is that it is not clear how a TM (as an object) can be passed as an input; what you do is provide its "program", that is, its states and transition function.

When multiple objects are encoded together as a single string (i.e., to be seen as a single object), it is usual practice to denote it as $\langle x_1, \ldots, x_m \rangle$. Again, it is not immediate what the encoding is. It could be simply concatenating the encodings of each $x_i$ and separating them (e.g., $\langle x_1, \ldots, x_m \rangle = \langle x_1 \rangle \# \cdots \# \langle x_m \rangle$); it could also be that the encoding of $x_i$ is altered in some way (e.g., each $0$ or $1$ in $\langle x_i \rangle$ is doubled and each such representation is separated by $01$); it could even be that the entirety of the representation is compressed (so as to reduce its length) or that it is subject to some predetermined enumeration (e.g., as a vector over some countable space).

Generally, if they are relevant to the context at all, these descriptions should be made precise beforehand, as most textbooks do. In computability theory, except when covering Gödelization, they usually are not; this is because the actual length of the input is irrelevant to computability questions. Things are different in complexity theory—though it usually does not get much attention there either (besides coming up in a preface or similar); most objects are encoded in binary anyway, and multiple objects with only a constant stretch, which suffices for almost all complexity-theoretical topics.

  • $\begingroup$ My question again is if there are multiple inputs w1,w2 with <M>, why in books they will write input as <M,w1,w2> and not as <M>,<w1>,<w2>? $\endgroup$ – Prithi Jul 2 '19 at 21:30
  • $\begingroup$ @Prithi Added a couple of paragraphs, also explaining encoding of multiple inputs. $\endgroup$ – dkaeae Jul 3 '19 at 7:25
  • $\begingroup$ @Prithi Also it is not clear how you would pass something like $\langle M \rangle, \langle w_1 \rangle$ to a TM. Do you mean a tuple $(\langle M \rangle, \langle w_1 \rangle)$ or actually the string $\langle M \rangle$, followed by a comma, followed by the string $\langle w_1 \rangle$? $\endgroup$ – dkaeae Jul 3 '19 at 7:28
  • $\begingroup$ I understand what you're trying to say. In maths notation, there's not much emphasis on implementation so, as a convention, all the inputs are encoded in a single description. Thanks. $\endgroup$ – Prithi Jul 4 '19 at 23:30
  • $\begingroup$ Also, there's an relevant extract in Michael Siper's book about the notation I recently read in section "Minimal Length Descriptions". $\endgroup$ – Prithi Jul 5 '19 at 1:15

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.