5 ms·

This is why I've never understood what it is. I see words, (and it's not that I don't understand what those words mean) but I simply don't know what is meant by

This is why I've never understood what it is. I see words, (and it's not that I don't understand what those words mean) but I simply don't know what is meant by them arranged in this way. There's some understanding that I'm fundamentally lacking which I've been searching to correct for years. I've put it down to "Math" which seems to be a whole impenetrable language itself. A language that my lack of understanding of (despite many unguided attempts) means I'll continue to be downvoted and snorted at when I say I still don't understand what a Turing machine or a monad actually is.

caspper69 7y ago
You are correct; you can learn what these things "are," but without at least some of the mathematics, it's going to be tough to fully grasp. And yes, mathematics is a language; it is the language for modelling the phenomena we experience in the world, including the non-physical (contracts, data / counting, etc.). I so, so, so wish that people were taught that mathematics is a language of relationships rather than one of rote numerical calculation. I think more people would stick with it. It's a shame, because the doors it opens are huge.
- The_rationalist 7y ago
  I don't quite understand how mathematics are more adapted to model the world than a programming language.
  - caspper69 7y ago
    The short answer, they are not; The long(er) answer? Mathematics are more limited, and thus, at least on the surface, provide a more rigid model. Plus, we have about 4500 years worth of equations that we know to be accurate; not so true for C or any other programming language. Plus, we can model all the way down in mathematics, as it is more abstract in nature. The long(est) answer? It's turtles all the way down.
    - kd5bjo 7y ago
      > Mathematics are more limited The fundamental point of the Church-Turing thesis is to show that everything computers can do can be described by mathematics, so any programing language has either the same or less power than math. They are certainly easier to use for many problems, though. Additionally, Gödel showed that there are true statements that can be described but not proven by math, ao it can never be a perfect model of the real world.
      - progval 7y ago
        > Additionally, Gödel showed that there are true statements that can be described but not proven by math, ao it can never be a perfect model of the real world. I assume you are refering to Gödel's incompleteness theorems; but this is not what they "say". What they say is that any formal system powerful enough to contain basic arithmetic is either inconsistent (ie. it can both prove and disprove a particular theorem) or incomplete (ie. cannot either prove or disprove all theorems). If you take the ZF set theory, for example, it is incomplete, because some statements cannot be either proved or disproved within ZF, such as the Axiom of Choice (AC) or Zorn's Lemma. However, that doesn't imply that ZF cannot be "a perfect model of the real world", because the AC is irrelevant in a the real world, because the AC only applies to infinite sets, which do not exist in the real world.
      - The_rationalist 7y ago
        Gödel theorem does not say anything about the real world. Mathematics are a superset of physics as they allow to explain all possible universes not just our. I've yet to see one concrete statement that ZFC can't explain. There's a list of such statements on wiki if I remember well.
  - mcguire 7y ago
    Short pithy answer: Exact real arithmetic is still an open research problem. Slightly longer answer: To the extent that they are formal languages, they both have the same ability to express things. More philosophical answer: Mathematics has a tradition of extension. Have a new idea you want to express as concisely as possible because you are going to be using it a lot? Grab a handful of Greek letters, symbols, funny fonts, and random other typography, and go to town. Outside of Lisp,[1] this flexibility is hard to do in most programming languages. [1] But inside a dog, it's too dark to read.
