ਕਿਉਂ Super Mario ਜ਼ਿਆਦਾਤਰ ਐਲਗੋਰਿਦਮਾਂ ਨਾਲੋਂ ਗਣਿਤਕ ਤੌਰ 'ਤੇ ਵਧੇਰੇ ਗੁੰਝਲਦਾਰ ਹੈ

ਭਾਵੇਂ ਇਹ ਇੱਕ ਪਲੰਬਰ ਦੁਆਰਾ ਰਾਜਕੁਮਾਰੀ ਨੂੰ ਬਚਾਉਣ ਵਾਲੇ ਇੱਕ ਸਧਾਰਨ ਪਲੇਟਫਾਰਮਰ ਵਾਂਗ ਲੱਗ ਸਕਦਾ ਹੈ, ਪਰ Super Mario ਅਸਲ ਵਿੱਚ ਥਿਊਰੇਟੀਕਲ ਕੰਪਿਊਟਰ ਸਾਇੰਸ ਦੇ ਡੂੰਘੇ ਰਹੱਸਾਂ ਦਾ ਇੱਕ ਦਰਵਾਜ਼ਾ ਹੈ। MIT ਦੀ ਨਵੀਂ ਖੋਜ ਤੋਂ ਪਤਾ ਲੱਗਦਾ ਹੈ ਕਿ ਖੇਡ ਦੇ ਕੁਝ ਖਾਸ ਕੌਂਫਿਗਰੇਸ਼ਨ ਗਣਿਤਕ ਤੌਰ 'ਤੇ undecidable (ਅਨਿਸ਼ਚਿਤ) ਹਨ, ਜੋ ਉਹਨਾਂ ਨੂੰ ਮਿਆਰੀ ਕੰਪਿਊਟੇਸ਼ਨਲ ਸਮੱਸਿਆਵਾਂ ਤੋਂ ਕਿਤੇ ਵੱਧ ਗੁੰਝਲਦਾਰ ਕਲਾਸ ਵਿੱਚ ਰੱਖਦੇ ਹਨ।

PSPACE ਤੋਂ RE-Complete ਤੱਕ: ਗੁੰਝਲਦਾਰਤਾ ਵਿੱਚ ਇੱਕ ਵੱਡੀ ਛਾਲ

ਸਾਲਾਂ ਤੋਂ, MIT ਪ੍ਰੋਫੈਸਰ Erik Demaine ਸਮੇਤ ਖੋਜਕਰਤਾਵਾਂ ਵਿੱਚ ਇਹ ਸਹਿਮਤੀ ਸੀ ਕਿ Super Mario PSPACE ਗੁੰਝਲਦਾਰਤਾ ਕਲਾਸ ਨਾਲ ਸਬੰਧਤ ਹੈ। ਇਸ ਕਲਾਸ ਵਿੱਚ ਉਹ ਸਮੱਸਿਆਵਾਂ ਸ਼ਾਮਲ ਹਨ ਜੋ ਹੱਲ ਕੀਤੀਆਂ ਜਾ ਸਕਦੀਆਂ ਹਨ, ਪਰ ਜਿਵੇਂ-ਜਿਵੇਂ ਇਨਪੁਟ ਦਾ ਆਕਾਰ ਵਧਦਾ ਹੈ, ਉਹਨਾਂ ਲਈ ਮੈਮੋਰੀ ਅਤੇ ਸਮੇਂ ਦੀ ਇੱਕ ਅਸੰਭਵ ਮਾਤਰਾ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ। ਹਾਲਾਂਕਿ PSPACE ਸਮੱਸਿਆਵਾਂ ਮੁਸ਼ਕਲ ਹਨ, ਫਿਰ ਵੀ ਉਹ ਕਾਫ਼ੀ ਸਰੋਤਾਂ ਦੇ ਨਾਲ ਇੱਕ ਕੰਪਿਊਟਰ ਦੁਆਰਾ ਮੂਲ ਰੂਪ ਵਿੱਚ "ਹੱਲਯੋਗ" ਹਨ।

ਹਾਲਾਂਕਿ, ਵਿਦਿਆਰਥੀਆਂ ਦੀ ਇੱਕ ਟੀਮ—Hayashi Ani, Holden Hall, Ricardo Ruiz, ਅਤੇ Naveen Venkat—ਦੇ ਹਾਲੀਆ ਕੰਮ ਨੇ ਇਸ ਅਨੁਮਾਨ ਨੂੰ ਤੋੜ ਦਿੱਤਾ ਹੈ। ਲੈਵਲ ਐਡੀਟਰਾਂ ਅਤੇ Super Mario Maker ਦੀ ਵਰਤੋਂ ਕਰਕੇ, ਖੋਜਕਰਤਾਵਾਂ ਨੇ ਅਜਿਹੇ ਖਾਸ ਲੈਵਲ ਤਿਆਰ ਕੀਤੇ ਜੋ RE-Complete ਹਨ। ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਖੇਡ undecidable problems ਦੇ ਖੇਤਰ ਵਿੱਚ ਪ੍ਰਵੇਸ਼ ਕਰ ਚੁੱਕੀ ਹੈ। ਇਹਨਾਂ ਖਾਸ ਸਥਿਤੀਆਂ ਵਿੱਚ, ਇੱਕ ਅਜਿਹਾ ਕੰਪਿਊਟਰ ਪ੍ਰੋਗਰਾਮ ਲਿਖਣਾ ਗਣਿਤਕ ਤੌਰ 'ਤੇ ਅਸੰਭਵ ਹੈ ਜੋ ਹਮੇਸ਼ਾ ਸਹੀ ਅਨੁਮਾਨ ਲਗਾ ਸਕੇ ਕਿ ਮਾਰੀਓ ਸਫਲਤਾਪੂਰਵਕ ਫਲੈਗਪੋਲ ਜਾਂ ਕਿਲ੍ਹੇ ਤੱਕ ਪਹੁੰਚ ਸਕਦਾ ਹੈ ਜਾਂ ਨਹੀਂ।

