Το Super Mario κρύβει ένα από τα μεγαλύτερα άλυτα προβλήματα των μαθηματικών

Μπορεί ένα επίπεδο στο Super Mario να είναι τόσο δύσκολο ώστε να μην υπάρχει καν τρόπος να αποδειχθεί αν μπορεί να ολοκληρωθεί; Η απάντηση, σύμφωνα με ερευνητές του MIT, είναι ναι — τουλάχιστον αν μιλάμε για ορισμένες θεωρητικά κατασκευασμένες πίστες.

Σε ερευνητική εργασία με τίτλο «You Can’t Solve These Super Mario Bros. Levels: Undecidable Mario Games», πέντε ερευνητές έδειξαν ότι παιχνίδια της σειράς Super Mario μπορούν να αναπαραστήσουν ένα από τα θεμελιώδη άλυτα προβλήματα της επιστήμης των υπολογιστών.

Το κλειδί βρίσκεται στο περίφημο «πρόβλημα του τερματισμού» — ή halting problem — που διατύπωσε ο Άλαν Τούρινγκ τη δεκαετία του 1930. Ο Βρετανός μαθηματικός απέδειξε ότι δεν μπορεί να υπάρξει ένας γενικός αλγόριθμος ο οποίος, για οποιοδήποτε πρόγραμμα υπολογιστή, να αποφασίζει πάντοτε αν αυτό θα σταματήσει κάποια στιγμή ή θα συνεχίσει να εκτελείται για πάντα.

Με άλλα λόγια, υπάρχουν ερωτήματα για τα οποία δεν είναι απλώς δύσκολο να βρούμε την απάντηση. Είναι μαθηματικά αποδεδειγμένο ότι δεν μπορεί να υπάρχει μία καθολική διαδικασία που να την υπολογίζει πάντα.

Τι σχέση έχει ο Μάριο με τον Άλαν Τούρινγκ;

Οι ερευνητές μετέτρεψαν το ερώτημα «μπορεί ο Μάριο να φτάσει στο τέλος αυτής της πίστας;» σε μια εκδοχή του προβλήματος του τερματισμού. Για να το κάνουν, χρησιμοποίησαν ένα απλό θεωρητικό μοντέλο υπολογιστή, τη λεγόμενη «μηχανή μετρητών». Η συγκεκριμένη μηχανή μπορεί να εκτελεί ελάχιστες εντολές: να αυξάνει έναν αριθμό κατά ένα, να τον μειώνει, να ελέγχει αν έχει φτάσει στο μηδέν και να σταματά.

Ακόμη όμως και ένα τόσο απλό σύστημα είναι αρκετό για να δημιουργήσει προβλήματα που δεν μπορούν να αποφασιστούν αλγοριθμικά σε όλες τις περιπτώσεις.

Στις πίστες του Mario, οι επιστήμονες χρησιμοποίησαν τους εχθρούς σαν αριθμητές. Μια διαδρομή του Μάριο μπορεί, για παράδειγμα, να δημιουργεί έναν νέο εχθρό, λειτουργώντας σαν η εντολή «+1». Μια διαφορετική διαδρομή μπορεί να εξαφανίζει έναν εχθρό, αντιστοιχώντας στο «-1».

Άλλοι μηχανισμοί μπορούν να επιτρέπουν στον Μάριο να συνεχίσει μόνο όταν δεν έχει απομείνει κανένας εχθρός. Έτσι, ολόκληρη η πίστα μπορεί να λειτουργήσει σαν υπολογιστής.

Αν ανοίξει τελικά ο δρόμος προς τον τερματισμό, τότε η αντίστοιχη «μηχανή» έχει σταματήσει. Αν όχι, μπορεί να συνεχίζει επ' άπειρον. Το πρόβλημα είναι ότι, σύμφωνα με το θεώρημα του Τούρινγκ, δεν υπάρχει γενική μέθοδος για να γνωρίζουμε εκ των προτέρων ποιο από τα δύο θα συμβεί.

Ποια παιχνίδια αφορά

Οι ερευνητές εφάρμοσαν την απόδειξή τους σε διάφορα παιχνίδια της σειράς, μεταξύ των οποίων τίτλους του «New Super Mario Bros.» αλλά και τα «Super Mario Maker», όπου οι ίδιοι οι παίκτες μπορούν να σχεδιάσουν πίστες.

Για τις ανάγκες της μαθηματικής απόδειξης, βέβαια, οι ερευνητές εξετάζουν θεωρητικές εκδοχές των παιχνιδιών χωρίς χρονικό όριο και χωρίς περιορισμό στον αριθμό των αντικειμένων ή των εχθρών.

Αυτό σημαίνει ότι δεν πρόκειται να εμφανιστεί ξαφνικά στο Nintendo Switch μια κανονική πίστα που κανείς δεν μπορεί να τερματίσει επειδή το απαγορεύει η θεωρία υπολογισμού.

Η έρευνα δείχνει όμως κάτι πολύ πιο παράξενο: οι κανόνες ορισμένων παιχνιδιών Mario είναι αρκετά πλούσιοι ώστε να αναπαραστήσουν γενικούς υπολογισμούς και, μαζί τους, προβλήματα που βρίσκονται έξω από τα όρια κάθε αλγορίθμου.

Όπως το έθεσε ο ερευνητής του MIT Έρικ Ντεμέιν: «Δεν ξέρουμε πώς να αποδείξουμε ότι ένα παιχνίδι είναι διασκεδαστικό. Μπορούμε όμως να αποδείξουμε ότι είναι δύσκολο».

Πηγή: Scientific American