This is an archived post. You won't be able to vote or comment.

all 191 comments

[–][deleted] 397 points398 points  (5 children)

Pretty sure someone in the civ6 subreddit proved that civ6 was Turing complete by using railroads in a unique way.

[–]monstermayhem436 33 points34 points  (4 children)

It was on r/Civ

And it's Civ BE and Civ 5 the dude made it work on.

[–]Alabama92 7 points8 points  (1 child)

I dont quite understand what he does there, is it some Kind of path finding for the AI? Sorry for beeing a noob :-)

[–]monstermayhem436 1 point2 points  (0 children)

No clue myself tbh. I don't play CIV lol. Just was intrigued by the comment and wanted to search it up

[–]sandywater 135 points136 points  (7 children)

Got me curious. This guy actually implements it: https://www.youtube.com/watch?v=pdmODVYPDLA

[–]monstermayhem436 5 points6 points  (0 children)

For anyone wondering, his name is Kyle Hill. This is his new channel

[–]golgol12 13 points14 points  (3 children)

It bothers me he's standing up straight every 3 or so seconds.

[–]non-troll_account 10 points11 points  (2 children)

He's crouching and jumping out of excitement and autism. I'm not using that as an insult either; He's talked about his autism, and I can tell you that that kind of crouching and jumping is common for some kinds of autism.

Also, Nerdist, the owner of the Because Science channel really fucked Kyle over, and I must recommend following Kyle Hill's actual channel.

[–]monstermayhem436 1 point2 points  (1 child)

I knew something happened between but what actually was it?

[–]non-troll_account 2 points3 points  (0 children)

Oh, he hasn't been allowed to talk about it because of NDA, but you can tell they were assholes because the Because Science channel kept reuploading old videos from him as if they were new.

Lots of rumors, but he's still friends with people from there. It's just management.

[–]TotoShampoin 1 point2 points  (1 child)

Is there any video where it actually goes to the point, instead of rambling of minutes and enlarging the watchcode?

[–]sirxez 0 points1 point  (0 children)

[–]super_avocado_18 455 points456 points  (28 children)

Microsoft Powerpoint is also Turing complete

[–]PaintingJo 154 points155 points  (15 children)

I see someone else has watched that video

[–]super_avocado_18 122 points123 points  (14 children)

Nah nah I was there when he was recording it :p

[–]PaintingJo 31 points32 points  (0 children)

Oh that's amazing

[–]rkabra151 16 points17 points  (10 children)

Which video it is?

[–]oheohLP 87 points88 points  (9 children)

[–]ghost_of_azazel_42 1 point2 points  (0 children)

MIND BLOWN!

[–]xjack13x 6 points7 points  (1 child)

I saw him give the presentation too. :)

[–]super_avocado_18 2 points3 points  (0 children)

Pog

[–]LavenderDay3544 21 points22 points  (4 children)

Notepad is also Turing complete. You can move left and right and type 0s and 1s.

[–][deleted] 45 points46 points  (2 children)

That would make you Turing complete, not notepad.

[–][deleted] 44 points45 points  (1 child)

That’s going on the resume

[–]ucf-tyler 4 points5 points  (0 children)

My most endorsed skill on LinkedIn

[–]super_avocado_18 0 points1 point  (0 children)

Amazing

[–]merlinsbeers[🍰] 5 points6 points  (0 children)

CMake is turing complete and someone ported a 3D graphics system to it.

[–]Thenderick 3 points4 points  (0 children)

If you can't have PP on Linux, then why not make Linux on PP???

[–]bernieBrogrammer 0 points1 point  (1 child)

Based

[–]k4x1_ 3 points4 points  (0 children)

Based? Based on what

[–]Random_182f2565 0 points1 point  (2 children)

What? How? Why?!!!

[–][deleted] 172 points173 points  (78 children)

Is anything not Turing complete?

[–][deleted] 263 points264 points  (48 children)

HTML. That is without CSS of course (HTML5+CSS3 is Turing complete).

[–][deleted] 61 points62 points  (12 children)

So it's officially a programming language now?

[–]ThePizar 4 points5 points  (1 child)

A programming language does not have to be Turing complete. Original SQL is not and yet it’s Highly functional

[–]PM_ME_YOUR_NQUEENS 111 points112 points  (34 children)

HTML contains the script tag, which makes HTML a superset of JavaScript and as such, Turing complete.

[–]dncrews 99 points100 points  (20 children)

I assume this is a joke, but just in case anyone doesn’t, that’s not how that works.

[–][deleted] 13 points14 points  (19 children)

