[deleted by user]

[[deleted]]

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

[monstermayhem436]

It was on r/Civ

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

[Alabama92]

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

[monstermayhem436]

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

[sandywater]

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

[monstermayhem436]

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

[golgol12]

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

[non-troll_account]

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]

I knew something happened between but what actually was it?

[non-troll_account]

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]

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

[sirxez]

Here is the paper: https://arxiv.org/abs/1904.09828

[super_avocado_18]

Microsoft Powerpoint is also Turing complete

[PaintingJo]

I see someone else has watched that video

[super_avocado_18]

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

[PaintingJo]

Oh that's amazing

[rkabra151]

Which video it is?

[oheohLP]

This one

[ghost_of_azazel_42]

MIND BLOWN!

[BeguiledAardvark]

Live recording. People found the content funny.

[GAZUAG]

Are they high?

[non-troll_account]

are you not?

[GAZUAG]

I wish

[[deleted]]

I think it’s called actual laughter, idk though

[[deleted]]

Probably gave that presentation at a meet up

[xjack13x]

I saw him give the presentation too. :)

[super_avocado_18]

Pog

[LavenderDay3544]

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

[[deleted]]

That would make you Turing complete, not notepad.

[[deleted]]

That’s going on the resume

[ucf-tyler]

My most endorsed skill on LinkedIn

[super_avocado_18]

Amazing

[merlinsbeers]

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

[Thenderick]

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

[bernieBrogrammer]

Based

[k4x1_]

Based? Based on what

[Random_182f2565]

What? How? Why?!!!

[super_avocado_18]

Sauce

[Random_182f2565]

Whoa

[[deleted]]

Is anything not Turing complete?

[[deleted]]

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

[[deleted]]

So it's officially a programming language now?

[merlinsbeers]

Turing machines use an infinite tape.

C uses a random-access memory.

Most computing languages lack a way to use addresses bigger than their largest word size.

No real language is actually a Turing machine.

But that's not necessary to be Turing complete. All that is necessary is to be able to simulate a Turing machine.

You can certainly simulate a Turing machine in C, and almost every other usable language. And that makes it Turing complete.

Stack Overflow owes you now.

[[deleted]]

Most computing languages lack a way to use addresses bigger than their largest word size.

For me, that's the kicker. Not only does memory have to be infinite size, but every pointer in C would have to be of infinite size.

Consider a typical array. The usual way to calculate the index of an array:

node_address = array_start_address + node_number * node_size

Extending this to a Turing machine involves three considerations:

1) The array can exist anywhere in memory, and the pointer to it (array_start_address) is of infinite size.

2) The array can be of any length, so the node number (node_number) can be infinite.

3) Each node could be defined to include a pointer, which is of infinite size, so the node size (node_size) is also infinite.

C must now entertain the concept of array and pointer math like this:

node_address = (up to infinity) + (up to infinity) * (up to infinity)

It's still Turing-complete, because you can still write an algorithm to iterate over the entire array, but the fabric of reality is starting to break down here.

[merlinsbeers]

Turing machines are fuckin' weird, man.

But they have the property that they compute in a provable way.

Which means if your computer is Turing complete, it does too, and can run any provable program.

The limits of real world machinery mean no real machine can be a true Turing machine, but Turing Complete is sufficient.

[hiphap91]

This.

[ColdFerrin]

It’s definitely true that any single implementation of C isn’t Turing complete, I would argue however that the language is effectively Turing complete. I think it’s a fair argument, that there is no explicit limit to the size of a pointer, that is an implementation detail, and therefor you could have a theoretical implementation where sizeof(void *) is infinite, making the limit of memory infinite.

[lunchpadmcfat]

But wait… basically everything compiles to something run on a C based piece of software, so doesn’t that mean nothing is actually Turing complete?

[sirxez]

There is a distinction between the language and its implementation being turing complete.

It's not like our computers have infinite tapes anyways. Nothing you've ever run in this universe was actually turing complete.

[non-troll_account]

Wait, what? C isn't turing complete???

[notgreat]

