Super Mario is mathier than you think
This title could be clearer and more informative.Try out Clickbait Shieldfor free (5 uses left this month).
MIT researchers have proven that certain Super Mario levels are undecidable — meaning no computer program can always determine whether Mario can complete them. By constructing 'counter gadgets' that simulate Minsky counter machines within game levels, the MIT Hardness Group showed Super Mario belongs to RE-Complete, the hardest complexity class for such problems. This places it beyond PSPACE and even harder than the traveling-salesman problem or integer factorization. The work uses reduction techniques and gadget theory, which have broader applications in robotics motion planning and chemical reaction network modeling.
22 Impressions