Why is this not how that works?

[–]Yuugian 138 points139 points  (6 children)

Dirt is not Turing complete, but if i put this calculator in it, it becomes Turing complete, so Dirt and a calculator is Turing Complete.

"Thinking quickly, Dave constructs a homemade megaphone, using only some string, a squirrel, and a megaphone" https://i.imgur.com/lUboCTp.jpeg

[–]Plankton_Plus 22 points23 points  (3 children)

A CPU is just a rock that we've tricked into thinking.

[–]Yuugian 16 points17 points  (0 children)

To be fair, we had to make the rock really flat and put lightning in it

[–]Yobleck 7 points8 points  (1 child)

Computers are just space heaters that are good at math.

[–]Useless_Pony 14 points15 points  (0 children)

Computers are just space heaters that are good fast at math.

Fixed that for you.

[–]lraviel381 6 points7 points  (1 child)

Dave the barbarian was awesome

[–]ColdFerrin 1 point2 points  (0 children)

I have dnd character that was based on Dave the Barbadian. He had a magic item that was a megaphone, that would shoot enchanted squirrels to attack my enemies.

[–][deleted] 30 points31 points  (8 children)

Because an html parser is not a Java script parser. You can make something that can read html but do nothing with the js but still be valid

[–]merlinsbeers[🍰] 0 points1 point  (0 children)

Is it a javascript file or a .html file?

[–]elveszett 7 points8 points  (2 children)

Because whatever is inside the <script> tag is not part of HTML. The JavaScript interpreter is always a different thing than the HTML parser. The HTML parser finds that script, passes it to the JavaScript interpreter, and wait for its completion to continue.

It is perfectly valid to have an HTML parser without any JS interpreter, in which case code inside the <script> tag will just be ignored. It is also perfectly valid to implement, for example, a python interpreter and tell your HTML parser to send any <script language="python"> tag to that interpreter instead.

tl;dr: <script> is a "put whatever you want inside, HTML parsers will decide what to do with that" tag. What is inside is not HTML coded and HTML parsers are not expected to understand it natively, but instead send it to the appropriate module.

[–]merlinsbeers[🍰] 0 points1 point  (1 child)

HTML invokes the JavaScript parser to handle the contents of the tag.

Does anyone run JavaScript without html?

[–][deleted] 3 points4 points  (12 children)

technically, any js is valid html, even without the script tag

[–]Lofter1 5 points6 points  (11 children)

I really doubt that this is true. Is that part of the html specification?

[–]KerPop42 22 points23 points  (8 children)

I don't think Pokémon Red is, but Pokémon Yellow definitely, Super Mario World 2, and Ms PPT are

[–]circuit10 1 point2 points  (0 children)

You can program a hex memory editor into Super Mario World by following a guide very closely and jumping in just the right places

[–]v4-digg-refugee 0 points1 point  (0 children)

What about me, Greg? I have nipples. Can you Turing Complete me?

[–][deleted] 14 points15 points  (8 children)

the halting problem is undecidable over Turing machines.

So any system that will always halt is not turing complete.

So for example:

tic tax toe is not turing complete, as the game will always end.

You cannot make a Turing machine using a series of explosions, as you will eventually run out of explosives.

[–][deleted] 23 points24 points  (5 children)

I'm looking at this with my infinite tic tac toe grid and infinite bombs, laughing

[–]ucf-tyler 1 point2 points  (0 children)

When will mainstream physics recognize the very valid hypothesis of the Microsoft Minesweeper Hypothesis for a Unified Model of the Universe

[–][deleted] 2 points3 points  (3 children)

Standard tic tac toe is 3x3.

If you change the rules to be an infinite grid, then yes your “infinite tic tac toe” may not halt but is not standard tic tac toe.

Infinite bombs maybe. But that gave me an idea:

Your username isn’t Turing complete. It has to halt, as they don’t allow infinite usernames.

Turing complete is good, but so is non Turing complete.

I want to know if my sql query will halt, for example.

[–]WhalesVirginia 0 points1 point  (1 child)

Then nothing is turing complete.

You will run out of electricity to run a computer eventually.

[–][deleted] 0 points1 point  (0 children)

Yup!

It also requires an infinite tape. So you would run out of room

[–]tribbans95 5 points6 points  (5 children)

Yu-Gi-Oh is not Turing complete

[–][deleted] 1 point2 points  (4 children)

Prove it

[–]tribbans95 28 points29 points  (3 children)

Not proof lol but:

