6 ms·

Unfortunately, the text by Gallier and Quaintancis is somewhat obsolete because it misses the following developments: * The Church/Turing Thesis is false for r

Unfortunately, the text by Gallier and Quaintancis is somewhat obsolete because it misses the following developments: * The Church/Turing Thesis is false for reasons outlined here: https://professorhewitt.blogspot.com/2021/03/the-churchturing-thesis-is-false.html https://professorhewitt.blogspot.com/2021/03/the-churchturin... * Gödel failed to prove inferential undecidablity in foundations for reasons outlined here: https://professorhewitt.blogspot.com/2021/03/godel-failed-to-prove-inferential.html https://professorhewitt.blogspot.com/2021/03/godel-failed-to... * That "theorems of an order can be computationally enumerated" is true but unprovable for reasons outlined here: https://professorhewitt.blogspot.com/2021/03/churchs-dilemma-resolved.html https://professorhewitt.blogspot.com/2021/03/churchs-dilemma... However, the text by by Gallier and Quaintancis does provide historical perspective.

bmc7505 5y ago
Why is this comment being downvoted?
- drdeca 5y ago
  Because it is wrong. The comment is claiming that the comment author has overturned well understood results, when they have not done so.
  - ProfHewitt 5y ago
    You are welcome to join the debate! Scientific development proceeds building on previous results as is the case here as shown by references in articles.
- exdsq 5y ago
  I assume because these are huge claims however they support these claims with their own blog site rather than a peer reviewed journal etc
  - ProfHewitt 5y ago
    The articles are published here: https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=2561841 https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=256...
    - ganafagol 5y ago
      SSRN is not a peer reviewed journal. It's essentially just a preprint server where anybody can dump whatever they please. So it's more like the personal blog that the parent comment referred to than a peer reviewed journal they were asking you to cite. Please cite peer reviewed works. As an accomplished academic of 70+ years I'm assuming you are very familiar with that process.
      - ProfHewitt 5y ago
        Dear Ganafagol: Please do not denigrate SSRN, which is used by many prominent researchers to publish their articles. Eventually, many of the articles are republished elsewhere. However, waiting years for trees to be cut down should not be allowed to slow down scientific progress! You are incorrect that SSRN is a "private blog".
        ganafagol 5y ago
        > You are incorrect that SSRN is a "private blog". And you are incorrect in claiming that I wrote that.
        ProfHewitt 5y ago
        Dear Ganafagol: I mistyped :-( Instead, you insinuated that SSRN is a "personal blog." Also, you are incorrect that "anybody can dump anything that they please" into SSRN. If you wait long enough, each article will be republished elsewhere :-) However, you may have to wait years :-( In the meantime, more articles will be published in SSRN for which you will have to wait even longer to be republished!
drdeca 5y ago
Let ◻ be the modal operator "It is provable that", so ◻P means that P is provable. The first part of your argument in the second link says:[ Suppose that there is a proposition UNP such that UNP ⇔ ¬◻UNP . Then, suppose that ¬UNP . It then follows that ¬¬◻UNP , i.e. that ◻UNP. Therefore, ◻◻UNP . Then, as UNP ⇔ ¬◻UNP, therefore ¬UNP ⇔ ◻UNP. Then, replace the ◻UNP in ◻◻UNP with ¬UNP, and therefore conclude ◻¬UNP . So, at this point, we have concluded that ◻¬UNP and also that ◻UNP. So, you can conclude that, __under these assumptions__, that ◻⊥ . So, under the assumption that there is a statement UNP such that UNP ⇔ ¬◻UNP , and the additional assumption that ¬UNP, you can conclude that ◻⊥. ] Indeed. If a system admits a statement UNP, (and the system is strong enough to do the appropriate reasoning) (and peano arithmetic and such does admit such a statement UNP), then within the system, you can show that ¬UNP implies ◻⊥. I.e. "if the statement that claims it cannot be proven, can be proven, then the system proves a contradiction". This is entirely normal, and does not overturn anything. However! While the assumption that ¬UNP allows us to derive ◻⊥, it does not allow us to derive ⊥. We have __not__ shown that ¬UNP → ⊥, we have only shown that ¬UNP → ◻⊥. Therefore, this is not justification in appealing to proof by contradiction, and concluding UNP (nor ◻UNP).
- bloak 5y ago
  I've not read ProfHewitt's argument, so I'm just looking at your summary. If ◻P means "P is a proposition that is formally provable within some implicit formal system" (perhaps there should be a subscripted letter to show which formal system because there are an infinite number of them), then I don't understand what ◻◻UNP means, because ◻UNP is not a proposition of the implicit formal system.
  - chriswarbo 5y ago
    > If ◻P means "P is a proposition that is formally provable within some implicit formal system" (perhaps there should be a subscripted letter to show which formal system because there are an infinite number of them) It doesn't mean that. The formal system is explicit: it's the system we're using to write statements like `◻P` (it's a form of modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic ).
