എന്തുകൊണ്ടാണ് സൂപ്പർ മാരിയോ മിക്കവാറും എല്ലാ അൽഗോരിതങ്ങളെക്കാളും ഗണിതശാസ്ത്രപരമായി കൂടുതൽ സങ്കീർണ്ണമാകുന്നത്

ഒരു രാജകുമാരിയെ രക്ഷിക്കുന്ന പ്ലംബറെക്കുറിച്ചുള്ള ലളിതമായ ഒരു പ്ലാറ്റ്‌ഫോമർ ഗെയിം എന്ന് തോന്നാമെങ്കിലും, സൂപ്പർ മാരിയോ യഥാർത്ഥത്തിൽ തിയററ്റിക്കൽ കമ്പ്യൂട്ടർ സയൻസിലെ ആഴമേറിയ രഹസ്യങ്ങളിലേക്കുള്ള ഒരു കവാടമാണ്. ഗെയിമിലെ ചില കോൺഫിഗറേഷനുകൾ ഗണിതശാസ്ത്രപരമായി അൺഡിസിഡബിൾ (undecidable) ആണെന്ന് MIT-യിൽ നിന്നുള്ള പുതിയ ഗവേഷണം വെളിപ്പെടുത്തുന്നു. ഇത് അവയെ സാധാരണ കമ്പ്യൂട്ടേഷണൽ പ്രശ്നങ്ങളെക്കാൾ വളരെ ഉയർന്ന ഒരു കോംപ്ലക്സിറ്റി ക്ലാസ്സിൽ എത്തിക്കുന്നു.

PSPACE മുതൽ RE-Complete വരെ: സങ്കീർണ്ണതയിലെ ഒരു വലിയ കുതിച്ചുചാട്ടം

വർഷങ്ങളായി, MIT പ്രൊഫസർ എറിക് ഡെമെയ്ൻ ഉൾപ്പെടെയുള്ള ഗവേഷകർക്കിടയിലുണ്ടായിരുന്ന പൊതുവായ അഭിപ്രായം സൂപ്പർ മാരിയോ PSPACE കോംപ്ലക്സിറ്റി ക്ലാസ്സിൽ ഉൾപ്പെടുന്നു എന്നതായിരുന്നു. ഇൻപുട്ട് വലുതാകുമ്പോൾ പരിഹരിക്കാൻ പ്രായോഗികമല്ലാത്ത അളവിൽ മെമ്മറിയും സമയവും ആവശ്യമായ പ്രശ്നങ്ങളാണ് ഈ ക്ലാസ്സിൽ അടങ്ങിയിരിക്കുന്നത്. PSPACE പ്രശ്നങ്ങൾ പ്രയാസകരമാണെങ്കിലും, ആവശ്യത്തിന് വിഭവങ്ങൾ ലഭ്യമാണെങ്കിൽ ഒരു കമ്പ്യൂട്ടറിന് അവ അടിസ്ഥാനപരമായി "പരിഹരിക്കാൻ" സാധിക്കും.

എന്നാൽ, ഹയാഷി അനി, ഹോൾഡൻ ഹാൾ, റിക്കാർഡോ റൂയിസ്, നവീൻ വെങ്കട്ട് എന്നിവരടങ്ങുന്ന വിദ്യാർത്ഥികളുടെ ഒരു സംഘം നടത്തിയ സമീപകാല പഠനം ഈ അനുമാനത്തെ തകർത്തു. ലെവൽ എഡിറ്ററുകളും Super Mario Maker-ഉം ഉപയോഗിച്ച്, ഗവേഷകർ RE-Complete ആയ പ്രത്യേക ലെവലുകൾ നിർമ്മിച്ചു. ഇതിനർത്ഥം ഗെയിം അൺഡിസിഡബിൾ പ്രശ്നങ്ങളുടെ (undecidable problems) ലോകത്തേക്ക് പ്രവേശിച്ചു എന്നാണ്. ഈ പ്രത്യേക സാഹചര്യങ്ങളിൽ, മാരിയോയ്ക്ക് വിജയകരമായി ഫ്ലാഗ്‌പോൾ അല്ലെങ്കിൽ കോട്ടയിൽ എത്താൻ കഴിയുമോ എന്ന് എപ്പോഴും കൃത്യമായി പ്രവചിക്കാൻ കഴിയുന്ന ഒരു കമ്പ്യൂട്ടർ പ്രോഗ്രാം എഴുതുന്നത് ഗണിതശാസ്ത്രപരമായി അസാധ്യമാണ്.

