4 ms·

> You know, the moment I saw a NAND gate schematic, my mind opened to an amazing revelation: we don't need both zeros and ones, just zeros and NAND gates! The n

> You know, the moment I saw a NAND gate schematic, my mind opened to an amazing revelation: we don't need both zeros and ones, just zeros and NAND gates! The number one is nothing but a zero, duplicated into the two inputs of a NAND gate. This is not as absurd as you think it is. The most commonly used definition of the natural numbers (https://en.wikipedia.org/wiki/Peano_axioms#Formulation https://en.wikipedia.org/wiki/Peano_axioms#Formulation) is structured in a way similar to your description: we have a single explicitly declared natural number (zero), and all other natural numbers are defined as a sequence of function applications on zero (ie 4 is defined as S(S(S(S(zero))))). Our notation for numbers is just "syntactic sugar" on top of this representation: useful when doing practical work with numbers, but only a hindrance when you're studying the concept of "number" itself. Analogously, in programming language theory (studying the properties of programming languages moreso than trying to do program things in them), we often prove properties of languages by studying extremely frugal, tiny languages (often called "calculi"), that only have the absolute minimum primitive constructs. Realizing that a construct can be expressed as "syntactic sugar" on top of a simpler one (objects on top of closures, for instance), is useful in this setting because it reduces the number of cases in proofs.

stopachka 6y ago
Fantastic explanation ookdatnog, thank you!
fhjfyjfgnh 6y ago
Except that you can't define an NAND gate without defining an output voltage for each of 0 and 1. You can't bootstrap +5V into existence ...and for that matter you can't define a NAND gate without specifying what input voltage will be interpreted as a 1. It is quite as ridiculous as kazinator intended. But great mansplanation, carry on.
- LudwigNagasena 6y ago
  But it doesn’t matter what you use to bootstrap something because we talk about abstractions. And it is absolutely true that NAND an F form a functionally complete set of gates. > But great mansplanation, carry on. What a weird way to be overtly sexist when you don’t even know the genders of the people involved.
- ookdatnog 6y ago
  You can define logic circuits abstractly, without referring to their implementation in electronics at all. Even if you insist on defining them in terms of electronics, I don't think there's a significant difference between assigning some meaning to an arbitrary voltage vs assigning some meaning to an arbitrary squiggle on a piece of paper.
