4 ms·
side question : i remember a course in my logic class where our teacher showed us a programming language made of only two letters, and where all operations, num
by bsaul 6y ago
side question :
i remember a course in my logic class where our teacher showed us a programming language made of only two letters, and where all operations, numbers, etc were all defined with just those two letters. It was created by some famous logician but i can't find anything on the web about it.
Anyone here knows what that could be ?
edit : i think the lesson was showing curry's work on combinator logic..
- ummwhat 6y agoPerhaps this is related. I learned that in fact you do not need for "God made the integers". The definition of every object in mathematics can be bootstrapped from the empty set. 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".
- JadeNB 6y ago> 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}". This is not the usual von Neumann encoding (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...), so I think you may have started one level too encoded. The usual encoding puts 0 equal to the empty set, and n + 1 equal to the union of n (a set with n elements) and {n} (a singleton with 1 element). In other words, if I understand the meaning of 'Etc.', your encoding puts 0 = {Ø}, 1 = {0, Ø} = {{Ø}, Ø}, 2 = {1, Ø} = {{{Ø}, Ø}, Ø}, …, whereas the usual encoding puts 0 = Ø, 1 = 0 ∪ {0} = {Ø}, 2 = 1 ∪ {1} = {Ø, {Ø}}, …. One advantage of this latter encoding is that the set n has n elements, and that the set n is n-times nested, in the sense that longest chain of elements x ∈ y ∈ z ∈ … ∈ n has length n. It also generalises nicely to ordinals (a transfinite generalization of the natural numbers), as explained in the above link (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...).
- Rerarom 6y agoProbably it was indeed combinatory logic, but see also https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot
- andrelaszlo 6y ago'0' and '1'? Sorry :P
- a1369209993 6y agoYou can technically do it with only one character (via Godel numbering and unary), but it gets annoying fast for obvious reasons.
- lelf 6y agohttps://en.wikipedia.org/wiki/SK_combinator_calculus https://en.wikipedia.org/wiki/SK_combinator_calculus ?
- calpaterson 6y agoSounds like SKI combinators. Three combinators: S,K and I. I is technically optional. https://en.m.wikipedia.org/wiki/SKI_combinator_calculus https://en.m.wikipedia.org/wiki/SKI_combinator_calculus
- inimino 6y agoI would guess the SK combinators. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
- bsaul 6y agoThanks, that was the one. This looks like a more fundamental axiomatic than lisp meta-circular evaluator. I'm surprised it didn't give birth to more experimentation (maybe because i remember it had some very weird properties and things that looked a lot like inconsistencies..)
- arethuza 6y ago"very weird properties and things that looked a lot like inconsistencies" Any idea what they were - as my final year project of my CS degree I did an implementation of a simple purely functional programming language that macro expanded into lambda calculus and then was converted into various sets of combinators for evaluation (from SK upwards). I thought there was actually a stunning lack of weirdness and inconsistency - mind you this did also come with a stunning lack of performance! NB The trickiest bit of the whole project was writing a garbage collector so I could actually get these things to run on a shared Unix mini-computer.... Edit: Getting Y (and therefore recursion) working purely in terms of SK still amazes me.
- bsaul 6y agoI think to remember something about being able to compute the fixed point of the function x -> x+1 (that is, a number for which this function returns the same number). Our teacher showed us this function, and i think he also told us, curry reaction when people showed him this was something along the line of « well, that just means my theory is more powerful than yours, because it can express things yours can’t ». that was 20 years ago, but it made a big impression on me, so i think my memories are correct :)
- abdullahkhalids 6y agoThe language Whitespace [1] has 3 characters only: spaces, tabs and linefeeds. [1] https://en.wikipedia.org/wiki/Whitespace_(programming_language) https://en.wikipedia.org/wiki/Whitespace_(programming_langua...