4 ms·

Regarding Goedel, I apologize and retract my claim. Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such w

Regarding Goedel, I apologize and retract my claim. Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such way. It can have applications, for instance Cantor's original paper used it to prove that there are infinitely many transcendental numbers. It is also used in real analysis, in Lebesgue integration, and in measure theory. But it is not the only way to do so. There is a very real sense in which {1,2,3} is a smaller set than {4,5}; that does depend on knowledge of the contents of the set though, not merely the number of elements contained. In a more abstract context where measure or natural density aren't applicable, cardinality can be left as the only well-defined definition of "size", but in most contexts I agree, it's just one of many possible definitions and they should each be used with care. Arguing about the sizes of different infinite sets is tricky, though. The set of even integers has the same cardinality as the set of all integers, even though it has density 0.5. The cardinality of the set of rationals is somehow "infinitely less" than the set of irrationals, even though both sets are dense on one another. But there are some things we can learn from not having Me, however, I like cardinality for the aesthetic properties. I like the Axiom of Choice and all the nonsense that follows from it. Cardinal infinities behave quite differently from the well-defined infinities of ordinals, hyperreal numbers, and surreal numbers. In your article "The Size of a Set", you discuss Formalism. Are you aware of the axiom "V=L"? It's quite neat, because by effectively outlawing any non-constructible sets, the Generalized Continuum Hypothesis follows! If you accept cardinality as a purely aesthetic definition in conjunction with Formalist ideology, you get a very beautiful result. Practical, maybe not, but beautiful. That is all to say that I agree with a lot of what's in your paper on "the Size of a Set". However, the "Program Analogy" section of the paper contains what I think is a flawed argument: > [A] Cantor-type conclusion concerning the sizes of sets of programs is absurd. The proper conclusion is simply that there is no program (in some programming language) to generate all and only the infinite-sequence programs (in that same programming language). It is not a conclusion about the sizes of sets. Likewise in the original Cantor argument, the proper conclusion is not about the sizes of sets; it is simply that there is no sequence of all infinite sequences. I think the correct conclusion here is that to determine which programs are "infinite-sequence" is undecidable. You've reached a contradiction, therefore the last assumption must be flawed; in this case the assumption was that you could write a program D "whose execution neither halts nor goes into a non-printing infinite loop." This assumption is about programs and programming languages, and says nothing about sets, so the analogy is flawed. In Cantor's argument, the assumption is that the set [0,1) can be ordered. You're correct in saying that this is merely a statement about the existence of a bijection between the naturals and the reals, but that is the definition of cardinality. Your issue here is that you don't like saying that cardinality means "size", and that's fair. But I think this analogy is a stretch at best, and irrelevant to your overall argument.