ഹാൾട്ടിംഗ് പ്രോബ്ലവുമായുള്ള (Halting Problem) ബന്ധം

ഒരു വീഡിയോ ഗെയിം എന്തുകൊണ്ട് അൺഡിസിഡബിൾ ആകുന്നു എന്ന് മനസ്സിലാക്കാൻ, അലൻ ട്യൂറിംഗിലേക്കും ഹാൾട്ടിംഗ് പ്രോബ്ലത്തിലേക്കും (Halting Problem) തിരിഞ്ഞുനോക്കേണ്ടതുണ്ട്. ഏതൊരു പ്രോഗ്രാമും ഒടുവിൽ നിർത്തുമോ അതോ എന്നെന്നേക്കുമായി പ്രവർത്തിച്ചുകൊണ്ടിരിക്കുമോ എന്ന് നിർണ്ണയിക്കാൻ കഴിയുന്ന ഒരു സാർവത്രിക അൽഗോരിതം ഇല്ലെന്ന് ട്യൂറിംഗ് തെളിയിച്ചു.

MIT ഗവേഷണ സംഘം റിഡക്ഷൻ (reduction) എന്ന സാങ്കേതികവിദ്യയിലൂടെ ഈ ലോജിക് മഷ്‌റൂം കിംഗ്ഡത്തിന് (Mushroom Kingdom) പ്രയോഗിച്ചു. സൂപ്പർ മാരിയോ ലെവലുകളെ "ഗഡ്‌ജെറ്റുകൾ" (gadgets) എന്ന് വിളിക്കപ്പെടുന്ന പ്രാദേശിക ഘടകങ്ങളായി വിഭജിച്ചുകൊണ്ട്, ഗെയിമിന്റെ മെക്കാനിക്സിനുള്ളിൽ സങ്കീർണ്ണമായ കമ്പ്യൂട്ടേഷണൽ ലോജിക് അനുകരിക്കാൻ ഗവേഷകർക്ക് കഴിഞ്ഞു. ഈ ഗഡ്‌ജെറ്റുകൾ ലോജിക് ഗേറ്റുകളായി പ്രവർത്തിക്കുന്നു; പൈപ്പുകൾ, പ്ലാറ്റ്‌ഫോമുകൾ, കൂടാതെ Goombas അല്ലെങ്കിൽ Spinies പോലുള്ള ശത്രുക്കൾ എന്നിവയുടെ പ്രത്യേക പാറ്റേണുകളിൽ ക്രമീകരിച്ചാൽ, അവയ്ക്ക് ഒരു ട്യൂറിംഗ് മെഷീന്റെ (Turing machine) പെരുമാറ്റം അനുകരിക്കാൻ കഴിയും. തൽഫലമായി, മാരിയോ ലെവലിന്റെ അവസാനം എത്തുമോ എന്ന് നിർണ്ണയിക്കുന്നത് ഒരു സങ്കീർണ്ണമായ പ്രോഗ്രാം എപ്പോഴെങ്കിലും നിർത്തുമോ എന്ന് നിർണ്ണയിക്കുന്നതിന് സമാനമായി മാറുന്നു.

എന്തുകൊണ്ടാണ് ഇത് AI-യുടെയും കമ്പ്യൂട്ടിംഗിന്റെയും ഭാവിക്ക് പ്രസക്തമാകുന്നത്

