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!
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
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.
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 :-)
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
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.
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
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.
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.
@@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.
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?
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.
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.
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
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?
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!
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.)
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).
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
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.
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
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
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.
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.
I once tried learning coding to create my own gameshark codes back when this game was new because coding was so complicated. The info about the gates is very nice and clear 👏
I was hoping this would somehow lead to doing it IN the game on hardware without any romhacking. However, that is probably legitimately impossible, no matter how small scale the idea or how far you stretch the idea of what a computer is. This is STILL insane.
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!
that reminds me of the cpu I was working on in The powder toy, tho its far from turing compleet but it can run some super simple programs (fibonachi and simple counter) and could be made theorically turing compleet if I was crazy enough to do the modifications I was thinking off but would be the worst way possible of doing it but seeing a fellow nerd making a full adder in a video game is something I love (I made simple full adders in 3 or 4 sandbox games but never through modding a game directly)
You could have one of the outputs send the player to an area where they can and must pull a switch before continuing. The switch both unlocks the path forward, and modifies future gates in whatever way is desired.
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!
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.
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
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 ;)
this is the best-looking person that has said the sentence "i've always been fascinated with building computers" ever also this was cool, subbed and i'll support you in the neighborhood subreddit
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
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.
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.
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:
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
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.
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.
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
"Alright, lets enter the Mossdeep city computer simulation zone" Japanese MMO ad plays
*SAO music plays*
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 :-)
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
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.
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
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
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
let it be known i love that lil snake
They're probably referencing the Death Adder
So glad whenever I don’t have my abacus on me I can now whip my DS out. Thank you for the life hack 🙏
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??
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.
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.
this is just a brief lesson on discrete math I love it
pretty sure adef has transcended past smart and is now bordering on evil genius and I am all for it
ITS L8 BIT 😮
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
Bro is the reason i picked extra physics and computer science in school
I was expecting using the RBY ACE bug to build a basic computer, but this feels more fun tbh
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.
So, in theory, you could run Pokemon in Pokemon, all displayed with Spinda-pixels.
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?
When i clicked on this, i was expecting using ACE to make a simulated microcontroller or something
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?
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
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.
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.
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
He was so preoccupied with whether he could, he never asked whether he should. Nintendo has already sent their lawyers after him 😢
Typical Nintendo.
Such an underrated channel. Thank you so much for the interesting / enlightening content!!
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?
Watching this video, I get the sense that this guy is definitely normal and always has been, which is cool.
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!
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!
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.
you own an abacus?
u must be a brave little abacus fan 😨
going from the cute little mossdeep half adder into the reveal of the tile full adder map is hysterical thank you
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).
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
I remember making this in class and hated it wasn’t easy, can only imagine your struggle
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.
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
This video is way more surreal for someone who actually has a neighbor named Hayden, lmao
it's heighdynn*
There's NO content like yours out there, this video was HELLA entertaining and awesome to see! Mad props!
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
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.
the amount of video game YT content that does a better job explaining digital logic and computer architecture than professors is staggering
This is really awesome!! I never thought about the tiles in mosdeeps gym as being this flexible. Excited for future content 😎
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.
I once tried learning coding to create my own gameshark codes back when this game was new because coding was so complicated. The info about the gates is very nice and clear 👏
Create a computer within yourself
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
The switches for Surge's gym have a pattern, they always are directly next to the next switch that was first found.
14:52 bro invented microchips in mossdeep gym
Not only is this neat, but you're the first person to teach me how addition in binary works
This is sick! Now you need to make a romhack where you have to input the correct numbers to get to the gym leader...
It's funny how this is SO much more interesting than just taking a CS class lol Great job!
I was hoping this would somehow lead to doing it IN the game on hardware without any romhacking. However, that is probably legitimately impossible, no matter how small scale the idea or how far you stretch the idea of what a computer is. This is STILL insane.
It can be done in Pokémon Yellow with a saving glitch m.ua-cam.com/video/p5T81yHkHtI/v-deo.html I'm not sure if there is a better video.
Yeah, the title is a misleading since he didn’t build the computer inside the game.
Every video I say ‘why adef’ and then watch cause I know how impressive this is.
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?
this project 🤝 me after walking on all these treadmill tiles: absolutely sick
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!
that reminds me of the cpu I was working on in The powder toy, tho its far from turing compleet but it can run some super simple programs (fibonachi and simple counter) and could be made theorically turing compleet if I was crazy enough to do the modifications I was thinking off but would be the worst way possible of doing it
but seeing a fellow nerd making a full adder in a video game is something I love (I made simple full adders in 3 or 4 sandbox games but never through modding a game directly)
I think you need to make something where the outputs are able to affect the next gate so that you can properly chain them.
You could have one of the outputs send the player to an area where they can and must pull a switch before continuing. The switch both unlocks the path forward, and modifies future gates in whatever way is desired.
Clearly the next step is to run Doom in Pokemon Sapphire.
NEW ADEF VIDEO MEANS I CLICK AND LIKE AND COMMENT FOR ALGO
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! ^^
Next semester I'm going to be learning more about logic gates and computers, so this came out at a great time
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!
Finally! Trash day on Tuesday, sign me up. Thanks Hayden.
dude i can’t wait to see a collab w other poketubers and my worlds collide
I usually just go to the one next to the Pokémon center nurse 😧
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.
I thought you were going to make a computer inside Pokémon sapphire, not just using sapphire's assets. Still pretty cool.
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
Oh this video comes to me just as I start really wanting to learn about code and computers.
Well, down the rabbit hole I guess.
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
It’s way too early in the morning for this
It is now theoretically possible to build a computer inside Pokemon Sapphire to run Pokemon Sapphire
Everything you make is a total banger
Making your own computer always seems to start with a poisonous snake and ends up in an 8-way orgy. Computing is awesome!
As someone who has been implementing a digital logic simulator in Javascript, this is super cool. Like. _Wow_ - well done adef!
Okay... I was expecting some pomeg glitch ACE, but this is super cool too!
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.
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 really needed this for my last assignment, you explain very clearly
this is the best-looking person that has said the sentence "i've always been fascinated with building computers" ever
also this was cool, subbed and i'll support you in the neighborhood subreddit
What a Brilliant video from a Brilliant person :)
Keep up the great videos Adef, they're always a treat to watch!
You don't need all of AND, NOT, and OR to construct every logic gate. In fact, you only need either NAND or NOR and you can construct all the others
It's okay, I also own an abacus and it's one of my favored possessions.
This is way cooler than the logic gate lessons I took when I was in highschool.
God, that style of intro made me so nostalgic to 2010s UA-cam
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
You always lose me like 5 min in and I still watch with baited breath like a cave man being shown fire