Now turn it into a quantum computer to speed things up lol
@ilytokyobt
2 ай бұрын
To this day it is said that its still running...
@LightPink
3 ай бұрын
Thank you for the video!
@theBestInvertebrate
5 ай бұрын
Woah, the music intensity lines up with the screen transitions, at least sometimes (particularly noticeable for breakfast)
@cerno_b
5 ай бұрын
Haha, that's totally by accident. :D
@theBestInvertebrate
5 ай бұрын
@@cerno_b would be nice to see gameplay too not just a montage.
@cerno_b
5 ай бұрын
@@theBestInvertebrate I agree. So far I think not a lot of people watch these timelapses and those who do generally come from playing the game, so I didn't bother. But you're right, it would have been a nice finisher to the video instead of cutting it off abruptly.
@JamesTDG
5 ай бұрын
Did you ever make it theoretically run doom?
@kamosevoyan4370
6 ай бұрын
Can anyone explain me why 2tag step is necessary, please?
@cerno_b
6 ай бұрын
In order to run an M:TG Turing Machine, we need to convert any Turing Machine into a Turing Machine with only 2 states. This is very hard to do manually (try it with a simple toy example). Fortunately, there are two math publications that help out here: A paper by Minsky and Cocke with an algorithm to convert any 2-symbol-Turing Machine into a 2-Tag System and a paper by Rogozhin with an algorithm to convert any 2-Tag System to a 2-state Turing machine. So basically the very hard process of writing a custom 2-State Turing Machine by hand is automated by using an algorithm that can convert a 2-symbol Turing Machine into a 2-Tag System and then further to a 2-state Turing Machine.
@poetac15
9 ай бұрын
Amazingly good free content. Thanks for posting.
@0011peace
9 ай бұрын
Why don' t show it in mtgo it has almost all the cards mtg. Even aea has all the cards in turning deck fron kyle ir t woud make mor usable
@RIPmitchhedbergRIP
Жыл бұрын
Are we at the point where wotc printing new cards will never have a significant impact on the efficiency of this machine? If not, hypothetically, how much bang for your buck can you get if I allow you to create say 10 new cards?
@cerno_b
Жыл бұрын
That's an excellent question! I'll need to sit on that for a precise answer but off the top of my head I think if there was a 4-way Phase it might enable us to base the game on a UTM(4,6). This could encode some classes of Turing Machines more efficiently. Trying to write any Turing Machine with just 2 states by hand is challenging, having 4 states available makes it much easier.
@peterSobieraj
Жыл бұрын
I see some coding in Visual Studio, some drawing in paint (I think), some music making, but I don't know what you are doing. Some introduction at the beginning, or show of finished product at the end will be useful.
@cerno_b
Жыл бұрын
Thanks for your feedback. These timelapse videos are more of a low-effort documentation of my game dev journey and process. You're right, I could have explained everything better. I hope that the video might interest a fellow game jam participant to see the portion of time spent coding/drawing/composing and at which stage in development I switch mediums. If you are interested in the game itself, I linked it in the description. Maybe I'll upload a compilation if my Ludum Dare games one of these days so it's easier to see what they look like in action.
@danielrhouck
Жыл бұрын
If I understand correctly, the different symbols are creature types. As such I imagine you could get a lot of benefit by going from UTM(2, 18) to using all 280 possible symbols.
@cerno_b
Жыл бұрын
The Rogozhin Universal Turing Machines come in different sizes, some have few states and many symbols, like UTM(2, 18), some have many states and few symbols, like UTM(24, 2). The reason why the M:TG Turing Machines are so insanely large is because we have to compress an arbitrary Turing Machine into one with just 2 states. So having more symbols would not help because we are still dealing with just two states. On the other hand, having more states might help. However the M:TG Turing Machine hinges on the phase mechanic which allows to switch between two game states which in turn map to the two Turing Machine states. If we were able to implement a 4-way phase in M:TG we might realize a UTM(4, 6) with just four states, which then might be easier to compress.
@danielrhouck
Жыл бұрын
@@cerno_b You don’t *need* to go through a UTM at all, in many specific cases; you need that for the general case. If something can be implemented directly with 2 states and 29 symbols I’d expect that to be faster than translating the same thing to UTM(2, 18) code. For most real problems this wouldn’t help, but for a minimal example like 2+3 it might. Or even “we don’t know if this is a win”, like a Collatz machine. Maybe I’m off base here, but you do talk about how the different levels of translation and the tape length both slow this down. More symbols means shorter tape, and trying to code simple problems directly means less extra work to implement 2-tag in between.
@cerno_b
Жыл бұрын
@@danielrhouck Definitely! If you assume a simple problem that can be expressed as a 2 state Turning Machine from the get go, then you can directly encode it as a M:TG Turing Machine which would run much faster. The problem is that there aren't really a lot of worthwhile programs that can easily be expressed as 2 state Turning Machines. At least as far as I know. I tried writing a Turing Machine with two states by hand. Try it yourself, it's really hard! If you have a cool one please let me know and we can try running it in my compiler to see how it plays out in the game. So the limiting factor is not necessarily the number of symbols but rather the number of states. Maybe there is a more efficient conversion method from generic TM to 2 state TM but the literature I know only goes through the process I described in the video. It is not efficient at all since it only concerns itself with the mathematical proof that this is possible in general and not practical execution.
@cerno_b
Жыл бұрын
Somehow KZitem wrecked a lot of my answers to the comments here because I switched from a non-gmail address to a gmail one. I did respond to most commenters, but those answers are gone now :(. Now some of the conversations look like people talking to themselves.
@ohiorizzler1434
Жыл бұрын
Now think about it: you can reduce fortnite onto this, so it is possible to play Fortnite in magic.
@cerno_b
Жыл бұрын
Or Magic: Arena
@warhead3337
Жыл бұрын
You deserve way more visibility! Really interessing! Great job!
@God-ch8lq
Жыл бұрын
but can it run doom?
@JubilantJerry
2 жыл бұрын
Using the universal Turing machine to implement 2 + 3 is like building a Rube Goldberg machine to pass butter... couldn't the Magic the Gathering deck implement any Turing machine of 18 symbols and 2 states? I'm pretty sure there's a much more compact method to code addition within those constraints. Also I suspect that more than 2 states is possible within the game rules.
@JubilantJerry
2 жыл бұрын
I've researched a bit more into this, looks like the Magic setup doesn't trivially generalize into more states since it uses phasing for its 2 states. Maybe it's possible to directly write a TM to do unary addition with 2 states and 18 symbols, but not really anything more complex without resorting to the nuclear option of using the UTM construction. I think Magic allows a lot more than 18 symbols, but it seems that in general you can't trade state count for symbol count other than by using a small UTM. It may be possible to directly write a much smaller program in the 2-tag description though. Your video probably used a 2-tag compilation that has exponential simulation overhead, and that was the step that made your final setup so big. According to "The Complexity of Small Universal Turing Machines: A Survey" by T Neary, there's 2-tag compiler with polynomial overhead. Then the Magic UTM simulates 2-tag with polynomial (quadratic) overhead. So you can get a much more efficient setup by one of these methods: 1. Manually write a small 2-tag implementation of unary addition, then convert it to the Magic UTM. The quadratic overhead should still be manageable if the 2-tag description is small. 2. Use the compiler from T Neary to convert your unary addition TM to 2-tag. The overhead of this step is close to quadratic. Adding the quadratic overhead for the Magic UTM on top of that gives close to a 4th power overhead. 3. Implement unary addition manually as a Turing machine of 2 states and 18 symbols, then convert it to Magic. This may require their more complex card setup for extending the blank tape though, if the blank symbol has a state transition. And this method isn't generalizable to other programs. 3. Find out a method of getting more than 2 states in Magic. Maybe we can use more cards in the library and enable / disable phasing in a periodic way. If it's possible to get a 3 state TM then we can use the efficient 3 state, 11 symbol direct simulation UTM from the above paper, which has a quadratic overhead end-to-end.
@zenithh-d
2 жыл бұрын
Thank you for sharing your process! I feel a lot better about my own development style in Game Maker Studio 2 by seeing someone else's process.
@cerno_b
2 жыл бұрын
Thanks for you your interest. Just an FYI, I have just completed my first Ludum Dare using Godot instead of Game Maker Studio and while there was a learning curve, I absolutely loved the experience. The scripting language which is based on Python feels so natural to me that I will permanently switch over to Godot from this LD on. I will upload a timelapse of that as well in case you're interested.
@zenithh-d
2 жыл бұрын
@@cerno_b I've been interested in Godot so a timelapse in Godot would help me wrap my head around it a little more I think. Thank you for your reply!
@cerno_b
2 жыл бұрын
Timelapse is done: kzitem.info/news/bejne/y4aum6achGJhiYo
@IkuMasterLink
2 жыл бұрын
But can it run Crysis?
@dbojangles1597
2 жыл бұрын
Wait so there is no creature type in the history of Magic that starts with a Q?
@cerno_b
2 жыл бұрын
You got me there for a second, but apparently no. Comprehensive Rules 205.3m. There is also no type with X, but other than that the alphabet is complete. magic.wizards.com/en/rules
@DeconvertedMan
2 жыл бұрын
Amazing! After all that work you would really be all *TAPPED OUT* :D
@AdrianHereToHelp
2 жыл бұрын
Could you get the complexity down by using a base determined by the number of symbols available and writing the program directly in the Magic Turing Machine rather than doing a bunch of conversions? (Obviously it would be a lot more work, but would it work?)
@cerno_b
2 жыл бұрын
Yes, in principle, but writing a Turing machine with just 2 states by hand is very difficult. For trivial Turing machines that may even be possible, like "take the input word and append a single letter", but as soon as you add repetition or any type of conditions to your program, you need more than 2 states and would have to use your tape in order to read and write markers that represent the state of your program. That is basically what this conversion does: Split up your program into a data section and a code section that can then be represented by a 2-state Universal Turing Machine. Doing this by hand is really hard. So the limitation is not necessarily the 18 symbols (which you could increase to the number of different tokens available in M:TG), but rather your limitation to 2 states (represented by the two statuses of the phase mechanic). You could however think of another way of running a different UTM in M:TG, like a (3,10) or a (4,6), but then you would have to figure out a clever way to use a different game mechanic to represent state changes.
@dzz5799
3 жыл бұрын
super interesting it's awsome!!!!!!
@stevenh4314
3 жыл бұрын
Correct me if I'm wrong, but if you can use mtg to make a Turing machine, and Turing machines are capable of doing anything a modern computer can, and you can play magic on a computer, then that would mean that you could simulate a game of mtg within mtg
@cerno_b
3 жыл бұрын
Nice idea! Yes, that would be entirely possible. There's always the question of how to wait for and handle inputs, so you may have to adapt the original Turing machine a little, but theoretically, it should be possible. You could even take that simulation and simulate it in a MtG Turing machine (and so on). MtGception.
@Ella-tw6ri
3 жыл бұрын
So, can I theoretically run doom on magic the gathering
@cerno_b
3 жыл бұрын
In theory, yes. However, consider how hard it was to formulate the simple task of 2+3 in Magic. Now consider, that a game essentially consists of a huge number of mathematical terms like that as well as a whole bunch of logic blocks, and we haven't even started discussing how we would move images the size of thousands of pixels through the machine. I'd guess that in order to achieve this you would easily need more time and matter than is available in our universe. But given an infinite supply of time and magic cards I guess you could pull it off.
@another3997
3 жыл бұрын
Most of this is lost on me, I'm more of a 'literary' person rather than logic and maths. My mind goes on strike before it makes sense, but respect for making the video and trying to explain it. I'll watch it a few times, just in case it finally clicks. On request. When recording the audio, please don't have the microphone so close to your mouth and speak a little louder... hearing the sounds of your breathing and your tongue moving as you talk is really offputting. 🙁
@cerno_b
3 жыл бұрын
Thanks for your feedback. To be honest, I am less than happy with the audio quality myself. I do have a decent microphone and a good setup but all the hardware in the world can't rescue you if you lack the experience in recording yourself. This was a first for me and I will aim to be better in the future. Thank you.
@another3997
3 жыл бұрын
Most of this is lost on me, I'm more of a 'literary' person rather than logic and maths. My mind goes on strike before it makes sense, but respect for making the video and trying to explain it. I'll watch it a few times, just in case it finally clicks. On request. When recording the audio, please don't have the microphone so close to your mouth and speak a little louder... hearing the sounds of your breathing and your tongue moving as you talk is really offputting. 🙁
@TheRegret
3 жыл бұрын
so if both players were playing a game to create a turing machine instead of 1 player, would the outcome be different? can i use interactions between the 8 player moves instead of 4, and the interaction between cards and their effects be the read/write, and the whole board as a whole being an output? edit: i realize this would be incredibly complex as you would have to have the interactions between cards be the program table and so the cards would still be limited in what range they could effect but can i use something other than creature tokens and power values? like for instance prodigal sorcerer deal 1 true damage to the player can i use that as a state change and have 20+ states with multiple programs?
@cerno_b
3 жыл бұрын
There are likely other Turing Machines besides this one. As long as the formal prerequisites are met, you can have different game elements represent the parts of the machine. One of the tricky parts is that none of the players may act of their own will, so you would have to set up the board in a way that no human interaction is possible. The game must basically play itself. The only part where human interaction is allowed is during the setup phase. Here we have to take control of the game starting with the first move to prevent the opponent from messing with our setup. Once the setup is done, we remove our own free will from the game and the machine starts running. I probably didn't understand your setup very well, could you elaborate a bit? In your 2-player setup, what would be the tape, how would you read/write on the tape and how would you represent the transitions in a way that ensures that the game plays itself without any possible player choice? Would this be a completely different approach or a modification of the current one? If you wanted to have 20+ states, then you could use a different Rogozhin UTM, like the UTM(24,2) or the UTM(10,3). However, you would have to find a way to switch between 20 different states based on the current position of your tape representation, all within the rule set of M:TG on auto-play.
@bivsvideos
3 жыл бұрын
Not gonna lie, some of this went over my head (most of it from how complex the steps of translation between the original Turing machine and the UTM were) , but it seems the majority of the problem of using magic as an actual functioning Turing machine comes from two sources: the function of the Turing machine itself causing too many triggers a player must take (which may or may not be fixable), and the fact that the current setup used a Rogozhin(2,18), which highly bloated the input tape. My questions about the programming side are way beyond my programming skill: If we used a different Rogozhin UTM (this might require a very different deck, but let's say hypothetically it did not), would this have a significant effect on the computational speed of a wizards cardboard machine? Could one of Rogozhin's UTMs get the MTG imput tape small enough to make doing a computation by hand feasible (again, assuming the original deck worked)? Which UTM(s) would do this the best? These are a little more magic related questions: If switching to a different UTM would significantly reduce computational time, would we be able to use the same deck, just with a different setup? This would clearly be easier to set up if both players used specific decks built to establish the Turing machine, but if both players had a 'Turing deck' do you think it would be easier to run too? As someone who likes programming and loves magic, I'm very curious if there's enough potential for improvement with a cardboard Turing machine to the point where we may be able to actually compute something at a table.
@Deez-Master
3 жыл бұрын
hm what would be the shortest computable program? are there any that could be played in a reasonable amount of time? I am guessing not lol
@cerno_b
3 жыл бұрын
The shortest Turing Machine is actually pretty boring. It is called the trivial Turing Machine and has only one state that is also the end state. It has no transitions and once it starts, it immediately stops without doing anything. So whatever is on your input tape is also your output tape. Starting from there you could think of Turing Machines that do slightly more, but I think unary addition is already one of the most simplistic Turing Machine possible.
@nonnonsence
3 жыл бұрын
You really should have tossed down two cards at the end. HERES YOUR TEST ONE, TWO! Humans for the win.
@williamgreen4982
3 жыл бұрын
ABC easy as a 10110111 I don’t even want to think about how not simple do re mi might be. abc 10110111 do re mi baby you and me girl
@thathemmer7598
3 жыл бұрын
Just perform each interaction in 1 microsecond, then you only have to use 18 days per head movement
@thathemmer7598
3 жыл бұрын
Picosecond per interaction leads to around 2 seconds per head movement
@AlexMonas
3 жыл бұрын
Hey Jan, I love your work. I'm currently working on a modeling language simplifying the effects of MtG cards in order to me able to compute millions of games of MtG in seconds. If you would like to have a quick chat, let me know here how to reach you or contact me via [email protected] Thanks Alex Monas
@PasseScience
3 жыл бұрын
There is in fact a way to see a result on this Magic Turing Machine, it's to tweak the transitions to have something that compute an easy fonction! As long as you keep 2 states it's easy to adapt, you can probably do a fast incrementor with it, and see (in a human time frame) the machine counting in binary by example. (Yes it's not a UTM anymore but we can actually see a computation everyone can understand)
@Hoscitt
3 жыл бұрын
Really good video, great antidote to the vacuous banality that is the majority of KZitem. This is how it should be used! Good work! 👍
@cerno_b
3 жыл бұрын
Thank you for your kind words.
@CelticKnight2004
3 жыл бұрын
My brain has melted and run out my ears.
@johannesstangl4734
4 жыл бұрын
Incredibly cool video, thank you for demonstrating this! I would have liked to ask the Magic The Gathering: Arena team if they would be in to simulate a turing machine in the online Magic version. But this would probably be infeasibly slow, if no faster compiler can be created.
@cerno_b
3 жыл бұрын
Thanks man. Yes, unfortunately it's not easily done. If you could find a better way to describe a TM as a 2 state TM (even with more than 18 symbols) there might be a way, but that's usually done via the proof I described. I thought maybe there's a way to build a different UTM into MTG, one using e.g. 4 states, by using a more complex version of the phasing mechanic, that might help, but I would assume that the resulting conversion would still be very complex. At least we could find more TMs to use directly that way. Native 2 state TMs that do useful stuff are very rare.
@Emilstekcor
4 жыл бұрын
I'm late here, but you've gotten yourself a subscriber cause this is amazing.
@aceundead4750
4 жыл бұрын
Dont try doing this in your head after watching. Iv got a headache now, because my brain wanted to do more equations
@gewinner5379
4 жыл бұрын
It would be funny to use MtgOnline for that. Although there are many annoying buggs ^^
@karakedi3726
4 жыл бұрын
This video is perfect, and deserves more credit for sure
@H1nted
4 жыл бұрын
As a physics masters student/ magic plauer this video is really iteresting in terms of substance,the only thing this hadn't blow up is because it requires a lot of attention span for a non scientific person so that s an issue and it requires someone who plays magic to watch the hole thing to find out how it all comes together, don't get discouraged the video is really well done it's just the audience you want to reach is really specefic
@Drawoon
4 жыл бұрын
So, using the UTM(2, 18) is pretty arbitrary right? If we can make a UTM with more states and as many symbols in magic, then we'd cut down on the amount of tokens significantly.
@willdriver7542
4 жыл бұрын
Found you through Kyle Hill. This really helped me understand how Turing machines actually work. Thank you
@KumaBones
4 жыл бұрын
Fascinating video!
@blim8777
4 жыл бұрын
"Simulating a Magic Turing machine by hand is out of the question"? Simulating it with this procedure, of course. I hope that, one day, much simpler ways to implement a Turing machine in MtG could be found. Anyway all of this is wonderful!
@BatouOfNexus
4 жыл бұрын
Great job! Very impressive work! Now all we need is a LLVM module so we can compile iPhone apps into a game of Magic the Gathering.
@von_nobody
4 жыл бұрын
First of all, idea of manually updating token is stupid, with 5 cards I would simply give up this silly endeavor. First of all, this need be tokens to mark correctly power of creature? No, if both sides agree you can easy image different "encoding" that still preserve MTG state and make it possible to pull off in real life. Solution is simple: stack cards As each creature have power that is equal to its position in Turning tape then why not represents this same on board? You have two stacks of cards, left and right, each creature on top have 3/3 stats, creature beneath have 4/4 and another lower 5/5 etc. As for most time they do not do any thing, you can simply ignore whole stack beneath, and only interact with top. Taking one creature from top is equal to taking -1/-1 damage for all units beneath, and adding one is equal to adding +1/+1 for all creatures. With this simply convention you change O(n) operation to O(1) without breaking any MTG rules. This could be even extended to have 5 different stacks of cards with different color, this mean more a multiple stack machine than classic Turing machine.
@skelten454
4 жыл бұрын
I love how this shows how you used lots of different software and pieces to make a finished product.
@skelten454
4 жыл бұрын
I very much enjoy and appreciate that you include links in the description. This help show that you are credible and know what you are talking about. I never second guessed you but it is good to see this aspect a responsibility taken. I hope this is an awesome start to your time creating content in whatever form it takes.
Пікірлер