There's only one issue. His understanding of Turing Complete. Sure, he has demonstrated that you can perform ALU - Arithmetic & Logic Operations within this title, but he has not demonstrated a very vital part of a Turing Machine and what it means to be Turing Complete. The type of circuitry he did with these logic gates is known commonly known as Combinatorial Logic where their outputs only rely on the incoming inputs, they hold no state. The crucial part that he is missing or has not yet demonstrated is known as Sequential Logic. Sequential Logic relies on its output to be one of its inputs, a feedback loop such as a Latch, Toggle, or Flip Flop. They retain state information. And these are the basic building blocks of memory devices. Without these, it is impossible for a complete logical device to be Turing Complete. You need to have a mechanism to store the results of your calculations. Don't get me wrong, what he was able to achieve by building a basic simple 4-bit binary ripple carry adder is pretty cool, but it's far from a State Machine. He won't be running DOOM, Tetris or Conway's Game of Life on it anytime soon!
Reddit went public on the stock market recently. It is not what it once was. Yes, that means get all your information off the site and do not give them any more.
@@hibbs1712tf kinda crack you on? Cause I want some, look at me, Google is public, you’re on UA-cam, who owns UA-cam? Yeah now delete your account, do it.
In fact electricity is not limited to on/off. Early computers experimented with analog and multiple levels of power, but differentiating between a bunch of levels of power was hard, so we don't see many analog computers these days.
Even our binary comouters today dont use "on or off" its a low voltage vs high voltage. And different circuits and such have different tolerances for the ranges
I don’t understand what the significance of this sentence means 😅 is this a good or bad thing and why? (I’m being so genuine, I want to know so bad and google is not going to be able to answer this question haha)
@@unburdenedcatcreature it’s both? Like it’s kinda repetitive to watch mattbattwings make truth tables in minecraft and physics for the birds (specifically the video mentioned by adef) describe them in totk, so I kinda tune out while we’re explaining XOR gates. This is not helped by me being a computer science major and this is all covered within a few meetings of your first class 😅 But because it’s familiar it’s also quite nice and nostalgic to hear over and over. I may not be paying full attention but I think it’s important these concepts are explained every time for people that DON’T watch youtube videos about computers and games like it’s their dayjob rofl Basically it’s neither bad nor good, just a recognizable step of explanation on a topic I’m already quite familiar with, and a consequence of each youtube video needing to treat itself as the only one the viewer will ever watch on that topic. And recognizing things is fun :-)
Would have I been born 10 or 15 years later, this very well could have been my childhood as well, and I would have loved to be friends with someone like Adef.
when you followed up the hayden bit with the 40 upvotes joke, you cemented your fate as someone i will be looking out for their next upload. i love finding and watching small(er) content creators. their jokes always hit different, and urs did.
@@archerelms I mean, if we go back like fifteen years, I'm sure plenty of us had some good reason to pick up a calculator for life. Still weird thinking that's probably the last one I'll ever buy.
For the record, you only need to be able to create either NAND or NOR to be able to make all of the other gates, since you can replicate all other truth tables with clever chaining of NAND/NOR gates and SOP/POS
Technically, chaining logic gates is not yet a Turing complete system. Usually, Turing complete systems have some form of memory where they can store intermediate results to feed them back into the calculation later
@@amconners Oh yeah, you are right. At least when the circuit can have cycles. I only thought about linearly chaining logic gates. In this case the computation always terminates after a fixed amount of time, which implies that the system is not Turing complete. I think we have to assume then that memory can be extended arbitrarily for logical circuits (with cycles) to be considered Turing complete. But this assumption is necessary anyway for any real world system to be considered Turing complete, so that should be fine
@@amconners But it requires more than just chaining them together even if you have a feedback loop to create a latch, toggle or flipflop you also need a clock generator or an oscillator to control the memory devices.
Unless your circuit can update itself, you cannot build memory. It's physically impossible. The circuits shown here are input -> output. No feedback possible. No memory, no Turing completeness
20-25 years ago putting together a computer was as easy as it is today. You simply order things and plug them together just the same. You might want to ask someone whether your part list makes sense but what else is new. But this wasn't the case in Soviet Union in the late 80s. The way i built a computer back then at the age of 9, well i read about computers in a book, they seemed fascinating, and really wanted one, so we went looking for relatives and friends which could help out. And help out they did, procuring a set of photocopied PCB artwork and ROM dumps, and a bunch of chips. And a user manual printed on a 9-pin dot matrix printer with tape that wasn't very fresh. The PCBs had to be etched, you had to find someone with a EPROM burner at work they could divert for a little to burn the ROM chips, and solder all of this together. The computer was Leningrad 48k, a clone of ZX Spectrum, an 1982 British home computer. With the difference that Spectrum has most of the computer on a single chip, the PLA, save for analogue voltage and support circuitry, RAM, CPU and ROM, and there was no Soviet equivalent for the PLA, or it wasn't obtainable, so it was replaced by a dozen odd TTL logic ICs from the 70s in Leningrad. It was spectacularly unreliable. We hand wired the keyboard from relableable reed switches, but we were able to get a fitting keyboard enclosure somehow, which also housed the computer logic board. It was connected to a tape recorder for storage and a small TV as a monitor.
I'm loving these videos! As a computer science major, it's kinda endearing how they are basically CS101, it reminds me of DannyB's OOT glitches explanations (although they are further down the CS curriculum lol). Maybe a colab for a computer in OOT next would be a fun idea?
Making a computer in Gen 3 is pretty cool... But... What about in Gen 1 and on cartridge? In theory, you MIGHT be able use one of the various ACE methods as a way to reprogram the game to add in some type of computer. I know there's a script using 8F to turn a sign in Cinnabar Island into a Pokemon dispenser, and I know there's several glitches that uses a specific amount of items in specific slots to do different things. Seems like you could in theory use this to make a calculator that adds up to 151 at least.
My favorite part of adef videos is having to pause and rewind so I can catch the half second text only jokes and Easter eggs. Really interesting video!
3:03 not actually. Binary just makes it so it's not as hard for one state to accidentally be read as a different state through voltage fluctuations. I actually really like balanced ternary computers. A balanced ternary computer has three states for each trit: positive, neutral, and negative.
Very cool and a great introduction to Boolean logic/arithmetic! I'd love to see you go down the rabbit hole on this more like some of your other videos inspired you to do. Especially since technically, you have a long way to go before Turing completeness. You are going to need an implementation of memory before you can build a Turing machine (this video demonstrates Boolean logic completeness, not Turing completeness).
I wonder. If some apocalyptic event happened, and this video is the only surviving record on how computers function, how long would it take us to get back to making modern-day computers
Great video, and a new sub :) Your statement near the end that this shows Turing completeness is not accurate though. Being able to simulate any fixed circuit does not imply Turing completeness (no circuit is Turing complete). What you would need to do is to show that you can simulate any Turing machine (or just a single universal Turing machine, which amounts to the same). For this you at least need some mechanism to store and read an arbitrary amount of memory (technically in this sense no real-world computer is Turing complete, but just like we do with real computers you would have to consider an "idealized" Pokemon game, which has no storage limit in the bag, or arbitrary number of boxes on the PC, or whatever). What this is closer to showing is that Pokemon is, in some sense, NP-Hard (imagine for example that to reach E4 you needed to find the set of inputs to a circuit which allows you to get to one of two possible exits, this would be NP-hard). But here we're still missing something to be able to simulate any circuit, namely a way to feed the output of one gate as the input of another. You were able to get around it here since every layer of the adder just depends on one bit of the previous layer (the carry) so you basically have two versions of the gate, and the player serving as the carry. I don't think anything like this works in general unfortunately :( I'm now really curious if there is a way to show NP-hardness! (Turing completeness I highly doubt is possible, but I'd be happy to be proven wrong)
There's already a bunch of papers from Eric Demaine et al on arxiv which show that several different mechanics from the Pokémon games suffice for NP-hardness (and PSPACE-completeness). It is very hard to put games like this outside PSPACE (eg showing Turing completeness) because you'd need something which can read and write data (eg an item which spawns other items which can spawn other items etc.)
Not done yet, so maybe you covered that: Actually you only need one gate ... that could be either "NAND" or "NOR". With one of those you can construct all the others.
4:13 So this video had me go down a rabbit hole to learn how to make all other logic gates using just these first three logic gates. And along the way, I discovered that all logic gates can easily just be made with a combination of simple NAND gates, which is just wild! I always wondered why one of my classmates in computer science class said that just NAND gates were the most fundamental building blocks of computer.
Here's a bonus computer science concept for the eagle-eyed viewer: look again at adef's implementation of the AND gate at 10:47. Do you notice how, if A is set to 0, then the treadmill tile for B isn't even encountered? Similarly, in the OR gate at 12:05, if A is set to 1, then the treadmill tile for B is also never encountered. This is a semantic called "short-circuit evaluation," which is present in some programming languages and evaluates the second input into a logic gate (more formally the second argument of a Boolean operator, if you're a gigantic nerd) only if the first is insufficient to determine the output. Some operations can't be short-circuited, like the XOR gate at 12:10 -- both gates must be evaluated to determine an XOR's output, which is why the Sapphire implementation has three treadmill tiles.
Genuinely one of my favourite UA-camrs going. Not only entertaining, but educational, with a dash of that wonderful nerdy humour I love and appreciate. Love your work Adef!
Bro, the time and dedication to learn this is amazing. I could only dream of having the knowledge to do this. Love this concepts and the videos, very fun and similar interest to my own childhood. Keep up the great work, love to see more
I kinda hope a gym in a future pokemon game finds a way to sneak logic gates inside of it, i feel like it would jump start a lot of kid’s creativity lol
I remember a paper where binsat was put in pokemon using trainer battles. You have just a haunter that knows lick. True would be a battle where you're outsped by a voltorb that only knows selfdestruct, and false would be a battle against a normal type with crunch that will outspeed and ohko you.
Its how a brains work and or not gates with synapses that are either on or off. Its y we have no free will. If our input is the same our output will be.
Honestly, the deeper one looks, the more meaningless the phrase "free will" becomes. Even if we were to pretend for the sake of argument that there is some supernatural aspect to it, that too would have to follow some kind of rules to perform its decision-making, again making it not-free. There are only two possibilities for a "source" of our decisions - causal determinism or true randomness. My money's on the first one.
the proof for Turing completeness requires state, which requires building memory. You'd need to implement a d flip flop, and chain those together to form a register and memory, and some kind of clock. And finally I guess some kind of proof you can switch between states. I'm not sure how you do that and it fits on screen to where the switches can affect everything but I salute the progress in proving that the Mossdeep City gym treadmills are Turing complete and could probably run Doom
3:02 Ok, so electricity can be more than just "on or off", and it's actually quite interesting that we use digital(two logic levels, "binary") electronics, as opposed to analog ones. There are of course multiple reasons for this, but a few of them are: Two logic levels make signal amplification easier, allowing you to stack arbitrary amounts of logic gates without adding noise. Related to the noise part is also that computations become completely deterministic(repeatable) without noise. Also they are easier to "clock" (only a clock signal + signal delay, instead of complicated phase relationships). That being said, analog circuits(and analog computation) does have it's uses: Basically all radio transmissions(Cellular, Wifi, FM broadcast, etc.) use analog circuitry, so does any kind of sound system(amplifiers). Some very old computers used analog computation, and they are making a slight comeback in some very special scenarios because they can be power efficient(e.g. analog sensor fusion). Very cool video though ;)
I saw the video and I went "working computer inside pokemon sapphire?, nah bullshit a whole computer can't be reduced so much in size that a Game Boy Advance cartridge can hold a whole pc", I just realized that it was not a physical computer when I watched the start of the video.
can't wait until someone makes a rom hack with an electric gym leader computer nerd that makes you compute "Hello World" before you can challenge them.
interesting tidbit about the elevated treadmill tiles: i believe it's actually been proven that any two-dimensional computing setup like this NEEDS to have paths be able to cross over other paths in order to be turing-complete! there's a toy "esoteric" programming language called Befunge that you might be interested in if you want to learn more
never in my life did I think I would hear concepts I learned in my college CS classes in a Pokemon video, but here we are! I worry about this man's sanity, but I'm here for the ride
I have rewatched every single pokemon related upload of yours i think about 15 times in anticipation for your next one. And to think there was another person just as nerdy as I
A calculator is NOT a computer. You need to be able to run a program that can branch execution paths based on calculations. And the ability to get stuck in an infinite loop. Autonomy is also not a requirement, but it does make these kinds of videos interesting. Is sapphire's scripting language turing complete?
could you use arbitrary code execution to attempt a version of this where you can set your inputs in the pc box names and have it set those when you enter the gym?
I am a massive computer science nerd, but for the last 5 years of my life I have failed to understand how logic gates actually do anything useful. I surrendered to only describing it as "Magic, Fuck You." You have such a magnificent way of breaking down elaborate concepts, I finally understand. To the moon with you, Adef!
Early on you say that all gates can be made with “and, not, or” but all gates can be made with just a nand, which is how most computers do it on a silicon level
this guy’s so cool i wish he was real
the moment you stop believing in me, i disintegrate
@@adef tolpadef
This is me when I clay
@@adef when the proof spits out ~adef
@@adefGoodbye!
Okay great now build a working Pokemon Sapphire inside a computer
someone did that already, people would call adef a hack
I would like to see a working version of Pokemon Sapphire inside of Pokemon Sapphire.
Sapphireception!
Nice try, Nintendo 💀
Oh hey you’re that melee guy
Nintendo is rapidly approaching your location.
Oh yeah? Well I built a non-working computer OUTSIDE pokemon sapphire. Better luck next time champ
Gottem
Sounds like something Gary would say
Found the H̶a̶y̶d̶e̶n̶ H̶a̶y̶d̶i̶n̶ H̶a̶y̶d̶o̶n̶ Heighdynn
Comedy gold
people who can only build non-working computers outside of pokemon saphire:
Doing all my damage calcs in my Pokémon Sapphire calculator from now on
Eisencalc 😤😤😤
For anyone who just joined, Calc is short for calculator, its slang
@@Voltaic01 cal is short for calendar, for anyone wondering. Its slang.
@@QuincyvhsVHS, for anyone who's curious, is short for Video Home System. It's an acronym.
Reminder: if a computer is Turing complete, you can run doom on it
I'm sure that video will pop up tomorrow
Doom complete
There's only one issue. His understanding of Turing Complete. Sure, he has demonstrated that you can perform ALU - Arithmetic & Logic Operations within this title, but he has not demonstrated a very vital part of a Turing Machine and what it means to be Turing Complete. The type of circuitry he did with these logic gates is known commonly known as Combinatorial Logic where their outputs only rely on the incoming inputs, they hold no state. The crucial part that he is missing or has not yet demonstrated is known as Sequential Logic. Sequential Logic relies on its output to be one of its inputs, a feedback loop such as a Latch, Toggle, or Flip Flop. They retain state information. And these are the basic building blocks of memory devices. Without these, it is impossible for a complete logical device to be Turing Complete. You need to have a mechanism to store the results of your calculations. Don't get me wrong, what he was able to achieve by building a basic simple 4-bit binary ripple carry adder is pretty cool, but it's far from a State Machine. He won't be running DOOM, Tetris or Conway's Game of Life on it anytime soon!
@@skilz8098nice thumbs 👍
@@skilz8098 it's not not even an ALU it's just an AU
the phrase "neighborhood subreddit" is terrifyingly dystopian yet feels so close to reality that it scares me
Reddit went public on the stock market recently. It is not what it once was. Yes, that means get all your information off the site and do not give them any more.
@@hibbs1712 I only use Reddit to look at memes, read BORU, and advertise my business, so they weren't really getting much from me to begin with.
@@hibbs1712tf kinda crack you on? Cause I want some, look at me, Google is public, you’re on UA-cam, who owns UA-cam? Yeah now delete your account, do it.
Nextdoor app
@@godminnette2 To be honest, I kinda refuse to believe anybody actually uses that for any sort of serious reason.
"Alright, lets enter the Mossdeep city computer simulation zone" Japanese MMO ad plays
*SAO music plays*
In fact electricity is not limited to on/off. Early computers experimented with analog and multiple levels of power, but differentiating between a bunch of levels of power was hard, so we don't see many analog computers these days.
Though every once in a while someone still experiments with tristate logic.
Even our binary comouters today dont use "on or off" its a low voltage vs high voltage. And different circuits and such have different tolerances for the ranges
There were some trinary computers in the USSR.
Potentiometers would like a word.
@@Zeldon567 That's an input device, not a computing device.
let it be known i love that lil snake
They're probably referencing the Death Adder
i love how every one of these videos have the plot of "fun idea, very cool" -> descent into madness -> relief and excitement
it's like Brian David Gilbert on Polygon
Seeing a truth table in a video about making a computer in a game is like seeing a bus metaphor for frame rules in a video about super mario bros
If it ain’t broke
asa well as the building of a basic adder. which isnt turring complete
But first, we need to talk about PARALLEL UNIVERSES
I don’t understand what the significance of this sentence means 😅 is this a good or bad thing and why? (I’m being so genuine, I want to know so bad and google is not going to be able to answer this question haha)
@@unburdenedcatcreature it’s both? Like it’s kinda repetitive to watch mattbattwings make truth tables in minecraft and physics for the birds (specifically the video mentioned by adef) describe them in totk, so I kinda tune out while we’re explaining XOR gates. This is not helped by me being a computer science major and this is all covered within a few meetings of your first class 😅
But because it’s familiar it’s also quite nice and nostalgic to hear over and over. I may not be paying full attention but I think it’s important these concepts are explained every time for people that DON’T watch youtube videos about computers and games like it’s their dayjob rofl
Basically it’s neither bad nor good, just a recognizable step of explanation on a topic I’m already quite familiar with, and a consequence of each youtube video needing to treat itself as the only one the viewer will ever watch on that topic. And recognizing things is fun :-)
Gonna be honest, the abacus isn’t helping with the Hayden problem, when he finds out he’s gonna post a real nasty one
Excuse you, it's Heighdynn, alright??
Wow that childhood sounded very normal!
Would have I been born 10 or 15 years later, this very well could have been my childhood as well, and I would have loved to be friends with someone like Adef.
I thought all of us made romhacks when we were 12?
@@komi___ I think I was 13
Cool vid! Next can you simulate my father's approval inside Pokemon Sapphire?
You don't need adef to help with that. Just beat the 5th gym in vanilla Pokemon Sapphire.
Considering you start the game in the back of a moving truck, I don't know how far we can really take this
when you followed up the hayden bit with the 40 upvotes joke, you cemented your fate as someone i will be looking out for their next upload. i love finding and watching small(er) content creators. their jokes always hit different, and urs did.
So glad whenever I don’t have my abacus on me I can now whip my DS out. Thank you for the life hack 🙏
The calculator is having an existential crisis in French
Its a refrence to a famous french painting of a pipe called "this is not a pipe"
As a native French speaker, I'm always amazed when I see French words in English videos xD
For some reason with your physics degree I feel like yes, it is normal you would own an abacus and not a calculator. But that could just be me.
I want an abacus now 🧮
We all have a calculator on our phones and computers, why would we have a separate calculator? But an abacus, that makes sense
@@archerelms I mean, if we go back like fifteen years, I'm sure plenty of us had some good reason to pick up a calculator for life. Still weird thinking that's probably the last one I'll ever buy.
pretty sure adef has transcended past smart and is now bordering on evil genius and I am all for it
ITS L8 BIT 😮
For the record, you only need to be able to create either NAND or NOR to be able to make all of the other gates, since you can replicate all other truth tables with clever chaining of NAND/NOR gates and SOP/POS
yea i remeber this from circuits but dont u also need to have a rs latch / switch to be able to store info / a tape so its turing complete idk
@@hashirkzyou can build latches only using NANDs or NORs
Technically, chaining logic gates is not yet a Turing complete system. Usually, Turing complete systems have some form of memory where they can store intermediate results to feed them back into the calculation later
memory can also be constructed solely by chaining logic gates!
@@amconners Oh yeah, you are right. At least when the circuit can have cycles. I only thought about linearly chaining logic gates. In this case the computation always terminates after a fixed amount of time, which implies that the system is not Turing complete. I think we have to assume then that memory can be extended arbitrarily for logical circuits (with cycles) to be considered Turing complete. But this assumption is necessary anyway for any real world system to be considered Turing complete, so that should be fine
@@amconners But it requires more than just chaining them together even if you have a feedback loop to create a latch, toggle or flipflop you also need a clock generator or an oscillator to control the memory devices.
Unless your circuit can update itself, you cannot build memory. It's physically impossible. The circuits shown here are input -> output. No feedback possible. No memory, no Turing completeness
Bro is the reason i picked extra physics and computer science in school
If I watch this entire video and it turns out all you've done by the end of it make a calculator, I'm going be both peeved and vexed.
I think this guy could prove Ariados is in fact a horse. He’s a treasure.
I mean, it is spanish for horse. My spanish uncle Jamon Tendo told me so.🤓
@@missglucktesbartierchen4143 is he the guy who invented magnemite?
Bomberman Hero OST spotted 2:07
Never thought I'd see you there ^^
Will you keep the blonde hair after the Funky Kong video? 😂
TY!
Knew I recognized it
20-25 years ago putting together a computer was as easy as it is today. You simply order things and plug them together just the same. You might want to ask someone whether your part list makes sense but what else is new.
But this wasn't the case in Soviet Union in the late 80s. The way i built a computer back then at the age of 9, well i read about computers in a book, they seemed fascinating, and really wanted one, so we went looking for relatives and friends which could help out. And help out they did, procuring a set of photocopied PCB artwork and ROM dumps, and a bunch of chips. And a user manual printed on a 9-pin dot matrix printer with tape that wasn't very fresh. The PCBs had to be etched, you had to find someone with a EPROM burner at work they could divert for a little to burn the ROM chips, and solder all of this together. The computer was Leningrad 48k, a clone of ZX Spectrum, an 1982 British home computer. With the difference that Spectrum has most of the computer on a single chip, the PLA, save for analogue voltage and support circuitry, RAM, CPU and ROM, and there was no Soviet equivalent for the PLA, or it wasn't obtainable, so it was replaced by a dozen odd TTL logic ICs from the 70s in Leningrad. It was spectacularly unreliable. We hand wired the keyboard from relableable reed switches, but we were able to get a fitting keyboard enclosure somehow, which also housed the computer logic board. It was connected to a tape recorder for storage and a small TV as a monitor.
So, in theory, you could run Pokemon in Pokemon, all displayed with Spinda-pixels.
This video is way more surreal for someone who actually has a neighbor named Hayden, lmao
it's heighdynn*
I was expecting using the RBY ACE bug to build a basic computer, but this feels more fun tbh
Such an underrated channel. Thank you so much for the interesting / enlightening content!!
He was so preoccupied with whether he could, he never asked whether he should. Nintendo has already sent their lawyers after him 😢
Typical Nintendo.
I'm loving these videos! As a computer science major, it's kinda endearing how they are basically CS101, it reminds me of DannyB's OOT glitches explanations (although they are further down the CS curriculum lol). Maybe a colab for a computer in OOT next would be a fun idea?
When i clicked on this, i was expecting using ACE to make a simulated microcontroller or something
Making a computer in Gen 3 is pretty cool... But... What about in Gen 1 and on cartridge? In theory, you MIGHT be able use one of the various ACE methods as a way to reprogram the game to add in some type of computer. I know there's a script using 8F to turn a sign in Cinnabar Island into a Pokemon dispenser, and I know there's several glitches that uses a specific amount of items in specific slots to do different things. Seems like you could in theory use this to make a calculator that adds up to 151 at least.
Watching this video, I get the sense that this guy is definitely normal and always has been, which is cool.
this is just a brief lesson on discrete math I love it
My favorite part of adef videos is having to pause and rewind so I can catch the half second text only jokes and Easter eggs. Really interesting video!
3:03 not actually. Binary just makes it so it's not as hard for one state to accidentally be read as a different state through voltage fluctuations. I actually really like balanced ternary computers. A balanced ternary computer has three states for each trit: positive, neutral, and negative.
14:52 bro invented microchips in mossdeep gym
the amount of video game YT content that does a better job explaining digital logic and computer architecture than professors is staggering
Very cool and a great introduction to Boolean logic/arithmetic!
I'd love to see you go down the rabbit hole on this more like some of your other videos inspired you to do.
Especially since technically, you have a long way to go before Turing completeness. You are going to need an implementation of memory before you can build a Turing machine (this video demonstrates Boolean logic completeness, not Turing completeness).
I wonder. If some apocalyptic event happened, and this video is the only surviving record on how computers function, how long would it take us to get back to making modern-day computers
What a Brilliant video from a Brilliant person :)
Keep up the great videos Adef, they're always a treat to watch!
Love the code at 2:44, very helpful
Sample also recently made an edit like this recently, and it's honestly something I'd love to see more
It is now theoretically possible to build a computer inside Pokemon Sapphire to run Pokemon Sapphire
Great video, and a new sub :) Your statement near the end that this shows Turing completeness is not accurate though.
Being able to simulate any fixed circuit does not imply Turing completeness (no circuit is Turing complete). What you would need to do is to show that you can simulate any Turing machine (or just a single universal Turing machine, which amounts to the same). For this you at least need some mechanism to store and read an arbitrary amount of memory (technically in this sense no real-world computer is Turing complete, but just like we do with real computers you would have to consider an "idealized" Pokemon game, which has no storage limit in the bag, or arbitrary number of boxes on the PC, or whatever).
What this is closer to showing is that Pokemon is, in some sense, NP-Hard (imagine for example that to reach E4 you needed to find the set of inputs to a circuit which allows you to get to one of two possible exits, this would be NP-hard). But here we're still missing something to be able to simulate any circuit, namely a way to feed the output of one gate as the input of another. You were able to get around it here since every layer of the adder just depends on one bit of the previous layer (the carry) so you basically have two versions of the gate, and the player serving as the carry. I don't think anything like this works in general unfortunately :(
I'm now really curious if there is a way to show NP-hardness! (Turing completeness I highly doubt is possible, but I'd be happy to be proven wrong)
There's already a bunch of papers from Eric Demaine et al on arxiv which show that several different mechanics from the Pokémon games suffice for NP-hardness (and PSPACE-completeness).
It is very hard to put games like this outside PSPACE (eg showing Turing completeness) because you'd need something which can read and write data (eg an item which spawns other items which can spawn other items etc.)
@@AFastidiousCuber Ah yes I should have guessed (or done a 20 sec Google search) about Eric having papers on this!
this project 🤝 me after walking on all these treadmill tiles: absolutely sick
Not done yet, so maybe you covered that:
Actually you only need one gate ... that could be either "NAND" or "NOR". With one of those you can construct all the others.
4:13 So this video had me go down a rabbit hole to learn how to make all other logic gates using just these first three logic gates. And along the way, I discovered that all logic gates can easily just be made with a combination of simple NAND gates, which is just wild! I always wondered why one of my classmates in computer science class said that just NAND gates were the most fundamental building blocks of computer.
This is really awesome!! I never thought about the tiles in mosdeeps gym as being this flexible. Excited for future content 😎
Create a computer within yourself
Here's a bonus computer science concept for the eagle-eyed viewer: look again at adef's implementation of the AND gate at 10:47. Do you notice how, if A is set to 0, then the treadmill tile for B isn't even encountered? Similarly, in the OR gate at 12:05, if A is set to 1, then the treadmill tile for B is also never encountered.
This is a semantic called "short-circuit evaluation," which is present in some programming languages and evaluates the second input into a logic gate (more formally the second argument of a Boolean operator, if you're a gigantic nerd) only if the first is insufficient to determine the output. Some operations can't be short-circuited, like the XOR gate at 12:10 -- both gates must be evaluated to determine an XOR's output, which is why the Sapphire implementation has three treadmill tiles.
There's NO content like yours out there, this video was HELLA entertaining and awesome to see! Mad props!
Genuinely one of my favourite UA-camrs going. Not only entertaining, but educational, with a dash of that wonderful nerdy humour I love and appreciate. Love your work Adef!
Bro, the time and dedication to learn this is amazing. I could only dream of having the knowledge to do this. Love this concepts and the videos, very fun and similar interest to my own childhood. Keep up the great work, love to see more
Clearly the next step is to run Doom in Pokemon Sapphire.
you own an abacus?
u must be a brave little abacus fan 😨
You may have made a working computer in pokemon sapphire, but did you make a working computer inside of the computer inside the pokemon center?
dude i can’t wait to see a collab w other poketubers and my worlds collide
going from the cute little mossdeep half adder into the reveal of the tile full adder map is hysterical thank you
I kinda hope a gym in a future pokemon game finds a way to sneak logic gates inside of it, i feel like it would jump start a lot of kid’s creativity lol
I remember a paper where binsat was put in pokemon using trainer battles. You have just a haunter that knows lick. True would be a battle where you're outsped by a voltorb that only knows selfdestruct, and false would be a battle against a normal type with crunch that will outspeed and ohko you.
Its how a brains work and or not gates with synapses that are either on or off. Its y we have no free will.
If our input is the same our output will be.
Honestly, the deeper one looks, the more meaningless the phrase "free will" becomes. Even if we were to pretend for the sake of argument that there is some supernatural aspect to it, that too would have to follow some kind of rules to perform its decision-making, again making it not-free.
There are only two possibilities for a "source" of our decisions - causal determinism or true randomness. My money's on the first one.
Okay, now build a working computer inside Minecraft that can run a functional Pokemon Sapphire that can run a working computer
the proof for Turing completeness requires state, which requires building memory. You'd need to implement a d flip flop, and chain those together to form a register and memory, and some kind of clock. And finally I guess some kind of proof you can switch between states. I'm not sure how you do that and it fits on screen to where the switches can affect everything but I salute the progress in proving that the Mossdeep City gym treadmills are Turing complete and could probably run Doom
Everything you make is a total banger
Finally! Trash day on Tuesday, sign me up. Thanks Hayden.
3:02 Ok, so electricity can be more than just "on or off", and it's actually quite interesting that we use digital(two logic levels, "binary") electronics, as opposed to analog ones.
There are of course multiple reasons for this, but a few of them are: Two logic levels make signal amplification easier, allowing you to stack arbitrary amounts of logic gates without adding noise. Related to the noise part is also that computations become completely deterministic(repeatable) without noise. Also they are easier to "clock" (only a clock signal + signal delay, instead of complicated phase relationships).
That being said, analog circuits(and analog computation) does have it's uses: Basically all radio transmissions(Cellular, Wifi, FM broadcast, etc.) use analog circuitry, so does any kind of sound system(amplifiers). Some very old computers used analog computation, and they are making a slight comeback in some very special scenarios because they can be power efficient(e.g. analog sensor fusion).
Very cool video though ;)
Making your own computer always seems to start with a poisonous snake and ends up in an 8-way orgy. Computing is awesome!
I don't really know anything about computing past basic binary, but you made everything easy to understand and entertaining as always so thank you! ^^
It's funny how this is SO much more interesting than just taking a CS class lol Great job!
I saw the video and I went "working computer inside pokemon sapphire?, nah bullshit a whole computer can't be reduced so much in size that a Game Boy Advance cartridge can hold a whole pc", I just realized that it was not a physical computer when I watched the start of the video.
can't wait until someone makes a rom hack with an electric gym leader computer nerd that makes you compute "Hello World" before you can challenge them.
this guy when he finds out he has a working computer inside his house:
Another great video by my fav Normal Guy. Good Job!
i really appreciate this; you’ve given me dungeon maze puzzles i can use for table games like d&d thank you so much for that, this rules.
interesting tidbit about the elevated treadmill tiles: i believe it's actually been proven that any two-dimensional computing setup like this NEEDS to have paths be able to cross over other paths in order to be turing-complete! there's a toy "esoteric" programming language called Befunge that you might be interested in if you want to learn more
Every video I say ‘why adef’ and then watch cause I know how impressive this is.
There's a working computer inside every Pokémon sapphire dummy. That's how the game runs
I remember making this in class and hated it wasn’t easy, can only imagine your struggle
Now build a computer inside a Pokémon.
never in my life did I think I would hear concepts I learned in my college CS classes in a Pokemon video, but here we are! I worry about this man's sanity, but I'm here for the ride
I have rewatched every single pokemon related upload of yours i think about 15 times in anticipation for your next one. And to think there was another person just as nerdy as I
Not only is this neat, but you're the first person to teach me how addition in binary works
Been on a roll lately, keep it up!
A calculator is NOT a computer. You need to be able to run a program that can branch execution paths based on calculations. And the ability to get stuck in an infinite loop. Autonomy is also not a requirement, but it does make these kinds of videos interesting.
Is sapphire's scripting language turing complete?
"At the end of the day it's a children's video game"
I feel attacked. LOL
Very cool. Thank you for becoming a new channel that I look forward to watching.
could you use arbitrary code execution to attempt a version of this where you can set your inputs in the pc box names and have it set those when you enter the gym?
I am a massive computer science nerd, but for the last 5 years of my life I have failed to understand how logic gates actually do anything useful. I surrendered to only describing it as "Magic, Fuck You." You have such a magnificent way of breaking down elaborate concepts, I finally understand. To the moon with you, Adef!
I saw this appear in my sub box and my first reaction, out loud, was "No you f***ing didn't. God dammit, adef, you have to be stopped."
your videos are always stepping it up this is amazing!
Next, do a deep dive into safari zones
Building a computer 20 years ago was exactly like it is now, newegg included
It’s way too early in the morning for this
Ah yes, a normal adult activity for an adult that results from a normal childhood.
Soon enough we’ll get “I ran doom on a Spinda in Pokemon Sapphire”
It's okay, I also own an abacus and it's one of my favored possessions.
Early on you say that all gates can be made with “and, not, or” but all gates can be made with just a nand, which is how most computers do it on a silicon level
Congrats on getting featured in an article from game radar, adef!