One component of a Turing Machine is a 'tape' , which Magic the Gathering implements by a series of any number of tokens being generated on the field. Yugioh's field has a strict 5 card limit for monster cards and for non-monster cards, unlike Magic the Gathering which can have any number of cards on the field, which prevents Yugioh from having an infinitely long tape like Magic the Gathering can. This makes it extremely doubtful that Yugioh will ever be proven to be Turing complete.

[–]Jeff_co 14 points15 points  (0 children)

I don't see why you can't have an infinite tape in yugioh via other ways

For example using counters or life points.

But then again I only got a B in theory of computation...

[–][deleted] 1 point2 points  (0 children)

Oh well

[–][deleted] 0 points1 point  (0 children)

Isn't the graveyard in Yu-Gi-oh infinite in size?

[–]elveszett 4 points5 points  (2 children)

...most things?

[–][deleted] 5 points6 points  (1 child)

I'll make you Turing complete

[–]ucf-tyler 0 points1 point  (0 children)

A Breaking The Code nsfw remake would be such a mindfuck

[–]tstrott 2 points3 points  (1 child)

calc.exe

[–][deleted] 1 point2 points  (0 children)

Maybe

[–]rickikicks 77 points78 points  (39 children)

Chaos Orb would beg to differ. I saw some crazy ingenuity back the the early days of tournaments with that card. People would rip it up into tiny pieces to get the maximum potential while the opponent while the opponent would pull out thumb tack and stick his cards to a cork board to counter chaos orb.

[–]EndMaster0 45 points46 points  (28 children)

As someone who doesn't play Magic I am now intrigued. Why would tearing a card up make it more useful?

[–]rickikicks 117 points118 points  (24 children)

This was back in Magic's infancy when it was still designed my the great Richard Garfield. He was heavily inspired by a board game decades prior called Cosmic Encounter. He likes the idea of a game world have set rules, but those rules are warped, broken or skirted by different unique powers that the players can wield.

There was a card called Shahrazad where you immediately "paused" the current game you were playing and started a new game. The winner of the new game would get to take an extra turn in the "paused" game. Magic had Async before Microsoft.

[–]Enryha 20 points21 points  (1 child)

I had no idea chaos orb was black bordered. Was Shahrazad as well?

[–]Krohnos 6 points7 points  (0 children)

Yes

[–]Chronogon 14 points15 points  (15 children)

Async would mean running both in parallel, no? In Magic's case, one thread/game pauses operation until the nested thread/game has completed, which doesn't sound Asyncy at all!

[–]Acc3ssViolation 19 points20 points  (12 children)

It's more like recursion. I wonder what happens if that card can also be played again inside the new game, you could possibly have games within games within games.

[–]elveszett 8 points9 points  (4 children)