Halting Problem ਨਾਲ ਸਬੰਧ

ਇੱਕ ਵੀਡੀਓ ਗੇਮ ਕਿਉਂ undecidable ਹੋ ਸਕਦੀ ਹੈ, ਇਹ ਸਮਝਣ ਲਈ, ਸਾਨੂੰ Alan Turing ਅਤੇ Halting Problem ਵੱਲ ਵਾਪਸ ਦੇਖਣਾ ਪਵੇਗਾ। Turing ਨੇ ਸਾਬਤ ਕੀਤਾ ਸੀ ਕਿ ਕੋਈ ਵੀ ਯੂਨੀਵਰਸਲ ਐਲਗੋਰਿਦਮ ਨਹੀਂ ਹੈ ਜੋ ਇਹ ਨਿਰਧਾਰਤ ਕਰ ਸਕੇ ਕਿ ਕੋਈ ਵੀ ਦਿੱਤਾ ਗਿਆ ਪ੍ਰੋਗਰਾਮ ਅੰਤ ਵਿੱਚ ਰੁਕ ਜਾਵੇਗਾ ਜਾਂ ਹਮੇਸ਼ਾ ਲਈ ਚਲਦਾ ਰਹੇਗਾ।

MIT ਖੋਜ ਟੀਮ ਨੇ reduction ਨਾਮਕ ਤਕਨੀਕ ਰਾਹੀਂ Mushroom Kingdom 'ਤੇ ਇਸ ਤਰਕ ਨੂੰ ਲਾਗੂ ਕੀਤਾ। Super Mario ਲੈਵਲ ਨੂੰ "gadgets" ਵਜੋਂ ਜਾਣੇ ਜਾਣ ਵਾਲੇ ਸਥਾਨਕ ਹਿੱਸਿਆਂ ਵਿੱਚ ਤੋੜ ਕੇ, ਖੋਜਕਰਤਾ ਖੇਡ ਦੇ ਮਕੈਨਿਕਸ ਦੇ ਅੰਦਰ ਗੁੰਝਲਦਾਰ ਕੰਪਿਊਟੇਸ਼ਨਲ ਲੌਜਿਕ ਦਾ ਸਿਮੂਲੇਸ਼ਨ ਕਰਨ ਦੇ ਯੋਗ ਹੋਏ। ਇਹ gadgets ਲੌਜਿਕ ਗੇਟਾਂ ਵਜੋਂ ਕੰਮ ਕਰਦੇ ਹਨ; ਜਦੋਂ ਉਹ ਪਾਈਪਾਂ, ਪਲੇਟਫਾਰਮਾਂ ਅਤੇ Goombas ਜਾਂ Spinies ਵਰਗੇ ਦੁਸ਼ਮਣਾਂ ਦੇ ਖਾਸ ਪੈਟਰਨਾਂ ਵਿੱਚ ਰੱਖੇ ਜਾਂਦੇ ਹਨ, ਤਾਂ ਉਹ ਇੱਕ Turing machine ਦੇ ਵਿਵਹਾਰ ਦੀ ਨਕਲ ਕਰ ਸਕਦੇ ਹਨ। ਨਤੀਜੇ ਵਜੋਂ, ਇਹ ਨਿਰਧਾਰਤ ਕਰਨਾ ਕਿ ਮਾਰੀਓ ਲੈਵਲ ਦੇ ਅੰਤ ਤੱਕ ਪਹੁੰਚਦਾ ਹੈ ਜਾਂ ਨਹੀਂ, ਇੱਕ ਗੁੰਝਲਦਾਰ ਪ੍ਰੋਗਰਾਮ ਕਦੇ ਰੁਕੇਗਾ ਜਾਂ ਨਹੀਂ, ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਦੇ ਬਰਾਬਰ ਹੋ ਜਾਂਦਾ ਹੈ।

AI ਅਤੇ ਕੰਪਿਊਟਿੰਗ ਦੇ ਭਵਿੱਖ ਲਈ ਇਹ ਕਿਉਂ ਮਹੱਤਵਪੂਰਨ ਹੈ