EricHehner 6y ago
I said: So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. You said: Alas, it has been proven. RAM computers are equivalent to Turing machines. If X and Y are Turing-complete languages then all X-programs can be converted to Turing machines, your proposed Y-program can also be converted into a Turing machine. Put another way, unless your language X is too weak to be useful, there should exist a deterministic program to convert any program written in Y into a program written in X with identical behavior (with regard to halting). This should be evident by the fact that the computers we use day-in and day-out execute one binary machine language. Any X-program and Y-program reduce to the same assembly language. I say: You cannot have read my papers carefully. I spent a lot of time explaining, with examples, why programs with subjective specifications cannot be translated from one TM-equivalent language to another TM-equivalent language. You said: This would disprove the Church-Turing thesis. I say: Again, you cannot have read the paper carefully. There is a section in each of www.cs.utoronto.ca/~hehner/OSS.pdf and www.cs.utoronto.ca/~hehner/EGT+.pdf titled "Church-Turing Thesis", explaining that it applies to all objective specifications, which are the only specifications considered by Church and Turing, but not to subjective specifications. You said: Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such way. It can have applications, for instance Cantor's original paper used it to prove that there are infinitely many transcendental numbers. It is also used in real analysis, in Lebesgue integration, and in measure theory. I say: Again, you cannot have read the paper carefully. Almost every time I mention applications in the paper, I say "applications outside mathematics". If you consider mathematics to be an application of mathematics, then all mathematics has applications. You said: the "Program Analogy" section of the paper contains what I think is a flawed argument. I say: Yes, I point out the flaw in the paper in the paragraph that starts with the sentence "Like the original Cantor argument, this program-analogy version is informal, and the informality may hide serious errors.". Did you miss it? You will "win" this debate by throwing misunderstandings at me faster than I can reply. And it's disheartening because the replies are already in the papers, if you read them carefully.
- PotatoPancakes 6y ago
  > I say: You cannot have read my papers carefully. I spent a lot of time explaining, with examples, why programs with subjective specifications cannot be translated from one TM-equivalent language to another TM-equivalent language. > I say: Again, you cannot have read the paper carefully. There is a section in each of www.cs.utoronto.ca/~hehner/OSS.pdf and www.cs.utoronto.ca/~hehner/EGT+.pdf titled "Church-Turing Thesis", explaining that it applies to all objective specifications, which are the only specifications considered by Church and Turing, but not to subjective specifications. Fair point, I had not read OSS. That said, I think your interest in "subjective specifications" goes against your apparent disinterest in the "twisted self-reference" of Halting Problem proofs. It throws readers off as you attempt to add twisted self-reference to the domain of programming, where it isn't usually found, and simultaneously remove it from other places where it emerges naturally (as a consequence of the Church-Turing Thesis). > I say: Again, you cannot have read the paper carefully. Almost every time I mention applications in the paper, I say "applications outside mathematics". If you consider mathematics to be an application of mathematics, then all mathematics has applications. Fair point, I concede. > I say: Yes, I point out the flaw in the paper in the paragraph that starts with the sentence "Like the original Cantor argument, this program-analogy version is informal, and the informality may hide serious errors.". Did you miss it? No, I didn't miss it, but the inclusion of such an irrelevant and flawed analogy is perplexing and makes the paper harder to read, and seem less worth the time it takes to read carefully. You've written a lot, and some of the material can be tough to chew through (especially that written with the structure of formal logic). > And it's disheartening because the replies are already in the papers, if you read them carefully. https://www.youtube.com/watch?v=HMqZ2PPOLik https://www.youtube.com/watch?v=HMqZ2PPOLik I've reread your OSS and EGT papers, with the additional help of your comments above, I think I now understand your stance better. I think part of your notoriety comes from your papers appearing to contradict the Halting Problem, with sections titled "How to Solve Halting" that don't actually provide a clear method. Instead, emphasizing that you're examining self-referential logic puzzles reminiscent of those found in Raymond Smullyan books would help clarify what you're doing. Many readers come in with the Bernard Russell mindset of "Let's try to avoid these self-referential questions" and thus have trouble adjusting to your angle. Most readers interested in The Halting Problem are not interested in "subjective specifications." Your papers aren't easy reads (and I'm not complaining: it's an unavoidable consequence of their nature as papers on self-referential logic) and a brief first pass of your papers leaves many of us misinterpreting your angle. I think some editing of your introductions and conclusions could help immensely. Be very upfront and explicit that you don't disagree with the common conclusions of The Halting Problem for objective specifications, but instead that you're more interested in exploring a different side of programming. (In this regard, Jeffrey Shallit's mean-spirited "fringe computer science" comments make sense, but really ought not to be an insult since you are in fact exploring an oft-ignored side of the field.) Err on the side of caution, and over-communicate your intent with the papers! When many readers think you've said X when you have not, in fact, said X, take that as constructive feedback to more explicitly say "not X" in edits and future papers. Thank you for guiding me in reading your papers. Your arguments in this thread have helped me make sense of them. I think I finally understand your arguments, and I hope with a change to your approach, you can successfully reach other readers too.

EricHehner 6y ago

