New answers tagged undecidability
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 ...
- 31
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.♦
- 156k
Top 50 recent answers are included