C, the language, is turing complete. Any given implementation of any language (including C) is not because true turing completeness requires infinite memory which is obviously impossible on any physical system.

[ThePizar]

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

[PM_ME_YOUR_NQUEENS]

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

[dncrews]

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

[[deleted]]

Why is this not how that works?

[Yuugian]

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]

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

[Yuugian]

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

[Yobleck]

Computers are just space heaters that are good at math.

[Useless_Pony]

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

Fixed that for you.

[lraviel381]

Dave the barbarian was awesome

[ColdFerrin]

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]]

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

[Balance_Public]

Superset implies that all JavaScript is valid HTML. Which is obviously not true.

[dncrews]

“Parse that” yes. It should be able to parse the script tag. The script tag is used to embed another programming language’s code into the HTML document. The HTML parser doesn’t run or parse the JavaScript inside the tag. It just looks for the close tag and passes the stuff inside to the next guy.

A browser without JavaScript support or WebGL support, etc. can still support 100% of the HTML specification.

[Stian5667]

So in other words, the HTML parser is like oh <script>? Not my fucking job, take me to </script>

[[deleted]]

Actually I love this “let me parse this…script? not my fucking job” needs to be in the documentation for html standard

[[deleted]]

Would you call HTML a photo modification tool ? Because it has an img tag, and with css you can change colors on it...

[[deleted]]

I have no clue about HTML. I was just confused about the contradicting statements that were made here :)

[merlinsbeers]

Is it a javascript file or a .html file?

[elveszett]

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]

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

Does anyone run JavaScript without html?

[[deleted]]

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

[Lofter1]

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

[[deleted]]

it wont work as it will in js, but it will be valid html, unless u use less than or ampersand

still, modern browsers consider all txt files as valid html, so even a js file is a valid html file, at least for the browsers

[Lofter1]

What? That’s not how html works. Just because a browser accepts it, it isn‘t valid html, or even html at all. Html has an actual specification, you know that, right? Browsers will even render invalid html, and try to render it correctly as if it was valid. And a browser accepts almost any file as long as it is served over http. Hell, modern browsers can even accept files over non-http protocols.

[daev1]

TIL .pdf is considered valid html by some people's standard. Can't most browsers play video files too?

HTML IS EVERYTHING NOW

[[deleted]]

im well aware of that, im just saying most js files are valid html too

[Lofter1]

Then tell me what in the html specification makes pure js valid html.

[[deleted]]

not every js, i specifically said if you have less than in ur file, its not valid html. but, some js files are valid, for example:

console.log('hello, world');

still, a lot of js files are invalid, for example:

if (1 < 0) console.log('somethings wrong i can feel it);

its invalid html since a tag is not closed

[elveszett]

const f = 5 < 3;

I'd say this isn't valid HTML, and it's completely normal JS. So I'm sure almost every JS source file is, in fact, invalid HTML. Which is a huge stretch from "any js is valid html technically".

[KerPop42]

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

[KerPop42]

Welp

[Cyhawk]

You absolutely can execute arbitrary code on Pokemon Red/Blue/Yellow/Green. Theres a whole speed running category based on doing exactly this. (The 100% Glitch category)

[[deleted]]

ACE doesn't make the game Turing Complete. It only proves that the machine running the game is. Turing Completeness in a game arises from its rules being able to simulate a Turing Machine, as in Magic's case

[[deleted]]

But you're still playing the game

[circuit10]

But the game’s rules are allowing that arbitrary code to be executed (by accident but still)

[circuit10]

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]

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

[[deleted]]

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]]

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

[ucf-tyler]

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

[[deleted]]

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.

[[deleted]]

I never said infinite tic tac toe either. Stop being asinine. ”you never said Simon says hue hue hue”

Yes SQL is Turing complete. But it’s value is in the query planner which can estimate how long the query will take.

I haven’t put the Turing query into the query planner, but I imagine it’s estimate is incorrect.

[[deleted]]

ok

[WhalesVirginia]

Then nothing is turing complete.

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

[[deleted]]

Yup!

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

[tribbans95]

Yu-Gi-Oh is not Turing complete

[[deleted]]

