ಯಾಕೆ ಸೂಪರ್ ಮರಿಯೋ ಹೆಚ್ಚಿನ ಅಲ್ಗಾರಿದಮ್ಗಳಿಗಿಂತ ಗಣಿತದ ದೃಷ್ಟಿಯಿಂದ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿದೆ
ಒಬ್ಬ ಪ್ಲಂಬರ್ ರಾಜಕುಮಾರಿಯನ್ನು ರಕ್ಷಿಸುವ ಸರಳ ಪ್ಲಾಟ್ಫಾರ್ಮರ್ ಆಟದಂತೆ ಕಂಡರೂ, ಸೂಪರ್ ಮರಿಯೋ ವಾಸ್ತವವಾಗಿ ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದ ಅತ್ಯಂತ ಆಳವಾದ ರಹಸ್ಯಗಳಿಗೆ ಒಂದು ದ್ವಾರವಾಗಿದೆ. MIT ನ ಹೊಸ ಸಂಶೋಧನೆಯು ಆಟದ ಕೆಲವು ವಿನ್ಯಾಸಗಳು (configurations) ಗಣಿತದ ಪ್ರಕಾರ ನಿರ್ಧರಿಸಲಾಗದವು (undecidable) ಎಂದು ಬಹಿರಂಗಪಡಿಸಿದೆ, ಇದು ಅವುಗಳನ್ನು ಸಾಮಾನ್ಯ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳಿಗಿಂತ ಬಹಳ ಮೀರಿದ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಕ್ಕೆ (complexity class) ತಳ್ಳುತ್ತದೆ.
PSPACE ನಿಂದ RE-Complete ವರೆಗೆ: ಸಂಕೀರ್ಣತೆಯಲ್ಲಿ ಒಂದು ಬೃಹತ್ ಜಿಗಿತ
ವರ್ಷಗಳ ಕಾಲ, MIT ಪ್ರೊಫೆಸರ್ ಎರಿಕ್ ಡೆಮೇನ್ ಸೇರಿದಂತೆ ಸಂಶೋಧಕರ ಒಮ್ಮತ ಏನೆಂದರೆ, ಸೂಪರ್ ಮರಿಯೋ PSPACE ಸಂಕೀರ್ಣತೆಯ ವರ್ಗಕ್ಕೆ ಸೇರಿದೆ ಎಂಬುದು. ಈ ವರ್ಗವು ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಆದರೆ ಇನ್ಪುಟ್ ಗಾತ್ರ ಬೆಳೆದಂತೆ ಇವುಗಳಿಗೆ ಅಸಾಧ್ಯವಾದಷ್ಟು ಮೆಮೊರಿ ಮತ್ತು ಸಮಯದ ಅವಶ್ಯಕತೆ ಇರುತ್ತದೆ. PSPACE ಸಮಸ್ಯೆಗಳು ಕಷ್ಟಕರವಾಗಿದ್ದರೂ, ಸಾಕಷ್ಟು ಸಂಪನ್ಮೂಲಗಳನ್ನು ನೀಡಿದರೆ ಅವುಗಳನ್ನು ಕಂಪ್ಯೂಟರ್ ಮೂಲಭೂತವಾಗಿ "ಪರಿಹರಿಸಬಹುದು".
ಆದರೆ, ಹಯಾಶಿ ಅನಿ, ಹೋಲ್ಡನ್ ಹಾಲ್, ರಿಕಾರ್ಡೊ ರೂಯಿಸ್ ಮತ್ತು ನವೀನ್ ವೆಂಕಟ್ ಎಂಬ ವಿದ್ಯಾರ್ಥಿಗಳ ತಂಡದ ಇತ್ತೀಚಿನ ಕೆಲಸವು ಈ ಕಲ್ಪನೆಯನ್ನು ಪುರোপুরি ಬದಲಿಸಿದೆ. ಲೆವೆಲ್ ಎಡಿಟರ್ಗಳು ಮತ್ತು Super Mario Maker ಅನ್ನು ಬಳಸಿಕೊಂಡು, ಸಂಶೋಧಕರು RE-Complete ಆಗಿರುವ ನಿರ್ದಿಷ್ಟ ಹಂತಗಳನ್ನು (levels) ನಿರ್ಮಿಸಿದರು. ಇದರರ್ಥ ಆಟವು ನಿರ್ಧರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳ (undecidable problems) ವ್ಯಾಪ್ತಿಗೆ ಪ್ರವೇಶಿಸಿದೆ ಎಂದರ್ಥ. ಈ ನಿರ್ದಿಷ್ಟ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಮರಿಯೋ ಯಶಸ್ವಿಯಾಗಿ ಫ್ಲಾಗ್ಪೋಲ್ ಅಥವಾ ಅರಮನೆಯನ್ನು ತಲುಪಬಲ್ಲನೇ ಎಂದು ಯಾವಾಗಲೂ ನಿಖರವಾಗಿ ಮುನ್ಸೂಚನೆ ನೀಡಬಲ್ಲ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಬರೆಯುವುದು ಗಣಿತದ ಪ್ರಕಾರ ಅಸಾಧ್ಯ.
Halting Problem ಗೆ ಇರುವ ಸಂಬಂಧ
ಒಂದು ವೀಡಿಯೊ ಗೇಮ್ ಏಕೆ ನಿರ್ಧರಿಸಲಾಗದಂತಿದೆ ಎಂಬುದನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು, ಅಲಾನ್ ಟ್ಯೂರಿಂಗ್ ಮತ್ತು Halting Problem ಅನ್ನು ಗಮನಿಸಬೇಕು. ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಪ್ರೋಗ್ರಾಂ ಅಂತಿಮವಾಗಿ ನಿಲ್ಲುತ್ತದೆಯೇ ಅಥವಾ ಎಂದಿಗೂ ಚಲಿಸುತ್ತಲೇ ಇರುತ್ತದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಲು ಯಾವುದೇ ಸಾರ್ವತ್ರಿಕ ಅಲ್ಗಾರಿದಮ್ ಇಲ್ಲ ಎಂದು ಟ್ಯೂರಿಂಗ್ ಸಾಬೀತುಪಡಿಸಿದರು.
MIT ಸಂಶೋಧನಾ ತಂಡವು reduction ಎಂಬ ತಂತ್ರದ ಮೂಲಕ ಈ ತರ್ಕವನ್ನು ಮಶ್ರೂಮ್ ಕಿಂಗ್ಡಮ್ಗೆ ಅನ್ವಯಿಸಿತು. ಸೂಪರ್ ಮರಿಯೋ ಹಂತವನ್ನು "gadgets" ಎಂದು ಕರೆಯಲ್ಪಡುವ ಸ್ಥಳೀಯ ಘಟಕಗಳಾಗಿ ವಿಭಜಿಸುವ ಮೂಲಕ, ಸಂಶೋಧಕರು ಆಟದ ಕಾರ್ಯವಿಧಾನದೊಳಗೆ ಸಂಕೀರ್ಣ ಕಂಪ್ಯೂಟೇಶನಲ್ ತರ್ಕವನ್ನು ಅನುಕರಿಸಲು (simulate) ಸಾಧ್ಯವಾಯಿತು. ಈ ಗ್ಯಾಜೆಟ್ಗಳು ಲಾಜಿಕ್ ಗೇಟ್ಗಳಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ; ಪೈಪ್ಗಳು, ಪ್ಲಾಟ್ಫಾರ್ಮ್ಗಳು ಮತ್ತು ಗೂಂಬಾ (Goombas) ಅಥವಾ ಸ್ಪಿನೀಸ್ (Spinies) ನಂತಹ ಶತ್ರುಗಳನ್ನು ನಿರ್ದಿಷ್ಟ ಮಾದರಿಗಳಲ್ಲಿ ಜೋಡಿಸಿದಾಗ, ಅವು ಟ್ಯೂರಿಂಗ್ ಮೆಷಿನ್ನ ನಡವಳಿಕೆಯನ್ನು ಪ್ರತಿಬಿಂಬಿಸಬಲ್ಲವು. ಪರಿಣಾಮವಾಗಿ, ಮರಿಯೋ ಹಂತದ ಅಂತ್ಯವನ್ನು ತಲುಪುತ್ತಾನೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು, ಒಂದು ಸಂಕೀರ್ಣ ಪ್ರೋಗ್ರಾಂ ಎಂದಾದರೂ ನಿಲ್ಲುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದಕ್ಕೆ ಸಮಾನವಾಗುತ್ತದೆ.
AI ಮತ್ತು ಕಂಪ್ಯೂಟಿಂಗ್ನ ಭವಿಷ್ಯಕ್ಕೆ ಇದು ಏಕೆ ಮುಖ್ಯ
ಈ ಸಂಶೋಧನೆಯು ಕೇವಲ ಗೇಮರ್ಗಳಿಗೆ ಒಂದು ಕುತೂಹಲಕಾರಿ ವಿಷಯವಲ್ಲ; ಇದು ಕಂಪ್ಯೂಟೇಶನ್ನ ಮೂಲಭೂತ ಮಿತಿಗಳ ಬಗ್ಗೆ ಒಂದು ಆಳವಾದ ನೆನಪನ್ನು ನೀಡುತ್ತದೆ. ನಾವು ಕೃತಕ ಬುದ್ಧಿಮತ್ತೆ (Artificial Intelligence) ಮತ್ತು ಸ್ವಯಂಚಾಲಿತ ತರ್ಕದ (automated reasoning) ಮಿತಿಗಳನ್ನು ವಿಸ್ತರಿಸುತ್ತಿರುವಾಗ, ಎಷ್ಟೇ ಪ್ರೊಸೆಸಿಂಗ್ ಪವರ್ ಅಥವಾ ಮೆಮೊರಿ ಲಭ್ಯವಿದ್ದರೂ ಸಹ, ಕೆಲವು ತಾರ್ಕಿಕ ರಚನೆಗಳು ಸಹಜವಾಗಿಯೇ ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ನ ವ್ಯಾಪ್ತಿಗೆ ಮೀರಿದ್ದವೆಂದು ನಾವು ಗುರುತಿಸಬೇಕು.
ಮೇಲ್ನೋಟಕ್ಕೆ ಸರಳವಾಗಿ ಕಾಣುವ ಪರಿಸರವು ನಿರ್ಧರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳನ್ನು ಹೊಂದಿರಬಹುದು ಎಂದು ಸಾಬೀತುಪಡಿಸುವ ಮೂಲಕ, MIT Hardness Group ಸಂಕೀರ್ಣತಾ ಸಿದ್ಧಾಂತವನ್ನು (complexity theory) ಸಂವಾದಾತ್ಮಕ, ನಿಯಮ ಆಧಾರಿತ ವ್ಯವಸ್ಥೆಗಳಿಗೆ ಹೇಗೆ ಅನ್ವಯಿಸಬಹುದು ಎಂಬುದನ್ನು ತೋರಿಸಿಕೊಡುತ್ತದೆ. ಇದು ನಾವು ಸಂಕೀರ್ಣ ಸಾಫ್ಟ್ವೇರ್ಗಳನ್ನು ಹೇಗೆ ವಿನ್ಯಾಸಗೊಳಿಸುತ್ತೇವೆ, ಸ್ವಯಂಚಾಲಿತ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಹೇಗೆ ಪರಿಶೀಲಿಸುತ್ತೇವೆ ಮತ್ತು ಹೆಚ್ಚುತ್ತಿರುವ ಅಲ್ಗಾರಿದಮಿಕ್ ಜಗತ್ತಿನಲ್ಲಿ ಏನನ್ನು "ಲೆಕ್ಕಹಾಕಬಹುದು" ಎಂಬ ಮಿತಿಗಳನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವಲ್ಲಿ ಪ್ರಭಾವ ಬೀರುತ್ತದೆ.
ಪ್ರಮುಖ ಅಂಶಗಳು
- ನಿರ್ಧರಿಸಲಾಗದಿರುವುದು (Undecidability): ಕೆಲವು ಸೂಪರ್ ಮರಿಯೋ ಹಂತಗಳನ್ನು ಈಗ RE-Complete ಎಂದು ವರ್ಗೀಕರಿಸಲಾಗಿದೆ, ಅಂದರೆ ಒಬ್ಬ ಆಟಗಾರ ಅವುಗಳನ್ನು ಪೂರ್ಣಗೊಳಿಸಬಲ್ಲನೇ ಎಂದು ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ಎಂದಿಗೂ ನಿಖರವಾಗಿ ಮುನ್ಸೂಚಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ.
- ಸಂಕೀರ್ಣತೆಯ ಬದಲಾವಣೆ (Complexity Shift): ಈ ಆಟವು "ಪರಿಹರಿಸಬಹುದಾದ ಆದರೆ ಕಷ್ಟಕರವಾದ" PSPACE ವರ್ಗದಿಂದ ನಿರ್ಧರಿಸಲಾಗದ ವ್ಯಾಪ್ತಿಗೆ ಸ್ಥಳಾಂತರಗೊಂಡಿದೆ, ಇದು Halting Problem ಅನ್ನು ಪ್ರತಿಬಿಂಬಿಸುತ್ತದೆ.
- ಕಂಪ್ಯೂಟೇಶನಲ್ ಗ್ಯಾಜೆಟ್ಗಳು (Computational Gadgets): ಸಂಶೋಧಕರು ಸಾರ್ವತ್ರಿಕ ಕಂಪ್ಯೂಟೇಶನ್ ಅನ್ನು ಅನುಕರಿಸುವ ಸಂಕೀರ್ಣ ಲಾಜಿಕ್ ಗೇಟ್ಗಳನ್ನು ನಿರ್ಮಿಸಲು ಆಟದ ಕಾರ್ಯವಿಧಾನಗಳನ್ನು (ಪೈಪ್ಗಳು, ಶತ್ರುಗಳು ಮತ್ತು ಪ್ಲಾಟ್ಫಾರ್ಮ್ಗಳು) "ಗ್ಯಾಜೆಟ್ಗಳಾಗಿ" ಬಳಸಿದರು.