6
$\begingroup$

In version gamma of the ACM/IEEE/AAAI Computer Science Curricula 2023, on page 50, one of the illustrative learning outcomes for the "Computational Models and Formal Languages" section of the curriculum states that students should be able to

Use arithmetization and diagonalization to prove Turing Machine Halting/Undecidability.

I am quite familiar with using a diagonalization argument to prove that the halting problem is undecidable, but what does it mean to use arithmetization to prove this result? I don't believe I've come across a proof using this technique in any texts I've read before. Everybody seems to go with the diagonalization argument.

$\endgroup$

2 Answers 2

14
$\begingroup$

I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a description of a Turing machine as a bit-string and hence as a natural number). See, e.g., https://en.wikipedia.org/wiki/Halting_problem#Formalization.

In other words, the requirement is not that students should know how to use diagonalization to prove Turing Machine Halting/Undecidability, and also know how to use arithmetization to prove Turing Machine Halting/Undecidability. It is not that there are two separate ways to prove the undecidability of the halting problem and students should know both. Rather, it is that there is a standard proof of the halting problem, and this proof relies on both diagonalization and on "arithmetization" as defined above, and students should know the standard proof and grok those two aspects of it.

$\endgroup$
2
  • 1
    $\begingroup$ So, arithmetization = Gödelization, I guess. $\endgroup$
    – chi
    Nov 13, 2023 at 19:07
  • 2
    $\begingroup$ @chi: You could also just call it "a character encoding" and/or "a Turing-complete programming language," but that's too mundane-sounding. You have to use fancy words when you speak of Gödel's encoding. $\endgroup$
    – Kevin
    Nov 13, 2023 at 22:49
3
$\begingroup$

TLDR: It means that they are using a technique to represent Turing machines as numbers in order for the circularity to be possible, hence "arithmetization".

It is not trivial (especially, it was not at the time) that such a thing as code existed, or that things like binary numbers (which are just numbers) could be used to list or index all possible programs.

After Turing introduced the concept of a Turing machine, he specified that there were sets of instructions that would define what particular machine one is talking about. But it is not immediately obvious from this, that everything about those instructions, could, in fact, be described using a finite number.

Look into Gödel numbering also. Gödel showed that numbers can be used also to index all possible proof theories that can be used as foundations of mathematics (rules for what is a valid proof).

It is more evident, however, from Turing's definition, that Turing machines could do operations on numbers. It was just less obvious that they could be described by numbers. Because of these two connections, it is possible to set up circular situations where Turing machines are calculating properties of other Turing machines, including, in particular, themselves.

This allowed Turing to create a machine that "halts (returns a value) only for numbers of (code of) Turing machines that will never halt". If the halting problem were solvable, such a machine would have to exist, because their (own) number would come up in the list of machines. Since this is a contradiction, it proves the halting problem is undecidable by any machine that is equivalent to a Turing machine, i.e. finite, mechanical.

$\endgroup$
1
  • $\begingroup$ > especially, it was not at the time > But it is not immediately obvious from this, that everything about those instructions, could, in fact, be described using a finite number. It was obvious for all people involved, given the historical context. Godel encoding was defined before Turing machines, and the undecidability of the halting problem was proved in the original paper and was one of its main points it. Ariphmitezation is not obvious to modern people, cuz now we have better intuition on Turing complete models. en.wikipedia.org/wiki/Halting_problem#Timeline $\endgroup$
    – uhbif19
    Nov 14, 2023 at 13:22

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.