kd5bjo 7y ago
Part of what makes this one hard is that it’s an essential foundational step but rarely used in practice— everything that’s actually useful about Turing machines is several levels removed from symbols on a tape. Probably the most visible outcomes of this work is complexity analysis of algorithms- you can’t talk about how much computational effort you need to do something until you have an agreed measure of computational effort. How many steps or tape cells a Turing machine would need is that fundamental measure, in a similar way to how the speed of light is our fundamental measure of velocity; they’re essential to our understanding of the field but not used on a day-to-day basis. Instead, we use more convenient ones that are themselves derived from the first-principles units.
continuational 7y ago
In programming languages, `Monad` is just an interface with the methods `map`, `flatten` and `pure`. As with many other interfaces, there are a few rules in the comments that implementations are expected to adhere to.
chewxy 7y ago
OK, let me try. Consider the notion of an algorithm. You are probably familiar with an algorithm: a series of steps to be completed by a computer (aka a person). This is the launch point for what a Turing machine is. Turing asks the question: if there exists a machine that can slavishly follow instructions, what can such a machine do, and what can such a machine NOT do? To answer this question without invoking the AI problem, Turing started with the simplest possible set of objects to work with: binary numbers. A simple machine then would be a machine that reads a "tape" of binary numbers. The machine is simple, so it can only read one number at a time. Based on the number read, the machine may either move the tape left (reading the next number), move the tape right (read the previous number), replace the digit on the current cell, or halt. You can see why such a machine is considered simple: The range of inputs and the action space is VERY limited. And yet despite its simplicity, it's shown that such a simple machine can do addition. Specifically it can perform computation on recursively enumerable problems. It is in this very narrow and specific sense that Church's Lambda Calculus and Turing's machines are considered equivalent. Modern authors tend to extend the reach of Lambda Calculus, but you should bear in mind that the Church Turing thesis is valid only for functions N->N. That is to say if a Turing Machine can calculate the result of a function that takes a natural number and returns a natural number, lambda calculus can calculate the same result, and vice versa [sidenote]. Now, having a machine that can do all that is pretty cool. Ideally you'd want to be able to describe the rules of the machine. That's called a programming language. This notion really only formalized itself way after Turing died. Aho, Ulman and gang were really the ones who made the connection between languages and automata. Wang's B machine introduced the notion of abstraction in Turing machines by adding compound features that can be translated to simple Turing machines (for example, an instruction that would be "delete the value, and move right"). This led to the study of programming languages. The family of imperative programming languages are inspired by Turing machines in this manner. [Sidenote]: If only functions of N->N are comparable for the Church Turing thesis, then why do people generalize it to all kinds of functions? A cheap trick is to say, all functions can be Gödel-string encoded. A G-string is a huge natural number that represents a function. Thus if you can find the Gödelized function, then all functions are computable by both formalisms. I find this a bit distasteful - when we compute with CPUs we don't actually compute Gödel numbers!
- 7y ago
carapace 7y ago
Maybe this will help: > Young man, in mathematics you don't understand things. You just get used to them. This was John von Neumann talking.

caspper69 7y ago

You are correct; you can learn what these things "are," but without at least some of the mathematics, it's going to be tough to fully grasp. And yes, mathematics is a language; it is the language for modelling the phenomena we experience in the world, including the non-physical (contracts, data / counting, etc.). I so, so, so wish that people were taught that mathematics is a language of relationships rather than one of rote numerical calculation. I think more people would stick with it. It's a shame, because the doors it opens are huge.

The_rationalist 7y ago
I don't quite understand how mathematics are more adapted to model the world than a programming language.
- caspper69 7y ago
  The short answer, they are not; The long(er) answer? Mathematics are more limited, and thus, at least on the surface, provide a more rigid model. Plus, we have about 4500 years worth of equations that we know to be accurate; not so true for C or any other programming language. Plus, we can model all the way down in mathematics, as it is more abstract in nature. The long(est) answer? It's turtles all the way down.
  - kd5bjo 7y ago
    > Mathematics are more limited The fundamental point of the Church-Turing thesis is to show that everything computers can do can be described by mathematics, so any programing language has either the same or less power than math. They are certainly easier to use for many problems, though. Additionally, Gödel showed that there are true statements that can be described but not proven by math, ao it can never be a perfect model of the real world.
    - progval 7y ago
      > Additionally, Gödel showed that there are true statements that can be described but not proven by math, ao it can never be a perfect model of the real world. I assume you are refering to Gödel's incompleteness theorems; but this is not what they "say". What they say is that any formal system powerful enough to contain basic arithmetic is either inconsistent (ie. it can both prove and disprove a particular theorem) or incomplete (ie. cannot either prove or disprove all theorems). If you take the ZF set theory, for example, it is incomplete, because some statements cannot be either proved or disproved within ZF, such as the Axiom of Choice (AC) or Zorn's Lemma. However, that doesn't imply that ZF cannot be "a perfect model of the real world", because the AC is irrelevant in a the real world, because the AC only applies to infinite sets, which do not exist in the real world.
    - The_rationalist 7y ago
      Gödel theorem does not say anything about the real world. Mathematics are a superset of physics as they allow to explain all possible universes not just our. I've yet to see one concrete statement that ZFC can't explain. There's a list of such statements on wiki if I remember well.