dandanua 5y ago
That book doesn't touch any nondeterministic behavior at all. So, the nondeterministic extension of the Church-Turing Thesis is absolutely irrelevant here. Your other cited "developments" seem senseful only in your personal universe.
- arethuza 5y ago
  Yeah - its a long time since I studied this kind of stuff but I'm pretty sure the Church–Turing thesis doesn't say anything about non-determinism or not - being more relevant to complexity than computability?
  - dandanua 5y ago
    The original thesis concerns only computable functions, which are deterministic by definition. It doesn't even consider their complexity. There are extended variations of the thesis, though. The complexity variation means that any computable function in one model of computation can have only a polynomial slowdown factor in comparison with another model of computation. It's believed to be false since the raise of quantum computations.
    - ProfHewitt 5y ago
      Nondeterministic Turing Machines were introduced very early and became the basis for the Church/Turing Thesis. An important complexity result is that in important applications, a digital implementation can be hundreds of times faster that a parallel lambda expression. Consequently, the lambda calculus cannot be a practical foundation for computing. See the following for more information: "An Actor Application Can Be Hundreds of Times Faster Than a Parallel Lambda Expression" https://professorhewitt.blogspot.com/2021/03/an-actor-application-can-be-hundreds-of.html https://professorhewitt.blogspot.com/2021/03/an-actor-applic...
  - ProfHewitt 5y ago
    The Church/Turing Thesis is that all computation can be performed by a nondeterministic Turing Machine. The Thesis is false because there are digital computations that cannot be performed by a nondeterministic Turing Machine. See the following article on how to formalize all of digital computation: "Physical Indeterminacy in Digital Computation" https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
