14 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

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 ...
D.W.'s user avatar
  • 156k
3 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

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 ...
Sam Gutkind's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible