How simple can a programming language be?
Вставка
- Опубліковано 11 лип 2023
- Most programming languages give you a lot of nice features to help you write code, but how many of these features can we get rid of and still be capable of doing everything we could before?
Subscribe :) - Наука та технологія
you can also do this with nand gates, wich is the gate that is more famous for having this property
Correct! I just found that NOR was easier to say :)
You can get NOT the same way, then OR & AND are obtained like with NOR, but by swapping both operator formats (so instead of (not (a nor b)) for OR, we have (not (a nand b)) for AND)
@@AByteofCode NOR gate is more popular because it takes only 2 MOS transistors to build instead of 4 for the NOR gate
@@koopalad4 You said NOR twice :)
@@AByteofCode demorgan's law 🥲 tomorrow i am going to have a exam on it... and i am going to fails because i am watching this instead of studing..
@@AByteofCodeis it possible to represent everything through AND? Interested, because AND is easily represented on macro level with "threshold" elements.
This video is basically reverse engineering the theory of computation lol, good to see an upload from this channel!
My favorite simple computation system is the SK combinator calculus. It's so cool that you can create any program with just two functions.
Agreed! Now I'm tempted to make a video on it :)
Or just 1 function with Wolfram Rule 110
@@WizardWalk hmm true! There's so many ways to do minimal computation :)
@@AByteofCodethat would be awesome! It doesn’t get nearly enough attention in the modern-day programming space
I wonder, would the lambda calculus also count as a "simple language"? All you need is abstraction, variables, and application.
I mean in essence lambda calculus has one feature: instant return functions. Can't get much simpler than that. (You don't even need variables per se, just function arguments)
SKI lambda calculus as a whole is just 3 characters + parentheses
@@perigord6281 But still three distinct operators
@@AByteofCodend you only need S and K. No free variables with these being combinators makes it in one sense simpler even than pure lambda calculus but then the programming with then looks even more complex
@@francescaerreia8859 Interesting, so how do you simulate I with SK?
1:20 as someone who’s trying to figure out how to make a node based UI with custom defined signal flow I appreciate this train of thought
Glad to hear that!
Complexity grows in direct proportion with the amount of options presented.
Congratulations, you have discovered the integrated circuit.
Although there it is typically the NAND gate.
i can see the fireship inspiration style but you have your unique touch which overpowers his keep going its good shit mijo!
Thanks for the kind words! I've been trying hard to not be too much like fireship so this is really encouraging
Never met a Chanel this concise while remaining interesting and informational, btw I like your color schemes.
I appreciate the kind words! A lot of thought went into the color scheme so I'm happy someone is finally pointing it out :D
Welcome back Byte of Code! I wonder if anyone has made an esolang that's like this...
Thank you! If nobody has, someone should! (The looping aspect would probably require some sort of visual interaction like scratch)
This video is the closest thing to playing many many hours of the game turing complete ive ever seen btw
I'd never even heard of that game before this video, so its pretty funny how similar it ended up :)
I created a very simple Turing complete laungage once:
Start with two variables that store a natural number: A and B. There are four instructions:
1. Do nothing.
2. Increase both variables by 1.
3. If A is greater than 0, decrease it by 1 and skip next K instructions.
4. Same as above, but for B.
I dont know yet what is the minimum value for K so let's say that K=100 (this means that you skip 100 instructions). The program loops around: if you go to the end then you loop back to the beggining. There is one extra Halt instruction on the and of the program. If you encode input correctly into A and B than this system is Turing complete.
I named the instructions:
1. _
2. +
3. A
4. B
Halt: H
if some one is intrested.
How would you prove the turing completeness of the language?
@@AByteofCode The standard answer is to simulate a turing machine (or other turing-equivalent systems) with it, right ? Anyway this sounds like a description of a variant of a counter machine.
@@TyphonBaalHammon Right of course, that's the simplest way of doing it. I was asking for more details about how this system in specific would simulate a TM
@@AByteofCode If you have a number in counter A, and use B as a temporary variable, you can write a program that multiplies or divides A by an arbitrary constant. Now consider the prime factorization of A: 2^a 3^b 5^c 7^d ...
Multiplying or dividing A by a prime number is equivalent to incrementing or decrementing one of those exponents (a, b, c, d, ...).
Now you can use a 2-counter machine to simulate any finite number of counters!
You can then use a pair of counters (one main counter and one scratchpad) to simulate a stack of bits: 'push 0' is doubling the counter, 'push 1' is doubling the counter and adding 1, and 'pop' is halving the counter and making a decision based on the remainder. And you can simulate arbitrarily many counters, so you can simulate arbitrarily many stacks!
You can then use a pair of stacks (one left and one right) to simulate a 2-symbol Turing machine tape - to move left, pop from the left stack and push to the right, and vice versa.
3:30 not quite, you can go one step further and reduce all those to individual transistors in different configurations, now all we are left with is boolean and mosfets :D
You got me :) I completely forgot about transistors
I know I'm coming in late, but another nice minimal system is bitwise cyclic tag (BCT). Definitely worth checking out
I'll definitively take a look! This sounds interesting :)
this guy is pretty good, he should try making functional programming videos
If you have any specific topics you'd like me to cover, feel free to mention them :)
@@AByteofCode functional programming comes with alot of jargon involved which may be too much for newbies, maybe a video explaining few of those?
@@AByteofCodegreat content btw, hope you make lots more
@@wackyator I have a video just like that in the plans but it'd be about 10 minutes long and that's a lot of work for one video. I could try to do it in a few parts
@@AByteofCodewould absolutely love that
Great content, great.
audio is really good in this video gj
Amazing!
cool video)
I think I would like you to create a virtual machine inside the java virtual machine using java itself
Pffft... NOR gates? When the Chad NAND is standing right there?
(excellent video)
NOR & NAND are very similar, I had to re-edit the whole section about logic gates because I mixed the two of them up first time :) I really just went with NOR since its easier to say
1:19 love the vsauce reference lol
you can do the same thing with nand, and I believe that how some CPUs work
Correct! I cut out the part about CPUs using this since the video was getting quite long already. For NAND just do the same this as NOR but swap the shape of how you make OR & AND
NANd also works
Are you familiar with Minecraft Redstone? Because this is basically how you needed to get _anything_ done in that environment. There is no programming language (unless you count Command Blocks), there are no packaged logical gates. All we had was NOR in the form of the Redstone Torch, and everything was built from that. We didn't even have NAND like most computation environments, at least not without building one from 2 NOR gates (and an implicit OR from just combining the wires; a trick that doesn't actually work in real electronics).
I love minecraft redstone! Im guessing NOR is done by combining the two wires and feeding it into the redstone torch for the not element?
@@AByteofCode You could do that, but I consider a proper NOR gate to be two wires into the same block with a torch on it with the wires not necessarily combined.
@@angeldude101 Right that makes a lot of sense too, it would avoid having to put repeaters in front of the redstone wires to avoid contaminating backwards
Redstone REPRESENT!!!
My years of messing with it has made me greatly favor NOR-based universal logic over NAND-based.
I remember back in the early days of Redstone figuring out how to make addressable memory and adder/subtractors. I eventually built a programmable CPU with a limited instruction set, but never made a final video about it.
I've never heard of the 10 other logic gates, does anyone have a link to somewhere where I could read about them?
I put that "10 more" since I couldn't find the symbols for each language. There doesn't seem to be many ressources about all the other gates, so if someone finds one I'd like to see it. (Maybe I should make it?)
If you have 2 binary inputs (4 possible inputs) and you want a function that is defined for each of these 4 inputs (so 4 outputs), then you have 4x4 possible functions to choose from
This image explains it well imo, if it doesn't, I guess you could pick up a copy of Digital design 5th edition and then read a bit :D
player.slideplayer.com/90/14596104/slides/slide_14.jpg
I suggest "Code: The Hidden Language of Computer Hardware and Software" by Charles Petzold. Great book explaining this and many other concepts.
@@ant1fact sound pretty interesting, I will put it on my plan to read, thanks for the suggestion!
we can go even further with a turing machine, though that's a bit more complicated
The Turing Machine is also a form of minimal computation, and the brainf**k programming language is pretty close to a simplified TM, but you still need to have multiple operators for it to work. It is simpler than spamming logic gates and it doesn't go as far as NOR/NAND
hmmm hi
I really appreciate this vsauce reference
_Technically_ there are 6 universal 2-input Logic gates, but they are all constructed from a NOT combined in some way with either AND or OR.
not (A or B): Neither (NOR)
A or notB: Converse Implication (If B, then A)
notA or B: Implication (If A, then B)
not (A and B): Mutual Exclusivity (NAND)
A and notB: Non-implication (A does not imply B)
notA and B: Converse Non-implication (B does not imply A)
Most people just point out the other of NOR & NAND so thanks for putting all of them!
@@AByteofCode I think I may have misnamed the implication gates though. It's a little brain-bending to translate the concepts of if/then to a boolean combination.
@@HansLemurson We looked at it briefly in math class and I didn't get it, so the brain bending bit is certainly true :)
The references!!
Glad to see them being noticed :)
@@AByteofCodeThey are (Fireship brain*** and Vsauce sounds)
@@cryptonative Brain*** wasn't a fireship reference, I just really like the language. However considering the similarities in style I see where you're coming from
Ah, yis. De Morgan's Law
This language would be super easy to read and write
Did you put this on 1.5x speed before uploading?
I tried putting more pauses than before but apparently not enough. Thanks for the feedback :)
C is max. easy.
You learn once, can program anything.
If you have enough time.
this reminds me a little bit of neural networks. they have also only one operation.
one could say: in the trainingsphase of the neural networks they change their source-code until the endresult is satisfying.
Isn't it NAnd (NOT AND) the basic logic gate? you can create from it everything else including NOT
Absolutely correct! NAND and NOR are both basic logic gates. I just talked about NOR because it sounds better :)
NOR gate is basically a minecraft redstone torch 😄
The torch is NOT (if you power the block its on) while NOR is a slightly more complicated contraption, but you get the idea :)
where did you run away to, bro? it's been a couple months now
Intensive school program + lack of inspiration in terms of storytelling
I'm very sorry about the lack of content, as always if you have any ideas they could be helpful
literally fireships little autistic brother... but in a good way XD
How calling someone autistic can be good?
I'll take that as a compliment :)
Out of curiosity, what gave away the autism bit?
@@AByteofCode Just a hunch XD
VSauce music :D
Or was it?
@@AByteofCode 🤔🤔🤔💤💤
@@AByteofCodethat's called "the Vsauce effect"
i have an idea for a (somehow turing complete) programming language:
instead of ascii and numbers, this works with unicode and numbers (notated u' and 'n) (oh and there's null notated as a ' )
they both are referred to as items
concatenating is the default operation (a&b)
(math works as normal with numbers)
to do an operation with unicode characters, first you take these and convert them into their unicode strings (like 𓅱 will be 13171), convert that into BASE (you can use a mixed radix to represent this number system, but good luck doing math in that system, or converting to or from base 10 by hand), then do the operation, then convert back into unicode
converting numbers and unicode symbols
you can use a null value (lack of an item) in operations, like null + null is 1,
but null × 2 is null
there is a way to crash the website the program is running on:
1. using both a number and a unicode char in the same math formula
and much more
I would've bet my left shoe you were gonna summarize it all into nand gates. I should've known you can do the same with nors smh
Never let them know your next move (actually it was that nor sounds better than nand)
λ!
You don't even need any logic when you know how to uuse electricity !
Desmos is turing complete
That sounds fun
You can immediately have two versions of this proposed language: one based on NOR, the other one based on NAND. Let the eternal war begin.
its vim vs emacs all over again
@@AByteofCode Exactly :D
And Hasklul programmers wonder why people say that you cant write anything useful in Hasklul.
I don't remember haskell being in this video
Hi
hey
Vhdl language
Just looked it up, vhdl sounds like a very interesting language (although verbose)
I need to watch Joe Rogan talk about gorillas to rest my brain after watching this
fair
SNOBOL
subleq2 a, b
Is a turing complete assembly language (en.m.wikipedia.org/wiki/One-instruction_set_computer)
Very true!