ਇਹ ਖੋਜ ਸਿਰਫ਼ ਗੇਮਰਾਂ ਲਈ ਇੱਕ ਮਜ਼ੇਦਾਰ ਤੱਥ ਨਹੀਂ ਹੈ; ਇਹ ਕੰਪਿਊਟੇਸ਼ਨ ਦੀਆਂ ਮੂਲ ਸੀਮਾਵਾਂ ਦੀ ਇੱਕ ਡੂੰਘੀ ਯਾਦ ਦਿਵਾਉਂਦੀ ਹੈ। ਜਿਵੇਂ-ਜਿਵੇਂ ਅਸੀਂ Artificial Intelligence ਅਤੇ ਆਟੋਮੇਟਡ ਰੀਜ਼ਨਿੰਗ ਦੀਆਂ ਸੀਮਾਵਾਂ ਨੂੰ ਵਧਾ ਰਹੇ ਹਾਂ, ਸਾਨੂੰ ਇਹ ਮਾਨਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਕੁਝ ਤਰਕਿਕ ਢਾਂਚੇ ਮੂਲ ਰੂਪ ਵਿੱਚ ਕਿਸੇ ਵੀ ਐਲਗੋਰਿਦਮ ਦੀ ਪਹੁੰਚ ਤੋਂ ਬਾਹਰ ਹਨ, ਚਾਹੇ ਕਿੰਨੀ ਵੀ ਪ੍ਰੋਸੈਸਿੰਗ ਪਾਵਰ ਜਾਂ ਮੈਮੋਰੀ ਉਪਲਬਧ ਹੋਵੇ।

ਇਹ ਸਾਬਤ ਕਰਕੇ ਕਿ ਇੱਕ ਦਿਖਣ ਵਿੱਚ ਸਧਾਰਨ ਵਾਤਾਵਰਣ undecidable ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਰੱਖ ਸਕਦਾ ਹੈ, MIT Hardness Group ਇਹ ਦਰਸਾਉਂਦਾ ਹੈ ਕਿ ਗੁੰਝਲਦਾਰਤਾ ਸਿਧਾਂਤ (complexity theory) ਨੂੰ ਇੰਟਰਐਕਟਿਵ, ਨਿਯਮ-ਅਧਾਰਤ ਪ੍ਰਣਾਲੀਆਂ 'ਤੇ ਕਿਵੇਂ ਲਾਗੂ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ। ਇਸਦੇ ਪ੍ਰਭਾਵ ਸਾਡੇ ਦੁਆਰਾ ਗੁੰਝਲਦਾਰ ਸਾਫਟਵੇਅਰ ਨੂੰ ਡਿਜ਼ਾਈਨ ਕਰਨ, ਆਟੋਮੇਟਡ ਪ੍ਰਣਾਲੀਆਂ ਦੀ ਜਾਂਚ ਕਰਨ, ਅਤੇ ਵਧਦੇ ਐਲਗੋਰਿਦਮਿਕ ਸੰਸਾਰ ਵਿੱਚ ਕੀ "ਗਣਨਾ" (calculate) ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਉਸਦੀਆਂ ਸੀਮਾਵਾਂ ਨੂੰ ਸਮਝਣ ਦੇ ਤਰੀਕੇ 'ਤੇ ਪੈਂਦੇ ਹਨ।

ਮੁੱਖ ਨੁਕਤੇ

• Undecidability: ਕੁਝ Super Mario ਲੈਵਲ ਹੁਣ RE-Complete ਵਜੋਂ ਸ਼੍ਰੇਣੀਬੱਧ ਹਨ, ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਕੋਈ ਵੀ ਐਲਗੋਰਿਦਮ ਕਦੇ ਵੀ ਇਹ ਸਹੀ ਅਨੁਮਾਨ ਨਹੀਂ ਲਗਾ ਸਕਦਾ ਕਿ ਕੋਈ ਖਿਡਾਰੀ ਉਹਨਾਂ ਨੂੰ ਖਤਮ ਕਰ ਸਕਦਾ ਹੈ ਜਾਂ ਨਹੀਂ।
• Complexity Shift: ਖੇਡ "ਹੱਲਯੋਗ ਪਰ ਮੁਸ਼ਕਲ" PSPACE ਕਲਾਸ ਤੋਂ undecidable ਦੇ ਖੇਤਰ ਵਿੱਚ ਚਲੀ ਗਈ ਹੈ, ਜੋ Halting Problem ਦੀ ਨਕਲ ਕਰਦੀ ਹੈ।
• Computational Gadgets: ਖੋਜਕਰਤਾਵਾਂ ਨੇ ਗੁੰਝਲਦਾਰ ਲੌਜਿਕ ਗੇਟ ਬਣਾਉਣ ਲਈ ਗੇਮ ਮਕੈਨਿਕਸ (ਪਾਈਪਾਂ, ਦੁਸ਼ਮਣ, ਅਤੇ ਪਲੇਟਫਾਰਮਾਂ) ਨੂੰ "gadgets" ਵਜੋਂ ਵਰਤਿਆ ਜੋ ਯੂਨੀਵਰਸਲ ਕੰਪਿਊਟੇਸ਼ਨ ਦਾ ਸਿਮੂਲੇਸ਼ਨ ਕਰਦੇ ਹਨ।