ഈ കണ്ടെത്തൽ ഗെയിമർമാർക്ക് വെറുമൊരു രസകരമായ വസ്തുത മാത്രമല്ല; കമ്പ്യൂട്ടേഷന്റെ അടിസ്ഥാനപരമായ പരിമിതികളെക്കുറിച്ചുള്ള ഗൗരവമായ ഓർമ്മപ്പെടുത്തൽ കൂടിയാണിത്. ആർട്ടിഫിഷ്യൽ ഇന്റലിജൻസിന്റെയും (AI) ഓട്ടോമേറ്റഡ് റീസണിംഗിന്റെയും അതിരുകൾ നമ്മൾ വികസിപ്പിക്കുമ്പോൾ, എത്ര വലിയ പ്രോസസ്സിംഗ് പവറോ മെമ്മറിയോ ലഭ്യമാണെങ്കിലും ചില ലോജിക്കൽ ഘടനകൾ സ്വാഭാവികമായും ഏതൊരു അൽഗോരിതത്തിന്റെയും പരിധിക്ക് പുറത്താണെന്ന് നമ്മൾ തിരിച്ചറിയണം.

ലളിതമെന്ന് തോന്നുന്ന ഒരു അന്തരീക്ഷത്തിൽ പോലും അൺഡിസിഡബിൾ പ്രശ്നങ്ങൾ ഉണ്ടാകാം എന്ന് തെളിയിക്കുന്നതിലൂടെ, ഇന്ററാക്ടീവ് ആയ, നിയമങ്ങൾ അടിസ്ഥാനമാക്കിയുള്ള സിസ്റ്റങ്ങളിൽ കോംപ്ലക്സിറ്റി തിയറി എങ്ങനെ പ്രയോഗിക്കാമെന്ന് MIT ഹാർഡ്‌നെസ് ഗ്രൂപ്പ് (Hardness Group) കാണിച്ചുതരുന്നു. സങ്കീർണ്ണമായ സോഫ്റ്റ്‌വെയറുകൾ രൂപകൽപ്പന ചെയ്യുന്നതിനും, ഓട്ടോമേറ്റഡ് സിസ്റ്റങ്ങൾ പരിശോധിക്കുന്നതിനും, വർദ്ധിച്ചുവരുന്ന അൽഗോരിതമിക് ലോകത്ത് എന്തൊക്കെ "കണക്കാക്കാം" എന്നതിന്റെ അതിരുകൾ മനസ്സിലാക്കുന്നതിനും ഇത് വലിയ സ്വാധീനം ചെലുത്തുന്നു.

പ്രധാന കാര്യങ്ങൾ

• അൺഡിസിഡബിലിറ്റി (Undecidability): ചില സൂപ്പർ മാരിയോ ലെവലുകൾ ഇപ്പോൾ RE-Complete ആയി തരംതിരിച്ചിരിക്കുന്നു, ഇതിനർത്ഥം ഒരു കളിക്കാരന് അവ പൂർത്തിയാക്കാൻ കഴിയുമോ എന്ന് ഒരു അൽഗോരിതത്തിനും കൃത്യമായി പ്രവചിക്കാൻ കഴിയില്ല എന്നാണ്.
• കോംപ്ലക്സിറ്റി മാറ്റം (Complexity Shift): ഗെയിം "പരിഹരിക്കാൻ കഴിയുന്ന എന്നാൽ പ്രയാസകരമായ" PSPACE ക്ലാസ്സിൽ നിന്ന് ഹാൾട്ടിംഗ് പ്രോബ്ലമിനെപ്പോലെ അൺഡിസിഡബിൾ മേഖലയിലേക്ക് മാറിയിരിക്കുന്നു.
• കമ്പ്യൂട്ടേഷണൽ ഗഡ്‌ജെറ്റുകൾ (Computational Gadgets): സാർവത്രിക കമ്പ്യൂട്ടേഷൻ അനുകരിക്കുന്ന സങ്കീർണ്ണമായ ലോജിക് ഗേറ്റുകൾ നിർമ്മിക്കുന്നതിനായി ഗവേഷകർ ഗെയിം മെക്കാനിക്സ് (പൈപ്പുകൾ, ശത്രുക്കൾ, പ്ലാറ്റ്‌ഫോമുകൾ) "ഗഡ്‌ജെറ്റുകളായി" ഉപയോഗിച്ചു.