ithinkso 6y ago
This touches on an interesting topic I've been thinking about for quite some time now. I have a somewhat reverse feeling about the definition of natural numbers (or for that matter, about the 'foundation of mathematics' as in ZFC set theory or whatever you want to choose) than you've presented above. Those definitions were developed after we had something useful in order to 'codify' it and make it more precise. They are not, in my opinion, a basic blocks that the rest is built from but an added layer of abstraction on top of whathever it is you're defining. I don't mean I don't understand set theory and the role it has, or advocating for any other system, I absolutely love it. What I mean is, in practical things (programming languages etc.), it feels a bit counter-productive to me to reduce them to the simplest possible definitions/terms (that have to fit to the particular use case by definition), declaring that a building block and then explaining every other concept in those terms as if it was a proof that we have trully found a foundation and the rest is just a 'syntactic sugar' edit: You all probably know this famous gif of a ballerina that can rotate to the left or to the right depending on how you think about it. After writing the above post the notion of S(S(S(S(0)))) keeps flipping in my brain between being an abstraction of and simplification of natural numbers. It's weird.
- ookdatnog 6y ago
  I agree with what you're saying, actually. I think these questions require drilling down to philosophical questions such as "what are numbers", "what is the essence of 'number'", "are numbers even real", etc. So I'll give it a go and be shamelessly long-winded about it :) I think that numbers, set theory, programming languages, etc, are all abstractions. Forming abstractions is a mental tool associated with our ability for language: we spot a pattern and we give that pattern a name. Once we've given it a name, we can talk _about_ the abstract concept as a subject of our statements. Perhaps the simplest form of abstraction we're capable of is "categorization". Ie we see a pointy-eared small animal that makes meowing sounds, we another one, and another one, ... and even though none of them are identical, our brain picks up on certain patterns in these creatures. We know that when we next see one of them, we can expect certain behaviors. So we give it a name, let's say, "cat", and now we can talk about the abstract concept of "cat" without referring to any specific individual cat. To see how big a deal this is, I find it useful to remember that cats aren't explicitly defined in the fabric of the universe, like they would be in a computer program (where we'd have a "Cat" data structure or object, usually), they're just emergent behavior of interacting molecules. But we can do more, we can also abstract out properties of objects. We can see that some frogs have a similar color to the leaves of most trees, so we can give this leaf-color a name, "green", and talk about the abstract concept of "green" without referring to a specific green thing. You can just say "I like green" (no one will ask you "a green what?"), or "mixing green and blue makes cyan" (no one will ask "mixing green and blue what makes cyan what?"). And then we also have "chunking", where we can talk about sets of objects as objects themselves. So we can talk about "a herd of sheep" as a singular thing. Our ability to abstract out properties of objects also applies to these chunked concepts. One property of a set of objects is "quantity". Speculation ahead. Initially we probably only had fairly vague terms to talk about quantity, perhaps individual words for small quantities (one, two and three, maybe), and after that it's just "many". But it seems we figured out pretty fast that counting sheep, counting apples, or counting pebbles are really in some sense "the same thing", so we might have first learned to count through some unary "notation" even though we had no names for quantities. We'd make carvings into bone or carry a bag of pebbles, one carving or one pebble for each sheep in our herd. Then we notice that certain operations on these quantities are also all "the same": it doesn't matter whether you're adding pebbles, sheep, carvings, ... you're always doing the same thing. So after a while we start using these operations to define bigger numbers (the French still call the number 80 "quatre-vingts" or "four twenties"). Now all numbers become nameable, and eventually we streamline and standardize these names. So now we have a name for every number, and we can talk about "thirty-two" without getting back a confused reply "thirty-two what?". And we can talk about operations on these numbers, like addition, multiplication, etc, but our hunger for abstraction isn't satiated at all. Since now we can talk about operations, we can also talk about properties of operations, so we notice that you can flip the arguments of additions and multiplications, and we give that property a name, commutativity, and we go on to invent abstract algebra. After doing maths for a few thousand years we start looking into patterns into the different, disparate branches of maths at the time (geometry, number theory, logic, etc), and notice that the common pattern is that all of them are doing deductive reasoning, and that should be modellable by logic. So we abstract out the common bits and come up with set theory and proof theory and the like. And in that process we notice that number theory has unnecessarily many axioms and Peano figures out we can just use induction to define the set of natural numbers. So yes, our intuition for numbers precedes Peano's definition by millennia or far more than millennia. But I'd say that's how it goes for _every_ definition. We always start by noticing some pattern, which initially we can't quite put our finger on (for example, Leibniz had a vague intuition that a lot of work in mathematics was in some sense so mechanical that one should be able to have a machine do it; he couldn't quite define computation yet but his hunch was spot-on), and then we try to refine our thoughts and come up with a definition. In that sense, I don't think it's more meaningful to worry about the "true nature" of a number (the Peano definition, or some other notation?) than it is to worry about the "true nature" of the color red (is it its wavelength on the electromagnetic spectrum? but a wavelength can be expressed as a number; so is the essence of red just a number? or its RGB value, which is linked to how humans perceive color?). Both numbers and colors are abstractions, and abstractions are mental tools. They are a means to an end: to make sense of the world and communicate about it to other humans. And we use just use the tool that is most helpful given the problem at hand. For most practical applications we're going to use a notation that's compact and easily manipulated (Arabic numerals), but when we're studying the foundations of mathematics, it's more sensible to reduce everything to its smallest, most elegant definition possible. Neither view is "more true" than the other, in both cases you're doing no more than naming patterns in herds of sheep and piles of apples.
EsotericAlgo 6y ago
As a compliment for those following the Wikipedia rabbit hole, the repeated function application To represent the natural numbers is referred to as https://en.m.wikipedia.org/wiki/Church_encoding#Church_numerals https://en.m.wikipedia.org/wiki/Church_encoding#Church_numer.... One of those calculi is lambda calculus (often extended with some syntactic niceties in PL research)

stopachka 6y ago

Fantastic explanation ookdatnog, thank you!

fhjfyjfgnh 6y ago

Except that you can't define an NAND gate without defining an output voltage for each of 0 and 1. You can't bootstrap +5V into existence ...and for that matter you can't define a NAND gate without specifying what input voltage will be interpreted as a 1. It is quite as ridiculous as kazinator intended. But great mansplanation, carry on.

LudwigNagasena 6y ago
But it doesn’t matter what you use to bootstrap something because we talk about abstractions. And it is absolutely true that NAND an F form a functionally complete set of gates. > But great mansplanation, carry on. What a weird way to be overtly sexist when you don’t even know the genders of the people involved.
ookdatnog 6y ago
You can define logic circuits abstractly, without referring to their implementation in electronics at all. Even if you insist on defining them in terms of electronics, I don't think there's a significant difference between assigning some meaning to an arbitrary voltage vs assigning some meaning to an arbitrary squiggle on a piece of paper.

ithinkso 6y ago

This touches on an interesting topic I've been thinking about for quite some time now. I have a somewhat reverse feeling about the definition of natural numbers (or for that matter, about the 'foundation of mathematics' as in ZFC set theory or whatever you want to choose) than you've presented above. Those definitions were developed after we had something useful in order to 'codify' it and make it more precise. They are not, in my opinion, a basic blocks that the rest is built from but an added layer of abstraction on top of whathever it is you're defining. I don't mean I don't understand set theory and the role it has, or advocating for any other system, I absolutely love it. What I mean is, in practical things (programming languages etc.), it feels a bit counter-productive to me to reduce them to the simplest possible definitions/terms (that have to fit to the particular use case by definition), declaring that a building block and then explaining every other concept in those terms as if it was a proof that we have trully found a foundation and the rest is just a 'syntactic sugar' edit: You all probably know this famous gif of a ballerina that can rotate to the left or to the right depending on how you think about it. After writing the above post the notion of S(S(S(S(0)))) keeps flipping in my brain between being an abstraction of and simplification of natural numbers. It's weird.

ookdatnog 6y ago
I agree with what you're saying, actually. I think these questions require drilling down to philosophical questions such as "what are numbers", "what is the essence of 'number'", "are numbers even real", etc. So I'll give it a go and be shamelessly long-winded about it :) I think that numbers, set theory, programming languages, etc, are all abstractions. Forming abstractions is a mental tool associated with our ability for language: we spot a pattern and we give that pattern a name. Once we've given it a name, we can talk _about_ the abstract concept as a subject of our statements. Perhaps the simplest form of abstraction we're capable of is "categorization". Ie we see a pointy-eared small animal that makes meowing sounds, we another one, and another one, ... and even though none of them are identical, our brain picks up on certain patterns in these creatures. We know that when we next see one of them, we can expect certain behaviors. So we give it a name, let's say, "cat", and now we can talk about the abstract concept of "cat" without referring to any specific individual cat. To see how big a deal this is, I find it useful to remember that cats aren't explicitly defined in the fabric of the universe, like they would be in a computer program (where we'd have a "Cat" data structure or object, usually), they're just emergent behavior of interacting molecules. But we can do more, we can also abstract out properties of objects. We can see that some frogs have a similar color to the leaves of most trees, so we can give this leaf-color a name, "green", and talk about the abstract concept of "green" without referring to a specific green thing. You can just say "I like green" (no one will ask you "a green what?"), or "mixing green and blue makes cyan" (no one will ask "mixing green and blue what makes cyan what?"). And then we also have "chunking", where we can talk about sets of objects as objects themselves. So we can talk about "a herd of sheep" as a singular thing. Our ability to abstract out properties of objects also applies to these chunked concepts. One property of a set of objects is "quantity". Speculation ahead. Initially we probably only had fairly vague terms to talk about quantity, perhaps individual words for small quantities (one, two and three, maybe), and after that it's just "many". But it seems we figured out pretty fast that counting sheep, counting apples, or counting pebbles are really in some sense "the same thing", so we might have first learned to count through some unary "notation" even though we had no names for quantities. We'd make carvings into bone or carry a bag of pebbles, one carving or one pebble for each sheep in our herd. Then we notice that certain operations on these quantities are also all "the same": it doesn't matter whether you're adding pebbles, sheep, carvings, ... you're always doing the same thing. So after a while we start using these operations to define bigger numbers (the French still call the number 80 "quatre-vingts" or "four twenties"). Now all numbers become nameable, and eventually we streamline and standardize these names. So now we have a name for every number, and we can talk about "thirty-two" without getting back a confused reply "thirty-two what?". And we can talk about operations on these numbers, like addition, multiplication, etc, but our hunger for abstraction isn't satiated at all. Since now we can talk about operations, we can also talk about properties of operations, so we notice that you can flip the arguments of additions and multiplications, and we give that property a name, commutativity, and we go on to invent abstract algebra. After doing maths for a few thousand years we start looking into patterns into the different, disparate branches of maths at the time (geometry, number theory, logic, etc), and notice that the common pattern is that all of them are doing deductive reasoning, and that should be modellable by logic. So we abstract out the common bits and come up with set theory and proof theory and the like. And in that process we notice that number theory has unnecessarily many axioms and Peano figures out we can just use induction to define the set of natural numbers. So yes, our intuition for numbers precedes Peano's definition by millennia or far more than millennia. But I'd say that's how it goes for _every_ definition. We always start by noticing some pattern, which initially we can't quite put our finger on (for example, Leibniz had a vague intuition that a lot of work in mathematics was in some sense so mechanical that one should be able to have a machine do it; he couldn't quite define computation yet but his hunch was spot-on), and then we try to refine our thoughts and come up with a definition. In that sense, I don't think it's more meaningful to worry about the "true nature" of a number (the Peano definition, or some other notation?) than it is to worry about the "true nature" of the color red (is it its wavelength on the electromagnetic spectrum? but a wavelength can be expressed as a number; so is the essence of red just a number? or its RGB value, which is linked to how humans perceive color?). Both numbers and colors are abstractions, and abstractions are mental tools. They are a means to an end: to make sense of the world and communicate about it to other humans. And we use just use the tool that is most helpful given the problem at hand. For most practical applications we're going to use a notation that's compact and easily manipulated (Arabic numerals), but when we're studying the foundations of mathematics, it's more sensible to reduce everything to its smallest, most elegant definition possible. Neither view is "more true" than the other, in both cases you're doing no more than naming patterns in herds of sheep and piles of apples.

EsotericAlgo 6y ago

As a compliment for those following the Wikipedia rabbit hole, the repeated function application To represent the natural numbers is referred to as https://en.m.wikipedia.org/wiki/Church_encoding#Church_numerals https://en.m.wikipedia.org/wiki/Church_encoding#Church_numer.... One of those calculi is lambda calculus (often extended with some syntactic niceties in PL research)