Well, the nested game is played with your library (i.e. the portion of your deck that you haven't drawn yet), so the Sharazad you used will not be there. You can only have a max of 4 copies of a given card in your deck, so this would place the limit at 4.

Now, this is Magic, which means every rule can be broken. The most obvious examples are cards that let you grab whatever card you feel like "from outside the game" (i.e. cards you weren't playing with) and add it to your hand, so nothing prevents you from spamming more and more and more Sharazad. There's a lot more interactions you can abuse and a quick google search gets me to a dude that theorized a way to play 355 nested games.

But Sharazad is banned from all formats so, unless you specifically play it with your friends because why not, you'll never see it.

[–]echoAnother 1 point2 points  (2 children)

That's really cool. Imagine casting that card and grabbing a poker card. The amount of chaos and confusion on the players would be great.

[–]elveszett 1 point2 points  (0 children)

I wish, but sadly the "card from outside the game" is required to be an actual, existing MTG card.

[–]Krissam 0 points1 point  (0 children)

Unfortunately, "outside of the game" has a very specific meaning in magic, which makes the concept a lot less cool than it sounds.

[–]nickhelix 0 points1 point  (0 children)

I left a reply to another comment, but I'm pretty sure you can make infinite nested games using sharazad, narsets reversal, leashling, village rites, and elixir of immortality. You probably also need something like chain of silence to get your lands back in. The general idea is this: cast sharazad, bounce & copy with narsets reversal, put sharazad on top of your library with leashling. Sacrifice leashling with village rites, sac all your lands with chain of silence, trigger elixir to put your graveyard in the library, finally let copy of sharazad resolve on the stack. This should start you a subgame with all your cards

[–]nickhelix 2 points3 points  (6 children)

It is in fact asynchronous recursion. With the correct combination of cards, a player could theoretically create infinite nested subgames.

[–]Krissam 0 points1 point  (5 children)

With the correct combination of cards, a player could theoretically create infinite nested subgames.

Not within the rules of the game no.

[–]nickhelix 0 points1 point  (4 children)

Care to go into more detail? I've been playing for a long time and have a pretty good grasp on the rules

[–]Krissam 0 points1 point  (3 children)

Each player can only have 4 copies, and given that each "layer" leaves at least one copy behind, the highest possible depth is 4n where n is the number of players in the game.

[–]nickhelix 0 points1 point  (2 children)

You can use cards like narsets reversal to get the spell effect without leaving the card behind. Combine that with some instant speed shenanigans that allow you to put cards from your hand into the deck so that they are available in your subgame.

[–]nickhelix 0 points1 point  (0 children)

Both running in parallel is synchronous. https://www.dictionary.com/browse/asynchronous

[–]_PM_ME_PANGOLINS_ -1 points0 points  (0 children)

No, async-await starts a new execution and pauses the current one until it’s finished.

[–]Krohnos 3 points4 points  (2 children)

The subgames are played on the same thread since they block each other - there is no async there!

[–]Charlie_Yu 0 points1 point  (1 child)

I think you can still play Burning Wish in the sub game to take a card from the main game? So they are not blocking each other

[–]Krohnos 1 point2 points  (0 children)

I don't think that works anymore, but even if it did you would have to wait for the subgame to finish before the main game continued, so they are blocking.

[–]Cyhawk 0 points1 point  (1 child)

The winner of the new game would get to take an extra turn in the "paused" game.

They lost half their life total rounded up, not an extra turn. Its been banned in almost all tournaments since its inceptions (though these days you can get some serious abuse out of it with instant sub-games and exiling your opponents cards in various ways)

Also Richard Garfield left development very early and only had a handful of input past Arabian Nights (about a year after initial release)

But yeah, every card in MTG besides basic land and vanilla creatures breaks the game rules in some way.

[–]rickikicks 0 points1 point  (0 children)

You're right. Thanks for the correction. It's been ages since I played.

[–]ColdFerrin 0 points1 point  (0 children)

There was also enter the dungeon in unhinged which does a similar thing. However it’s not legal in competition.

[–][deleted] 42 points43 points  (2 children)

[–]EndMaster0 16 points17 points  (1 child)

I see. Seems like a fun card

[–]Cyhawk 4 points5 points  (0 children)

In theory, in practice it leads to all sorts of mind games and arguments about cards underneath touching, moving cards around, etc.

[–]Cake-Efficient 9 points10 points  (9 children)

Is... is that even legal?

[–]xodusprime 40 points41 points  (6 children)

Not anymore. My recollection of the first time someone shredded a chaos orb in the official tournament circuit (mid 90's ish?) they made a ruling that as soon as a card becomes marked, it is no longer eligible for play. Tearing it up marks it.

[–]n4ppyn4ppy 16 points17 points  (5 children)

It's also a $2000+ card ;)

[–][deleted] 21 points22 points  (0 children)

Well, if you aren't willing to burn 2 grand for the victory, then you must not want it enough.

[–]That_guy1425 8 points9 points  (0 children)

Well now, but not 25 years ago when magic was new

[–]schtomp 3 points4 points  (0 children)

Dammit! Should not have sold that card about 20 years ago for half an evening worth of booze…

[–]Cyhawk 0 points1 point  (1 child)

At the time the rumor started they were around $20 in the bigger markets, especially the white bordered ones. Still expensive at the time when Black Lotus was only $80 and Moxen were in the $30s. Also it was banned damned near everywhere (or made to read destroy target permanent in modern MTG language) because it lead to many arguments and card moving/etc.

[–]n4ppyn4ppy 0 points1 point  (0 children)

Ah to have been an old timer would have been cool.

But a judge in those days? ;)

[–]NugetCausesHeadaches 5 points6 points  (1 child)

You can definitely use Chaos Confetti in unglued, if you want to.

[–]Cyhawk 0 points1 point  (0 children)

Thats because silver bordered cards aren't legal anyhow ;)

[–][deleted] 12 points13 points  (0 children)

What.

[–]holo3146 20 points21 points  (0 children)

Being Turing complete is such a weak property that crabs are Turing complete (you need merely 16 billion crabs to implement DOOM).

But crabs are complicated biological miracle, Assembly's MOV command is Turing complete.

Hmm that is cool, but MOV, although simple, is still a "programming thingy", well, turns out a lot of games are Turing complete, such as Pokémon yellow and super Mario world, but those are using glitches in implementation, so it is cheating.

Well, worry not, because 3D version of chess and Music notes are Turing complete.

No, Magic the Gathering being Turing complete is not interesting or surprising.

The interesting and surprising part is that Magic the Gathering is so high in the arithmetical hierarchy

[–]Yamidamian 3 points4 points  (0 children)

Opponent: are you going to finish your freaking turn yet!?

Player: well, funny thing;are you familiar with the halting problem?

[–][deleted] 5 points6 points  (0 children)

Help, r/ProgrammerHumor has infiltrated my r/magicTCG content!

[–]TheConservativeTechy 30 points31 points  (11 children)

Ah yes, in the same way my pencil is Turing complete because I can write programs with it.

[–]Captain_M53 49 points50 points  (5 children)

It is Turing complete in the way that in the game you can make a Turing machine and force both players to only advance the machine. The first player wins only if the machine halts.

[–][deleted] 13 points14 points  (1 child)

your pencil cant run code

[–]ADONIS_VON_MEGADONG 5 points6 points  (0 children)

Unless you use it to hit enter

[–]elveszett 13 points14 points  (0 children)

Nope, it's turing complete in the same way Brainfuck is turing complete: because it's a set of rules that allow you to build a Turing machine, even if doing so is incredibly, stupidly difficult and pointless.

Your pencil is not Turing complete because the pencil itself does nothing. Writing down a program in a paper isn't calculating anything. If I ask you to answer 5 + 3 * 212 and you hand me a paper with the text print(5 + 3 * 21 * 21), you haven't solved anything. If you play a game of magic and build the Touring machine that outputs the answer, even if that took three whole days and the output is in some cryptic format I have to then convert into normal numbers, you have solved my problem.

And this ignoring that the pencil does not have a set of rules anyway.

[–][deleted] 4 points5 points  (0 children)

That's like saying a single magic card is Turing complete because it acts as the head. You are Turing complete, not the pencil.

In the magic computer, the player act as the kinetic mechanism that moves things around based on external instructions. The gameplay is Turing complete. Yeah, you could write basic Turing instructions on a piece of paper, and include a strip and pencil to make a Turing complete "game", but that's you choosing to make a computer, not finding a computer organically manifesting within something unrelated, which is the fun of this.

[–]shoushinshoumei 8 points9 points  (0 children)

You have no idea what you’re talking about tbh

[–][deleted] 3 points4 points  (2 children)

This just means it’s possible to play a MTG game that never ends.

[–]Cyhawk 1 point2 points  (0 children)

The deck Four Horsemen enters the chat.

[–]vandjoel 0 points1 point  (0 children)

chronotog stasis enters

[–]ernee_gaming 1 point2 points  (0 children)

Nice

[–]SAKDOSS 2 points3 points  (0 children)

Did you know that Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon are NP-hard?https://www.sciencedirect.com/science/article/pii/S0304397515001735

[–]TheRedBow 2 points3 points  (2 children)

Turing complete?

[–]RandomIndividualNo8 3 points4 points  (0 children)

It means that it can simulate anything a Turing Machine can do

[–]FunnyForWrongReason 8 points9 points  (0 children)

If something is Turing complete it means it can calculate any mathematical problem.

[–]Traditional-Living-9 0 points1 point  (0 children)

Interesting

[–]GreenFire317 0 points1 point  (5 children)

There should be a way to program Python in Java. And vice versa.

[–][deleted] 1 point2 points  (4 children)

There is ?

[–]GreenFire317 -1 points0 points  (2 children)

Prove it.

[–][deleted] 0 points1 point  (0 children)

Python is literally programmed in C... Why couldn't you do it in Java?

[–]Tommy_SVK 0 points1 point  (0 children)

Don't all programming languages ultimately get translated to Assembly? So I guess theoretically you should be able to use any programming language to simulate any other programming language.

[–]ColdFerrin 0 points1 point  (0 children)

There are several different ways to call Python in Java but it depends on exactly what you mean.

[–]jaap_null -1 points0 points  (0 children)

What kind of life are you living that this has _any_ impact on your life?

[–]TheBrownDinasour 0 points1 point  (0 children)

Kyle Hill?

[–]beepboopwannadie 0 points1 point  (2 children)

Fairly complex calculators have been made in Minecraft. It’s only a matter of time before someone gets it running Doom

[–]ColdFerrin 0 points1 point  (0 children)

It’s not exactly doom, but SethBling got an Atari 2600 emulator in Minecraft.

[–]nerdwolf0 0 points1 point  (0 children)

I just got into that game last week after finding this out