6 ms·

Turing machines are terribly inefficient, though. They may be easier to reason about than lambda calculus, but not good for practical computing purposes. Their

Turing machines are terribly inefficient, though. They may be easier to reason about than lambda calculus, but not good for practical computing purposes. Their value was in proving that logical and mathematical reasoning could be mechanized with an automatic device, something that had not been clear until then. Computing science cares a lot about building efficient processes. Thus to create real working programs, a better basis is a combination of lambda calculus for defining mathematical structures and (Von Neumann based) agent-based models for defining stateful processes. Modern programming languages are evolving to be capable of representing either model, to adapt themselves to the style more suited to the problem at hand.

kaba0 5y ago
Efficiency is not important at all when you talk about a mathematical proof. Do we really care about a proof using induction taking n or n^2 operations? For seeing whether a given statement holds true, minimizing complexity is the most important.
- TuringTest 5y ago
  > Efficiency is not important at all when you talk about a mathematical proof. Precisely, and that's the main difference between computer science and the rest of mathematics. Typically CS cares about the process to find a result, and not just its value nor the possibility or impossibility to find it.
  - bregma 5y ago
    > Typically CS cares about the process to find a result, and not just its value nor the possibility or impossibility to find it. Typically, programmers care about the process to find the result. Some programmers are computer scientists. You can not conclude that all computer scientists are programmers, so your statement is based on logical fallacy.
    - TuringTest 5y ago
      Computer science still has computational complexity theory and analysis of algorithms as sub-fields, with complexity classes and Big O notation. These very much care about the process to find results, which was the basis for my statement :-) The fallacy is on your interpretation of what I said. There are results in theoretical computer science that don't care about the efficiency in the process; the most essential are the computability theorems exploring what parts of mathematics can be computed, and what we mean by computation anyway. But the most essential part -the halting problem- was resolved long ago, so the lion's share of applications of computing science is in finding practical ways to use computers, which again needs to take efficiency into account.
- antonvs 5y ago
  > Efficiency is not important at all when you talk about a mathematical proof. Do we really care about a proof using induction taking n or n^2 operations? Efficiency and tractability of representation is also an issue, though, and mathematicians (and programmers) do care about that, a great deal. That's why the lambda calculus has been used as the basis for proof assistants such as Coq, whereas Turing machines have not.
fnrslvr 5y ago
This whole debate is always so bewildering. Programming paradigm fanboys get into heated arguments about which model is the "best" one, but actual computer science research uses myriad different models of computation, usually endeavoring to select the one that is most convenient for the given purpose. Sometimes that could mean using the lambda calculus, particularly in study of language theory and type systems. Other times that could mean some sort of black box model, such as when proving lower bounds for solving problems using specific operations (see e.g. the sorting lower bound). Yet other times, like when establishing the ground-zero of some new variety of computational hardness, I can't think of many more suitable models to cut up into pieces and embed into the substrate of some other problem than those based upon Turing machines.
- TuringTest 5y ago
  Well, computing science studies programming paradigms; so defining them and analyzing what makes them suitable for what purposes is pretty much within its scope. As I said above, it may very well be that the best usage for Turing machines is using them in mathematical proofs; where the efficiency of the computation is not a concern.
  - fnrslvr 5y ago
    Really the best usage of all the computation models we're discussing here is using them in mathematical reasoning. If you're looking to "create real working programs," then a better basis is probably going to be some combination of actual industry-grade programming languages and actual CPU architectures. This response might come off as a little facetious, but seriously, I think the idea of "founding" industrial computing languages/platforms upon theoretical research models of computation misunderstands the relationship between theory and practice. There is a relationship for sure, the research on these models usually does want to translate into real-world implications somehow, but your functional programming language is not the literal lambda calculus.
    - TuringTest 5y ago
      Certainly practical programming languages are not a one-to-one implementation of a theoretical model, but these models do create families of related languages that keep a close relationship and are separated from languages based on a different model. Each time a new theoretical model is created to represent a particular programming problem, entirely new languages are created to ease the practical approaches of building systems for the underlying problem. And it is worth keeping track of which models are good for which problems. So no, theoretical models are not good just for doing math with them, also for guiding practical usage.
