7 ms·
Proofs based on diagonalization help reveal the limits of algorithms
- est31 3y agoGödel also had a short appearance in the Oppenheimer movie, in the scene where Einstein talks about Kurt still being afraid even though they are in the states now.
- ninepoints 3y agoI would probably refer to this as "Cantor's diagonalization" to avoid the ambiguity with "matrix diagonalization" using the matrix eigendecomposition.
- srcreigh 3y agoI’d rather not call it diagonalization at all. Nothing about turings construction enumerates many machines and builds a new machine to flip some aspect of the other machines on the list. It’s more like the liar paradox akin to Gödel first incompleteness theorem.
- doomrobo 3y agoIt turns out that these are all kind of the same, the Liar's Paradox, Russell's Paradox, the Halting Problem, etc. And indeed the they rely on a "diagonal map" i.e., a map x -> (x, x) in the construction. This was a great read, if you want a mathematical take on it, and some generalization too. https://arxiv.org/abs/math/0305282v1 https://arxiv.org/abs/math/0305282v1
- hgsgm 3y agoSure, if you create a larger object it can contain two smaller objects. But that construction is so general that it contains all proofs of the from "There exists X that does not have not property Y" that proceed by constructing something that lacks the property, and stuffs the proof into the diagram.
- abdullahkhalids 3y agoIts not fully general. Many different types of undecidability proofs are basically proofs by diagonalization, but not all are. See some counter examples: https://mathoverflow.net/q/454105 https://mathoverflow.net/q/454105
- srcreigh 3y ago“I genuinely don’t have an operational definition for what it means to use diagonalization” - Terry Tao
- joaogui1 3y agoSo you are listing all TMs + inputs and creating a machine which does the opposite (from a halting perspective), which is like when Cantor lists the reals and creates a new one that has the opposite digit from the other reals
- hgsgm 3y agoNo, it's not like that at all. It's just an algorithm that contradicts itself, like Russell's Paradox.
- cvoss 3y agoBroaden your view of the Halting undecidability proof. Let T_i enumerate all Turing machines. Let E be a function that encodes a Turing machine as a tape. Suppose Halting is decidable, and let H_i,j be the table of bits such that H_i,j is 1 iff T_i halts on input tape E(T_j). There is some x such that H_x,j = !H_j,j for all j (we can construct/find such a machine by hypothesis). Therein lies the diagonalization, you see? We just identified a row such that the bit in column j differs from the jth bit on the the diagonal. The paradox you reference is what happens at bit H_x,x. But, in the bigger context, this argument proceeded by diagonalization.
- hgsgm 3y agoI tried to comment that on the article. But they use Disqus which is hostile to people making comments.
- xelxebar 3y agoHrm... Ambiguity only arises out of context. IMHO, there is ample enough context here to disambiguate, just as you seem to have successfully done. Matrix diagonalization and what you're calling Cantor's diagonalization can both be seen as instantiations of a more general diagonalization process. This latter process seems to be what the article is obliquely pointing at, cf my top-level comment for a video that introduces those details.
- housecarpenter 3y agoThe term I've seen most often is "diagonal argument".
- xelxebar 3y agoHere's a nice video that digs into the general structure of diagonalization arguments: https://www.youtube.com/watch?v=dwNxVpbEVcc https://www.youtube.com/watch?v=dwNxVpbEVcc It's a really neat way to see a shared core between seemingly-separate topics: - Gödel's Incompleteness Theorems, - Cantor's Theorem, - Russell's Paradox, - The Halting Problem, - The Y Combinator!, - etc.
- 3abiton 3y agoGreat video, thanks for sharing
- ballenf 3y agoI have a problem with the diagonalization, but I'm more of a math fan so please forgive my ignorance. The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. Then says that we construct a number that can't be on them by flipping bits the down the diagonal. But hasn't this concept already kind of mixed domains? The enumeration was describing a process, but the diagonal flipping move seems to assume or require that the enumeration is complete or at least paused. How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. Obviously at any point in time it won't be, but aren't we just kind of proving that we can construct a number that isn't on the list yet? And the first process would certainly eventually get to our constructed number? The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I just don't get how we conclude that Integers are countable and Reals are Uncountable from this proof, even though its obvious in an intuitive sense that Reals have to be much "larger".
- vgatherps 3y ago> The proof of uncountability of real numbers starts with a process of enumerating this infinite list of infinitely long binary numbers. > How could the diagonal construction ever finish to allow a "check" of whether the result of that process is actually on the list. > The diagonal just seems like a shortcut to a number that we know the first process hasn't gotten to yet? I think you are mixing up the enumeration of the (hypothetically countable) reals with the existance of said set of reals, and viewing the construction of the counterexample as an actual process that involves programmatically iterating over the list instead of a description of how the digits of said new real number is created. There is no pause or setp-by-step of this iteration that's required, since it's only telling you that the i'th digit of the counterexample will be distinct from the i'th digit of the i'th number (thereby creating a real not in your countable set, since you have created a number outside of your 1-1 mapping onto the natural numbers).
- ballenf 3y agoCan someone explain this part of Turing's proof: > ... we can define an uncomputable problem like the one in Turing’s proof: “Given an input string representing the code of an algorithm, output 1 if that algorithm outputs 0 when its own code is the input; otherwise, output 0.” Every algorithm that tries to solve this problem will produce the wrong output on at least one input — namely, the input corresponding to its own code. Why is this impossible? As I see it, there are two algorithms intermixed in that statement: 1. Code that emits a 0 if the input is it's own code 2. Code that emits a 1 if it receives as input code that behaves according to Algo 1. Feel like I'm missing something basic or obvious!
- lsy 3y agodef unc(algstr) { if (algstr(algstr) == 0) return 1 else return 0 } unc(unc) -> what does this return?
- hyperhello 3y agoStack overflow exception, since it calls unc(unc) from itself.
- ghkbrew 3y agoImagine you have an code which does #2. Now give it itself as an argument. What is the result? If it emits 0 then it's behaving according to #1, then because we assumed it satisfies #2 it must emit 1, a contradiction. Similarly it can't emit 1. Thus it is impossible to have an algorithm which solves #2 for all inputs, because it must fail on at least one input (itself)
- deleted 3y ago[deleted]
- Slow_Dog 3y agoThe document's initial example of diagonalization doesn't explain it properly. It shows how you can find a binary string that's not in the list; fine. But it's conveniently a list of 5 strings of length 5. It doesn't show how you'd find a new string of length 5 that's not in a list of 6 such strings, or 31 such strings. I suspect the "conveniently" may drop out of some conversion of a real problem to an abstraction, but that's not explained.
- quietbritishjim 3y agoI think the missing piece is just note that, for actual proof applications, the length of the individual "strings" and the total number of them is both (countable) infinity, so the size does match.
- thaumasiotes 3y agoIt's not necessary that they match. All you need is that the length of each string is not less than its position in the list.
- thaumasiotes 3y ago> The document's initial example of diagonalization doesn't explain it properly. > It shows how you can find a binary string that's not in the list; fine. But it's conveniently a list of 5 strings of length 5. It doesn't show how you'd find a new string of length 5 that's not in a list of 6 such strings This is actually a mistake on your part. It's true that it's possible to find a string of length 5 that isn't already contained in a list of 6 such strings. But it isn't possible to do that by using diagonalization. The concept of diagonalization is that you differ from the first string in the list at index 1, from the second string in the list at index 2, from the third at index 3, and so on. A list of six strings, to illustrate diagonalization, would require all of the strings to be six digits long.
- wzdd 3y ago> would require all of the strings to be six digits long The OP's point (presumably, because it bugged me too) is that the article doesn't make this clear.
- syats 3y agoI thought for a second the title was missing a (1936).
- 7373737373 3y agoUnrelated to this, but one type of mathematical argument/technique I've never seen explained "for dummies" is proving the independence of an axiom from a set of axioms.
- LudwigNagasena 3y agoA relevant link, Lawvere's fixed point theorem: https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theore...