4 ms·

Development of Lambda Calculus [Church 1931] and Turing Machine [Turing 1936] were fundamental achievements. However, they are inadequate models of computati

Development of Lambda Calculus [Church 1931] and Turing Machine [Turing 1936] were fundamental achievements. However, they are inadequate models of computation because there are digital computations they cannot implement. See the following for an example: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021

kamray23 5y ago
Only true for nondeterministic systems. Which all computers are as there is physical nondeterminism. However, it can (mostly) be ignored in any practical application of these theories, because the chances of you ending up in a nondeterministic computation at all are minute, never mind an unbounded one. And we are talking about practical applications here. Also, isn't that your own paper?
- ProfHewitt 5y ago
  Many-core computer systems and networked computer systems depend crucially on indeterminacy in order to gain performance. See the following https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
  - wizzwizz4 5y ago
    Many-core and networked computer systems fight indeterminacy. My networking algorithms would be a lot simpler if I could guarantee that everything operated in lockstep; the fact that I have to discard lockstep to get performance is because lockstep is a high-cost abstraction over a high-entropy (so, basically non-deterministic) underlying reality, not because indeterminacy is somehow inherently better. It's a concession.
    - ProfHewitt 5y ago
      A concession to the physical world?
      - wizzwizz4 5y ago
        For networking, yes. For multicore, it's merely a concession to the fact that instructions on my architecture are variable-length, and there's a transparent cache mechanism (requiring knowledge of memory access patterns, which requires knowing the result of the computation ahead of time).
        ProfHewitt 5y ago
        Because arbiters are used in communications among cores, a many-core computer has inherent indeterminacy.
        wizzwizz4 5y ago
        Not necessarily? If you have a real-time OS and you write your program well, you can synchronise timings and have cores send messages to each other without queues. It's hard to write fast code that does that, but in narrow circumstances, it's possible (I'm thinking embedded applications) – and when it is possible, it's faster than the equivalent algorithm with indeterminacy. Indeterminacy slows things down. It's a concession.
        ProfHewitt 5y ago
        Indeterminacy using many=cores speeds up processing. Enforced determinacy slows down processing.
        wizzwizz4 5y ago
        And natural determinacy, if you can get it, speeds up processing more than indeterminacy. The useful question is “what's the lowest-level model I can usefully use?”, not “can I do it with indeterminacy?”. Do you think the above statement is wrong? If so, why?
        ProfHewitt 5y ago
- YeGoblynQueenne 5y ago
  It's fine to link to one's own work when it's the poitn of the discussion, I'm pretty sure.
tsimionescu 5y ago
I've tried really hard to understand which part of that paper is an example of a computation that a Turing machine couldn't implement, and I have been completely unable to do so. I will say that the writing in the paper is in serious need of some basic copy editing - it is full of typos, repeated phrases and entire paragraphs (especially in the abstract).
- ProfHewitt 5y ago
  What exactly are the typos? Which paragraph is repeated?
  - tsimionescu 5y ago
    The repeated paragraphs are in the abstract on the site, not in the actual pdf. Here is a sample: > “Monster” is a term introduced in [Lakatos 1976] for a mathematical construct that introduces inconsistencies and paradoxes. Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. Monsters can lurk long undiscovered. For example, that “theorems are provably computational enumerable” [Euclid approximately 300 BC] is a monster was only discovered after millennia when [Church 1934] used it to identify fundamental inconsistency in the foundations of mathematics that is resolved in this article. > Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. This article explains how the theories Actors and Ordinals recraft classical foundations without limiting mathematical power. > Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. Computer Science brings new concerns and considerations to foundations beyond earlier work requiring new machinery. This article explains how the theories Actors and Ordinals recraft classical foundations without limiting mathematical power. > “Monster” is a term introduced in [Lakatos 1976] for a mathematical construct that introduces inconsistencies and paradoxes. Since the very beginning, monsters have been endemic in foundations. They can lurk long undiscovered. For example, that "theorems are provably computational enumerable" [Euclid approximately 300 BC] is a monster was only discovered after millennia when [Church 1934] used it to identify fundamental For typos in the actual PDF, here are a few : - teams of Wrens (female Naval Officers) operated large-scale simulations in [sic!] that discovered ways to defeat U-boat attacks that were crippling Britain. - The reason that in practice that [sic!] an Actor can be hundreds of times faster is that in order to carry out a concurrent computation, the parallel [...] - close request when received, send [...] [not a typo, just strange phrasing?] - if it is not recorded as that the engine is [...] - Actor event induction (cf. [Turing 1949]) can used to prove [...] - Suppose to obtain a contradiction that there is [...]

kamray23 5y ago

Only true for nondeterministic systems. Which all computers are as there is physical nondeterminism. However, it can (mostly) be ignored in any practical application of these theories, because the chances of you ending up in a nondeterministic computation at all are minute, never mind an unbounded one. And we are talking about practical applications here. Also, isn't that your own paper?

ProfHewitt 5y ago
Many-core computer systems and networked computer systems depend crucially on indeterminacy in order to gain performance. See the following https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
- wizzwizz4 5y ago
  Many-core and networked computer systems fight indeterminacy. My networking algorithms would be a lot simpler if I could guarantee that everything operated in lockstep; the fact that I have to discard lockstep to get performance is because lockstep is a high-cost abstraction over a high-entropy (so, basically non-deterministic) underlying reality, not because indeterminacy is somehow inherently better. It's a concession.
  - ProfHewitt 5y ago
    A concession to the physical world?
    - wizzwizz4 5y ago
      For networking, yes. For multicore, it's merely a concession to the fact that instructions on my architecture are variable-length, and there's a transparent cache mechanism (requiring knowledge of memory access patterns, which requires knowing the result of the computation ahead of time).
      - ProfHewitt 5y ago
        Because arbiters are used in communications among cores, a many-core computer has inherent indeterminacy.
        wizzwizz4 5y ago
        Not necessarily? If you have a real-time OS and you write your program well, you can synchronise timings and have cores send messages to each other without queues. It's hard to write fast code that does that, but in narrow circumstances, it's possible (I'm thinking embedded applications) – and when it is possible, it's faster than the equivalent algorithm with indeterminacy. Indeterminacy slows things down. It's a concession.
        ProfHewitt 5y ago
        Indeterminacy using many=cores speeds up processing. Enforced determinacy slows down processing.
        wizzwizz4 5y ago
        And natural determinacy, if you can get it, speeds up processing more than indeterminacy. The useful question is “what's the lowest-level model I can usefully use?”, not “can I do it with indeterminacy?”. Do you think the above statement is wrong? If so, why?
        ProfHewitt 5y ago
YeGoblynQueenne 5y ago
It's fine to link to one's own work when it's the poitn of the discussion, I'm pretty sure.

tsimionescu 5y ago

I've tried really hard to understand which part of that paper is an example of a computation that a Turing machine couldn't implement, and I have been completely unable to do so. I will say that the writing in the paper is in serious need of some basic copy editing - it is full of typos, repeated phrases and entire paragraphs (especially in the abstract).

ProfHewitt 5y ago
What exactly are the typos? Which paragraph is repeated?
- tsimionescu 5y ago
  The repeated paragraphs are in the abstract on the site, not in the actual pdf. Here is a sample: > “Monster” is a term introduced in [Lakatos 1976] for a mathematical construct that introduces inconsistencies and paradoxes. Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. Monsters can lurk long undiscovered. For example, that “theorems are provably computational enumerable” [Euclid approximately 300 BC] is a monster was only discovered after millennia when [Church 1934] used it to identify fundamental inconsistency in the foundations of mathematics that is resolved in this article. > Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. This article explains how the theories Actors and Ordinals recraft classical foundations without limiting mathematical power. > Euclid, Richard Dedekind, Gottlob Frege, Bertrand Russell, Kurt Gödel, Ludwig Wittgenstein, Alonzo Church, Alan Turing, and Stanisław Jaśkowski all had issues with mathematical monsters as discussed in this article. Computer Science brings new concerns and considerations to foundations beyond earlier work requiring new machinery. This article explains how the theories Actors and Ordinals recraft classical foundations without limiting mathematical power. > “Monster” is a term introduced in [Lakatos 1976] for a mathematical construct that introduces inconsistencies and paradoxes. Since the very beginning, monsters have been endemic in foundations. They can lurk long undiscovered. For example, that "theorems are provably computational enumerable" [Euclid approximately 300 BC] is a monster was only discovered after millennia when [Church 1934] used it to identify fundamental For typos in the actual PDF, here are a few : - teams of Wrens (female Naval Officers) operated large-scale simulations in [sic!] that discovered ways to defeat U-boat attacks that were crippling Britain. - The reason that in practice that [sic!] an Actor can be hundreds of times faster is that in order to carry out a concurrent computation, the parallel [...] - close request when received, send [...] [not a typo, just strange phrasing?] - if it is not recorded as that the engine is [...] - Actor event induction (cf. [Turing 1949]) can used to prove [...] - Suppose to obtain a contradiction that there is [...]