deleted 5y ago
[deleted]
antonvs 5y ago
> They may be easier to reason about than lambda calculus That was a claim someone made, but it turned out to be a misunderstanding, and is incorrect. I've covered this here: https://news.ycombinator.com/item?id=27338055 https://news.ycombinator.com/item?id=27338055 (see the parent comment for quotes from Godel & Church that I'm referring to.)

kaba0 5y ago

Efficiency is not important at all when you talk about a mathematical proof. Do we really care about a proof using induction taking n or n^2 operations? For seeing whether a given statement holds true, minimizing complexity is the most important.

TuringTest 5y ago
> Efficiency is not important at all when you talk about a mathematical proof. Precisely, and that's the main difference between computer science and the rest of mathematics. Typically CS cares about the process to find a result, and not just its value nor the possibility or impossibility to find it.
- bregma 5y ago
  > Typically CS cares about the process to find a result, and not just its value nor the possibility or impossibility to find it. Typically, programmers care about the process to find the result. Some programmers are computer scientists. You can not conclude that all computer scientists are programmers, so your statement is based on logical fallacy.
  - TuringTest 5y ago
    Computer science still has computational complexity theory and analysis of algorithms as sub-fields, with complexity classes and Big O notation. These very much care about the process to find results, which was the basis for my statement :-) The fallacy is on your interpretation of what I said. There are results in theoretical computer science that don't care about the efficiency in the process; the most essential are the computability theorems exploring what parts of mathematics can be computed, and what we mean by computation anyway. But the most essential part -the halting problem- was resolved long ago, so the lion's share of applications of computing science is in finding practical ways to use computers, which again needs to take efficiency into account.
antonvs 5y ago
> Efficiency is not important at all when you talk about a mathematical proof. Do we really care about a proof using induction taking n or n^2 operations? Efficiency and tractability of representation is also an issue, though, and mathematicians (and programmers) do care about that, a great deal. That's why the lambda calculus has been used as the basis for proof assistants such as Coq, whereas Turing machines have not.

fnrslvr 5y ago

This whole debate is always so bewildering. Programming paradigm fanboys get into heated arguments about which model is the "best" one, but actual computer science research uses myriad different models of computation, usually endeavoring to select the one that is most convenient for the given purpose. Sometimes that could mean using the lambda calculus, particularly in study of language theory and type systems. Other times that could mean some sort of black box model, such as when proving lower bounds for solving problems using specific operations (see e.g. the sorting lower bound). Yet other times, like when establishing the ground-zero of some new variety of computational hardness, I can't think of many more suitable models to cut up into pieces and embed into the substrate of some other problem than those based upon Turing machines.

TuringTest 5y ago
Well, computing science studies programming paradigms; so defining them and analyzing what makes them suitable for what purposes is pretty much within its scope. As I said above, it may very well be that the best usage for Turing machines is using them in mathematical proofs; where the efficiency of the computation is not a concern.
- fnrslvr 5y ago
  Really the best usage of all the computation models we're discussing here is using them in mathematical reasoning. If you're looking to "create real working programs," then a better basis is probably going to be some combination of actual industry-grade programming languages and actual CPU architectures. This response might come off as a little facetious, but seriously, I think the idea of "founding" industrial computing languages/platforms upon theoretical research models of computation misunderstands the relationship between theory and practice. There is a relationship for sure, the research on these models usually does want to translate into real-world implications somehow, but your functional programming language is not the literal lambda calculus.
  - TuringTest 5y ago
    Certainly practical programming languages are not a one-to-one implementation of a theoretical model, but these models do create families of related languages that keep a close relationship and are separated from languages based on a different model. Each time a new theoretical model is created to represent a particular programming problem, entirely new languages are created to ease the practical approaches of building systems for the underlying problem. And it is worth keeping track of which models are good for which problems. So no, theoretical models are not good just for doing math with them, also for guiding practical usage.

deleted 5y ago

[deleted]

antonvs 5y ago

> They may be easier to reason about than lambda calculus That was a claim someone made, but it turned out to be a misunderstanding, and is incorrect. I've covered this here: https://news.ycombinator.com/item?id=27338055 https://news.ycombinator.com/item?id=27338055 (see the parent comment for quotes from Godel & Church that I'm referring to.)