- mcguire 7y ago
  Short pithy answer: Exact real arithmetic is still an open research problem. Slightly longer answer: To the extent that they are formal languages, they both have the same ability to express things. More philosophical answer: Mathematics has a tradition of extension. Have a new idea you want to express as concisely as possible because you are going to be using it a lot? Grab a handful of Greek letters, symbols, funny fonts, and random other typography, and go to town. Outside of Lisp,[1] this flexibility is hard to do in most programming languages. [1] But inside a dog, it's too dark to read.

kd5bjo 7y ago

Part of what makes this one hard is that it’s an essential foundational step but rarely used in practice— everything that’s actually useful about Turing machines is several levels removed from symbols on a tape. Probably the most visible outcomes of this work is complexity analysis of algorithms- you can’t talk about how much computational effort you need to do something until you have an agreed measure of computational effort. How many steps or tape cells a Turing machine would need is that fundamental measure, in a similar way to how the speed of light is our fundamental measure of velocity; they’re essential to our understanding of the field but not used on a day-to-day basis. Instead, we use more convenient ones that are themselves derived from the first-principles units.

continuational 7y ago

In programming languages, `Monad` is just an interface with the methods `map`, `flatten` and `pure`. As with many other interfaces, there are a few rules in the comments that implementations are expected to adhere to.

chewxy 7y ago

OK, let me try. Consider the notion of an algorithm. You are probably familiar with an algorithm: a series of steps to be completed by a computer (aka a person). This is the launch point for what a Turing machine is. Turing asks the question: if there exists a machine that can slavishly follow instructions, what can such a machine do, and what can such a machine NOT do? To answer this question without invoking the AI problem, Turing started with the simplest possible set of objects to work with: binary numbers. A simple machine then would be a machine that reads a "tape" of binary numbers. The machine is simple, so it can only read one number at a time. Based on the number read, the machine may either move the tape left (reading the next number), move the tape right (read the previous number), replace the digit on the current cell, or halt. You can see why such a machine is considered simple: The range of inputs and the action space is VERY limited. And yet despite its simplicity, it's shown that such a simple machine can do addition. Specifically it can perform computation on recursively enumerable problems. It is in this very narrow and specific sense that Church's Lambda Calculus and Turing's machines are considered equivalent. Modern authors tend to extend the reach of Lambda Calculus, but you should bear in mind that the Church Turing thesis is valid only for functions N->N. That is to say if a Turing Machine can calculate the result of a function that takes a natural number and returns a natural number, lambda calculus can calculate the same result, and vice versa [sidenote]. Now, having a machine that can do all that is pretty cool. Ideally you'd want to be able to describe the rules of the machine. That's called a programming language. This notion really only formalized itself way after Turing died. Aho, Ulman and gang were really the ones who made the connection between languages and automata. Wang's B machine introduced the notion of abstraction in Turing machines by adding compound features that can be translated to simple Turing machines (for example, an instruction that would be "delete the value, and move right"). This led to the study of programming languages. The family of imperative programming languages are inspired by Turing machines in this manner. [Sidenote]: If only functions of N->N are comparable for the Church Turing thesis, then why do people generalize it to all kinds of functions? A cheap trick is to say, all functions can be Gödel-string encoded. A G-string is a huge natural number that represents a function. Thus if you can find the Gödelized function, then all functions are computable by both formalisms. I find this a bit distasteful - when we compute with CPUs we don't actually compute Gödel numbers!

7y ago

carapace 7y ago

Maybe this will help: > Young man, in mathematics you don't understand things. You just get used to them. This was John von Neumann talking.