I said: So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. You said: Alas, it has been proven. RAM computers are equivalent to Turing machines. If X and Y are Turing-complete languages then all X-programs can be converted to Turing machines, your proposed Y-program can also be converted into a Turing machine. Put another way, unless your language X is too weak to be useful, there should exist a deterministic program to convert any program written in Y into a program written in X with identical behavior (with regard to halting). This should be evident by the fact that the computers we use day-in and day-out execute one binary machine language. Any X-program and Y-program reduce to the same assembly language. I say: You cannot have read my papers carefully. I spent a lot of time explaining, with examples, why programs with subjective specifications cannot be translated from one TM-equivalent language to another TM-equivalent language. You said: This would disprove the Church-Turing thesis. I say: Again, you cannot have read the paper carefully. There is a section in each of www.cs.utoronto.ca/~hehner/OSS.pdf and www.cs.utoronto.ca/~hehner/EGT+.pdf titled "Church-Turing Thesis", explaining that it applies to all objective specifications, which are the only specifications considered by Church and Turing, but not to subjective specifications. You said: Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such way. It can have applications, for instance Cantor's original paper used it to prove that there are infinitely many transcendental numbers. It is also used in real analysis, in Lebesgue integration, and in measure theory. I say: Again, you cannot have read the paper carefully. Almost every time I mention applications in the paper, I say "applications outside mathematics". If you consider mathematics to be an application of mathematics, then all mathematics has applications. You said: the "Program Analogy" section of the paper contains what I think is a flawed argument. I say: Yes, I point out the flaw in the paper in the paragraph that starts with the sentence "Like the original Cantor argument, this program-analogy version is informal, and the informality may hide serious errors.". Did you miss it? You will "win" this debate by throwing misunderstandings at me faster than I can reply. And it's disheartening because the replies are already in the papers, if you read them carefully.

PotatoPancakes 6y ago
> I say: You cannot have read my papers carefully. I spent a lot of time explaining, with examples, why programs with subjective specifications cannot be translated from one TM-equivalent language to another TM-equivalent language. > I say: Again, you cannot have read the paper carefully. There is a section in each of www.cs.utoronto.ca/~hehner/OSS.pdf and www.cs.utoronto.ca/~hehner/EGT+.pdf titled "Church-Turing Thesis", explaining that it applies to all objective specifications, which are the only specifications considered by Church and Turing, but not to subjective specifications. Fair point, I had not read OSS. That said, I think your interest in "subjective specifications" goes against your apparent disinterest in the "twisted self-reference" of Halting Problem proofs. It throws readers off as you attempt to add twisted self-reference to the domain of programming, where it isn't usually found, and simultaneously remove it from other places where it emerges naturally (as a consequence of the Church-Turing Thesis). > I say: Again, you cannot have read the paper carefully. Almost every time I mention applications in the paper, I say "applications outside mathematics". If you consider mathematics to be an application of mathematics, then all mathematics has applications. Fair point, I concede. > I say: Yes, I point out the flaw in the paper in the paragraph that starts with the sentence "Like the original Cantor argument, this program-analogy version is informal, and the informality may hide serious errors.". Did you miss it? No, I didn't miss it, but the inclusion of such an irrelevant and flawed analogy is perplexing and makes the paper harder to read, and seem less worth the time it takes to read carefully. You've written a lot, and some of the material can be tough to chew through (especially that written with the structure of formal logic). > And it's disheartening because the replies are already in the papers, if you read them carefully. https://www.youtube.com/watch?v=HMqZ2PPOLik https://www.youtube.com/watch?v=HMqZ2PPOLik I've reread your OSS and EGT papers, with the additional help of your comments above, I think I now understand your stance better. I think part of your notoriety comes from your papers appearing to contradict the Halting Problem, with sections titled "How to Solve Halting" that don't actually provide a clear method. Instead, emphasizing that you're examining self-referential logic puzzles reminiscent of those found in Raymond Smullyan books would help clarify what you're doing. Many readers come in with the Bernard Russell mindset of "Let's try to avoid these self-referential questions" and thus have trouble adjusting to your angle. Most readers interested in The Halting Problem are not interested in "subjective specifications." Your papers aren't easy reads (and I'm not complaining: it's an unavoidable consequence of their nature as papers on self-referential logic) and a brief first pass of your papers leaves many of us misinterpreting your angle. I think some editing of your introductions and conclusions could help immensely. Be very upfront and explicit that you don't disagree with the common conclusions of The Halting Problem for objective specifications, but instead that you're more interested in exploring a different side of programming. (In this regard, Jeffrey Shallit's mean-spirited "fringe computer science" comments make sense, but really ought not to be an insult since you are in fact exploring an oft-ignored side of the field.) Err on the side of caution, and over-communicate your intent with the papers! When many readers think you've said X when you have not, in fact, said X, take that as constructive feedback to more explicitly say "not X" in edits and future papers. Thank you for guiding me in reading your papers. Your arguments in this thread have helped me make sense of them. I think I finally understand your arguments, and I hope with a change to your approach, you can successfully reach other readers too.