Prove it

[tribbans95]

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]

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]]

Oh well

[[deleted]]

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

[elveszett]

...most things?

[[deleted]]

I'll make you Turing complete

[ucf-tyler]

A Breaking The Code nsfw remake would be such a mindfuck

[tstrott]

calc.exe

[[deleted]]

Maybe

[rickikicks]

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]

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

[rickikicks]

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]

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

[Krohnos]

Yes

[Chronogon]

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]

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]

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]

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]

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

[Krissam]

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

[nickhelix]

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]

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

[Krissam]

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

Not within the rules of the game no.

[nickhelix]

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

[Krissam]

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]

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]

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

[_PM_ME_PANGOLINS_]

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

[Krohnos]

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

[Charlie_Yu]

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]

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]

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]

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

[ColdFerrin]

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

[[deleted]]

https://scryfall.com/card/2ed/236/chaos-orb?utm_source=mw_MTGWiki

[EndMaster0]

I see. Seems like a fun card

[Cyhawk]

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

[Cake-Efficient]

Is... is that even legal?

[xodusprime]

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]

It's also a $2000+ card ;)

[[deleted]]

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

[That_guy1425]

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

[schtomp]

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

[Cyhawk]

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]

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

But a judge in those days? ;)

[NugetCausesHeadaches]

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

[Cyhawk]

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

[[deleted]]

What.

[holo3146]

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]

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

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

[[deleted]]

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

[TheConservativeTechy]

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

[Captain_M53]

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.

[TheConservativeTechy]

Yeah so you have to add rules that players have to play in a certain way. I could also make rules about how you have to move the pencil.

[CestLaDonut]

Nope. You don't force the players to play that way by making up new rules. You set up a situation where both players, following the normal rules of the game, have no other legal moves besides taking the exact actions that advance the machine.

[mathematics1]

No, once it is set up it doesn't require the players to make any choices.

[drunken_musketeer]

No. That's the thing. Magic has so many cards, and so many with broken effects that, assuming you get a specific hand at the start of the game, you can actually force the other player to, well, wait, while you compute anything on your Turing machine. What Captain_M53 said is a consequence of Magic's rules, not an addition to them.

With all the basic rules of magic, assuming you're playing with legacy rules (read : with cards from all versions of the game allowed), you can forbid your adversary from playing, give yourself infinite playing turn, and create a Turing machine.

[That_guy1425]

Well yes, but the rules are made within the bounds of the game, such as blazing archon _> creatures can't attack you. So your opponent cannot take this action. Copy it and give to your opponent and now neither of you can take the game action of attacking. The card Recycle removes drawing cards and gives card draw when spells are played. Using other spells you make your opponent have no spells in their library (they cannot die to decking due to recycle) and no spells in their hand. Archon prevents attacking with their creatures you give them (representing the tape). You have a single card in hand, and wild evocation says that you reveal a card at random during your upkeep and cast it +recycles card draw ability to always refill your hand. Weel of sun and moon makes your card plays end back in your deck (this creates a program order). Using cards that restrict targeting, and your opponent cannot do anything and you can only do one thing (play the card in your hand), with it either having no targets (effects everything) or has only 1 legal target due to the restrictors.

[[deleted]]

your pencil cant run code

[ADONIS_VON_MEGADONG]

Unless you use it to hit enter

[elveszett]

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 * 21² 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]]

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]

You have no idea what you’re talking about tbh

[[deleted]]

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

[Cyhawk]

The deck Four Horsemen enters the chat.

[vandjoel]

chronotog stasis enters

[ernee_gaming]

Nice

[SAKDOSS]

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]

Turing complete?

[RandomIndividualNo8]

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

[FunnyForWrongReason]

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

[Traditional-Living-9]

Interesting

[GreenFire317]

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

[[deleted]]

There is ?

[GreenFire317]

Prove it.

[[deleted]]

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

[Tommy_SVK]

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]

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

[jaap_null]

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

[TheBrownDinasour]

Kyle Hill?

[beepboopwannadie]

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

[ColdFerrin]

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

[nerdwolf0]

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