ganafagol 5y ago
I'm having trouble understanding whether you are (1) a troll hiding behind Carl Hewitts name using a veil of CS lingo that's just complex enough to appear legit but is actually nonsense, or (2) actually Carl Hewitt losing his mind with a bunch of nonsense, or (3) actually Carl Hewitt who is on to something big and the world has just not caught up with you. To convince us of (3), have your theories been discussed at related conferences and what does the community make of them?
- ivanbakel 5y ago
  Having skimmed through the paper accessible at the end of the first link, I am leaning towards (1). It contains a barrage of eye-assaulting notation, lots of digressions and repetition, and basically no formal substance (which, for a logic/computation paper, is bizarre).
  - emmelaich 5y ago
    His WP talk page is a shit-show. I'm leaning towards 2. https://en.wikipedia.org/wiki/Talk:Carl_Hewitt https://en.wikipedia.org/wiki/Talk:Carl_Hewitt https://en.wikipedia.org/wiki/Talk%3ACarl_Hewitt%2FArchive_2 https://en.wikipedia.org/wiki/Talk%3ACarl_Hewitt%2FArchive_2 (to disclose, I am not qualified to actually judge the arguments)
    - ProfHewitt 5y ago
      As is common with many social media platforms, Wikipedia has huge problems with accountability :-( It's not worthwhile to go into the whole sordid story on HN.
  - ProfHewitt 5y ago
    Sorry that mathematical notation is causing you problems. How do you see the article lacking in formal substance?
    - ganafagol 5y ago
jkhdigital 5y ago
Ignore the downvotes: there is value in reading and attempting to understand some of this material, despite the inflammatory way the claims are made. Carl Hewitt is presumably in his 70s, so I'll forgive him for being an old man who probably doesn't give a shit what people think. In particular, I find the discussion of "paradox" attacks to be quite illuminating. Bertrand Russell attempted to remove self-referential and self-applicable paradoxes through the embellishments of types and orders. Hewitt argues that Gödel basically "cheated" in his proofs because the Diagonalization Lemma violated restrictions on orders. I'm not qualified to evaluate that argument on the basis of mathematical reasoning, but I do believe it points to a mismatch between the way computation is modeled in the abstract and the way it happens in reality. In the purely abstract world of natural numbers, there's really only one kind of thing: the natural number. Statements about natural numbers can be represented by natural numbers, statements about statements about natural numbers can also be represented by natural numbers, etc. While a given natural number can be parsed to compute if it is a valid encoding of a proposition of a certain order, it is always and forever a natural number and nothing else. However, I'm not entirely convinced that this captures the nature of computation in reality. When computation is embodied in a physical system, is it possible that the output of some computation can itself manifest computational properties that are not mere compositions of the lower level computational model? Where the interactions between the "higher level" objects simply follow a different set of rules and thus form the foundation of a new formalism? The notion of types seems to be a way to capture this, by introducing the possibility of distinguishing a "thing" from its abstract representation or description. If everything exists only within the world of the abstract representation, then a thing is indeed no different from its description, as any manipulation of the thing is equivalent to some manipulation of its description. But when the thing is, in fact, a physical object, it is clear that construction of the thing can fundamentally alter the model of computation. Why is this? I suspect that it is because there are no "pure" or "inert" abstractions in the real world; everything is in fact performing computation all the time. So physical constructions are not just compositions of objects, but also compositions of the computational capabilities of those objects. I realize this probably sounds like navel-gazing at this point, but sometimes that can be a useful activity.
- ProfHewitt 5y ago
amgreg 5y ago
I am disappointed at several comments on this thread. Professor Hewitt, I personally think you've enriched the community by putting these claims here. They've led me to read more about several things, which I will list here for anyone else who might be looking for related topics: The difference between indeterminism and nondeterminism, bounded and unbounded nondeterminism, the actor model of computation, local arbitration versus global consensus, and state machines versus configuration-based computation. You've responded to the ad hominem attacks with class. I hope you do not take them as a reflection of the HN community at large; please keep coming back and posting (provocatively) as you have done, because it induces learning.
- ProfHewitt 5y ago
  Thank you very much for your warm words. Of course, I sometimes make mistakes :-( However, I do try to learn from them!
  - ProfHewitt 5y ago
    PS. Also thanks for picking up on important topics including "indeterminism and nondeterminism, bounded and unbounded nondeterminism, the Actor model of computation, local arbitration versus global consensus, and state machines versus configuration-based computation."

bmc7505 5y ago

Why is this comment being downvoted?

drdeca 5y ago
Because it is wrong. The comment is claiming that the comment author has overturned well understood results, when they have not done so.
- ProfHewitt 5y ago
  You are welcome to join the debate! Scientific development proceeds building on previous results as is the case here as shown by references in articles.
exdsq 5y ago
I assume because these are huge claims however they support these claims with their own blog site rather than a peer reviewed journal etc
- ProfHewitt 5y ago
  The articles are published here: https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=2561841 https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=256...
  - ganafagol 5y ago
    SSRN is not a peer reviewed journal. It's essentially just a preprint server where anybody can dump whatever they please. So it's more like the personal blog that the parent comment referred to than a peer reviewed journal they were asking you to cite. Please cite peer reviewed works. As an accomplished academic of 70+ years I'm assuming you are very familiar with that process.
    - ProfHewitt 5y ago
      Dear Ganafagol: Please do not denigrate SSRN, which is used by many prominent researchers to publish their articles. Eventually, many of the articles are republished elsewhere. However, waiting years for trees to be cut down should not be allowed to slow down scientific progress! You are incorrect that SSRN is a "private blog".
      - ganafagol 5y ago
        > You are incorrect that SSRN is a "private blog". And you are incorrect in claiming that I wrote that.
        ProfHewitt 5y ago
        Dear Ganafagol: I mistyped :-( Instead, you insinuated that SSRN is a "personal blog." Also, you are incorrect that "anybody can dump anything that they please" into SSRN. If you wait long enough, each article will be republished elsewhere :-) However, you may have to wait years :-( In the meantime, more articles will be published in SSRN for which you will have to wait even longer to be republished!

drdeca 5y ago

Let ◻ be the modal operator "It is provable that", so ◻P means that P is provable. The first part of your argument in the second link says:[ Suppose that there is a proposition UNP such that UNP ⇔ ¬◻UNP . Then, suppose that ¬UNP . It then follows that ¬¬◻UNP , i.e. that ◻UNP. Therefore, ◻◻UNP . Then, as UNP ⇔ ¬◻UNP, therefore ¬UNP ⇔ ◻UNP. Then, replace the ◻UNP in ◻◻UNP with ¬UNP, and therefore conclude ◻¬UNP . So, at this point, we have concluded that ◻¬UNP and also that ◻UNP. So, you can conclude that, __under these assumptions__, that ◻⊥ . So, under the assumption that there is a statement UNP such that UNP ⇔ ¬◻UNP , and the additional assumption that ¬UNP, you can conclude that ◻⊥. ] Indeed. If a system admits a statement UNP, (and the system is strong enough to do the appropriate reasoning) (and peano arithmetic and such does admit such a statement UNP), then within the system, you can show that ¬UNP implies ◻⊥. I.e. "if the statement that claims it cannot be proven, can be proven, then the system proves a contradiction". This is entirely normal, and does not overturn anything. However! While the assumption that ¬UNP allows us to derive ◻⊥, it does not allow us to derive ⊥. We have __not__ shown that ¬UNP → ⊥, we have only shown that ¬UNP → ◻⊥. Therefore, this is not justification in appealing to proof by contradiction, and concluding UNP (nor ◻UNP).

bloak 5y ago
I've not read ProfHewitt's argument, so I'm just looking at your summary. If ◻P means "P is a proposition that is formally provable within some implicit formal system" (perhaps there should be a subscripted letter to show which formal system because there are an infinite number of them), then I don't understand what ◻◻UNP means, because ◻UNP is not a proposition of the implicit formal system.
- chriswarbo 5y ago
  > If ◻P means "P is a proposition that is formally provable within some implicit formal system" (perhaps there should be a subscripted letter to show which formal system because there are an infinite number of them) It doesn't mean that. The formal system is explicit: it's the system we're using to write statements like `◻P` (it's a form of modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic ).

dandanua 5y ago

That book doesn't touch any nondeterministic behavior at all. So, the nondeterministic extension of the Church-Turing Thesis is absolutely irrelevant here. Your other cited "developments" seem senseful only in your personal universe.

arethuza 5y ago
Yeah - its a long time since I studied this kind of stuff but I'm pretty sure the Church–Turing thesis doesn't say anything about non-determinism or not - being more relevant to complexity than computability?
- dandanua 5y ago
  The original thesis concerns only computable functions, which are deterministic by definition. It doesn't even consider their complexity. There are extended variations of the thesis, though. The complexity variation means that any computable function in one model of computation can have only a polynomial slowdown factor in comparison with another model of computation. It's believed to be false since the raise of quantum computations.
  - ProfHewitt 5y ago
    Nondeterministic Turing Machines were introduced very early and became the basis for the Church/Turing Thesis. An important complexity result is that in important applications, a digital implementation can be hundreds of times faster that a parallel lambda expression. Consequently, the lambda calculus cannot be a practical foundation for computing. See the following for more information: "An Actor Application Can Be Hundreds of Times Faster Than a Parallel Lambda Expression" https://professorhewitt.blogspot.com/2021/03/an-actor-application-can-be-hundreds-of.html https://professorhewitt.blogspot.com/2021/03/an-actor-applic...
- ProfHewitt 5y ago
  The Church/Turing Thesis is that all computation can be performed by a nondeterministic Turing Machine. The Thesis is false because there are digital computations that cannot be performed by a nondeterministic Turing Machine. See the following article on how to formalize all of digital computation: "Physical Indeterminacy in Digital Computation" https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566

ganafagol 5y ago

I'm having trouble understanding whether you are (1) a troll hiding behind Carl Hewitts name using a veil of CS lingo that's just complex enough to appear legit but is actually nonsense, or (2) actually Carl Hewitt losing his mind with a bunch of nonsense, or (3) actually Carl Hewitt who is on to something big and the world has just not caught up with you. To convince us of (3), have your theories been discussed at related conferences and what does the community make of them?

ivanbakel 5y ago
Having skimmed through the paper accessible at the end of the first link, I am leaning towards (1). It contains a barrage of eye-assaulting notation, lots of digressions and repetition, and basically no formal substance (which, for a logic/computation paper, is bizarre).
- emmelaich 5y ago
  His WP talk page is a shit-show. I'm leaning towards 2. https://en.wikipedia.org/wiki/Talk:Carl_Hewitt https://en.wikipedia.org/wiki/Talk:Carl_Hewitt https://en.wikipedia.org/wiki/Talk%3ACarl_Hewitt%2FArchive_2 https://en.wikipedia.org/wiki/Talk%3ACarl_Hewitt%2FArchive_2 (to disclose, I am not qualified to actually judge the arguments)
  - ProfHewitt 5y ago
    As is common with many social media platforms, Wikipedia has huge problems with accountability :-( It's not worthwhile to go into the whole sordid story on HN.
- ProfHewitt 5y ago
  Sorry that mathematical notation is causing you problems. How do you see the article lacking in formal substance?
  - ganafagol 5y ago

jkhdigital 5y ago

Ignore the downvotes: there is value in reading and attempting to understand some of this material, despite the inflammatory way the claims are made. Carl Hewitt is presumably in his 70s, so I'll forgive him for being an old man who probably doesn't give a shit what people think. In particular, I find the discussion of "paradox" attacks to be quite illuminating. Bertrand Russell attempted to remove self-referential and self-applicable paradoxes through the embellishments of types and orders. Hewitt argues that Gödel basically "cheated" in his proofs because the Diagonalization Lemma violated restrictions on orders. I'm not qualified to evaluate that argument on the basis of mathematical reasoning, but I do believe it points to a mismatch between the way computation is modeled in the abstract and the way it happens in reality. In the purely abstract world of natural numbers, there's really only one kind of thing: the natural number. Statements about natural numbers can be represented by natural numbers, statements about statements about natural numbers can also be represented by natural numbers, etc. While a given natural number can be parsed to compute if it is a valid encoding of a proposition of a certain order, it is always and forever a natural number and nothing else. However, I'm not entirely convinced that this captures the nature of computation in reality. When computation is embodied in a physical system, is it possible that the output of some computation can itself manifest computational properties that are not mere compositions of the lower level computational model? Where the interactions between the "higher level" objects simply follow a different set of rules and thus form the foundation of a new formalism? The notion of types seems to be a way to capture this, by introducing the possibility of distinguishing a "thing" from its abstract representation or description. If everything exists only within the world of the abstract representation, then a thing is indeed no different from its description, as any manipulation of the thing is equivalent to some manipulation of its description. But when the thing is, in fact, a physical object, it is clear that construction of the thing can fundamentally alter the model of computation. Why is this? I suspect that it is because there are no "pure" or "inert" abstractions in the real world; everything is in fact performing computation all the time. So physical constructions are not just compositions of objects, but also compositions of the computational capabilities of those objects. I realize this probably sounds like navel-gazing at this point, but sometimes that can be a useful activity.

ProfHewitt 5y ago

amgreg 5y ago

I am disappointed at several comments on this thread. Professor Hewitt, I personally think you've enriched the community by putting these claims here. They've led me to read more about several things, which I will list here for anyone else who might be looking for related topics: The difference between indeterminism and nondeterminism, bounded and unbounded nondeterminism, the actor model of computation, local arbitration versus global consensus, and state machines versus configuration-based computation. You've responded to the ad hominem attacks with class. I hope you do not take them as a reflection of the HN community at large; please keep coming back and posting (provocatively) as you have done, because it induces learning.

ProfHewitt 5y ago
Thank you very much for your warm words. Of course, I sometimes make mistakes :-( However, I do try to learn from them!
- ProfHewitt 5y ago
  PS. Also thanks for picking up on important topics including "indeterminism and nondeterminism, bounded and unbounded nondeterminism, the Actor model of computation, local arbitration versus global consensus, and state machines versus configuration-based computation."