Πώς να φτιάξετε έναν υπολογιστή Origami | Περιοδικό Quanta

Το 1936, ο Βρετανός μαθηματικός Άλαν Τούρινγκ σκέφτηκε μια ιδέα για έναν παγκόσμιο υπολογιστή. Ήταν μια απλή συσκευή: μια άπειρη λωρίδα ταινίας καλυμμένη με μηδενικά και ένα, μαζί με μια μηχανή που μπορούσε να κινείται εμπρός και πίσω κατά μήκος της ταινίας, αλλάζοντας τα μηδενικά σε ένα και αντίστροφα σύμφωνα με κάποιο σύνολο κανόνων. Έδειξε ότι μια τέτοια συσκευή θα μπορούσε να χρησιμοποιηθεί για την εκτέλεση οποιουδήποτε υπολογισμού.

Ο Τούρινγκ δεν σκόπευε η ιδέα του να είναι πρακτική για την επίλυση προβλημάτων. Αντίθετα, πρόσφερε έναν ανεκτίμητο τρόπο για να εξερευνήσετε τη φύση του υπολογισμού και τα όριά του. Τις δεκαετίες μετά από αυτή τη θεμελιώδη ιδέα, οι μαθηματικοί έχουν συγκεντρώσει μια λίστα με ακόμη λιγότερο πρακτικά υπολογιστικά σχήματα. Παιχνίδια όπως το Minesweeper ή το Magic: The Gathering θα μπορούσαν, καταρχήν, να χρησιμοποιηθούν ως υπολογιστές γενικής χρήσης. Το ίδιο θα μπορούσαν και τα λεγόμενα κυψελωτά αυτόματα όπως του John Conway Παιχνίδι της Ζωής, ένα σύνολο κανόνων για την εξέλιξη των ασπρόμαυρων τετραγώνων σε ένα δισδιάστατο πλέγμα.

Τον Σεπτέμβριο του 2023, Ίννα Ζακαρέβιτς του Πανεπιστημίου Cornell και Τόμας Χαλ του Franklin & Marshall College έδειξε ότι οτιδήποτε μπορεί να υπολογιστεί μπορεί να υπολογιστεί διπλώνοντας χαρτί. Απέδειξαν ότι το origami είναι "ολοκληρωμένο το Turing" - που σημαίνει ότι, όπως μια μηχανή Turing, μπορεί να λύσει οποιοδήποτε υπολογιστικό πρόβλημα που μπορεί να λυθεί, με αρκετό χρόνο.

Ο Zakharevich, ένας δια βίου λάτρης του origami, άρχισε να σκέφτεται αυτό το πρόβλημα το 2021 αφού σκόνταψε σε ένα βίντεο που εξηγούσε την πληρότητα του Turing του Game of Life. «Ήμουν ότι το origami είναι πολύ πιο περίπλοκο από το Game of Life», είπε ο Zakharevich. "Αν το Game of Life είναι ολοκληρωμένο το Turing, το origami θα πρέπει να είναι και το Turing πλήρες."

Αλλά δεν ήταν αυτός ο τομέας της ειδικότητάς της. Αν και είχε διπλώσει το origami από μικρή — «αν θέλετε να μου δώσετε ένα εξαιρετικά περίπλοκο πράγμα που απαιτεί ένα φύλλο χαρτιού 24 ιντσών και έχει 400 βήματα, το έχω ξεπεράσει όλα αυτά», είπε — της η μαθηματική έρευνα ασχολήθηκε με τα πολύ πιο αφηρημένα πεδία της αλγεβρικής τοπολογίας και της θεωρίας κατηγοριών. Έτσι έστειλε email στον Hull, ο οποίος μελετούσε τα μαθηματικά του origami με πλήρες ωράριο.

«Μόλις μου έστειλε email από το μπλε και σκέφτηκα, γιατί ένας αλγεβρικός τοπολόγος με ρωτάει για αυτό;» είπε ο Χαλ. Αλλά συνειδητοποίησε ότι ποτέ δεν είχε σκεφτεί πραγματικά αν το origami θα μπορούσε να είναι πλήρες του Turing. «Ήμουν, μάλλον είναι, αλλά στην πραγματικότητα δεν ξέρω».

Έτσι, αυτός και ο Ζαχάρεβιτς ξεκίνησαν να αποδείξουν ότι μπορείτε να φτιάξετε έναν υπολογιστή από origami. Πρώτα έπρεπε να κωδικοποιήσουν τις υπολογιστικές εισόδους και εξόδους - καθώς και βασικές λογικές πράξεις όπως AND και OR - ως πτυχές χαρτιού. Εάν μπορούσαν στη συνέχεια να δείξουν ότι το σχήμα τους θα μπορούσε να προσομοιώσει κάποιο άλλο υπολογιστικό μοντέλο που είναι ήδη γνωστό ότι είναι ολοκληρωμένο ο Turing, θα πετύχαιναν τον στόχο τους.

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

Δύο από αυτές τις πιέτες εισόδου τροφοδοτούν ένα περίπλοκο γρύλισμα πτυχών που ονομάζεται gadget. Το gadget κωδικοποιεί τη λογική λειτουργία. Προκειμένου να γίνουν όλες αυτές οι πτυχές και να συνεχίσουν να διπλώνουν το χαρτί επίπεδη - μια απαίτηση που επιβάλλουν οι Χαλ και Ζαχάρεβιτς - συμπεριέλαβαν μια τρίτη πτυχή που αναγκάζεται να διπλωθεί με συγκεκριμένο τρόπο. Εάν η πιέτα γυρίσει προς μία κατεύθυνση, σημαίνει ότι η έξοδος είναι ΑΛΗΘΗΣ. Αν γυρίσει αντίστροφα, η έξοδος είναι FALSE.

Οι μαθηματικοί σχεδίασαν διαφορετικά gadget που μετατρέπουν τις εισροές σε εξόδους σύμφωνα με διάφορες λογικές πράξεις. «Ήταν πολύ να παίζουμε με χαρτί και να στέλνουμε φωτογραφίες ο ένας στον άλλο… και μετά να γράφουμε αυστηρές αποδείξεις ότι αυτά τα πράγματα λειτουργούσαν όπως είπαμε», είπε ο Χαλ.

Είναι γνωστό από τα τέλη της δεκαετίας του 1990 ότι ένα απλούστερο μονοδιάστατο αναλογικό του Conway's Game of Life ολοκληρώθηκε ο Turing. Ο Χαλ και ο Ζαχάρεβιτς κατάλαβαν πώς να γράψουν αυτή την έκδοση του Life από την άποψη των λογικών πράξεων. «Καταλήξαμε να χρειαζόμαστε μόνο τέσσερις πύλες: AND, OR, NAND και NOR», είπε ο Zakharevich, αναφερόμενος σε δύο επιπλέον απλές πύλες. Αλλά για να συνδυάσουν αυτές τις διαφορετικές πύλες, έπρεπε να κατασκευάσουν νέα gadgets που απορροφούσαν ξένα σήματα και επέτρεπαν σε άλλα σήματα να στρίβουν και να τέμνονται χωρίς να παρεμβαίνουν μεταξύ τους. «Αυτό ήταν το πιο δύσκολο κομμάτι», είπε ο Ζαχάρεβιτς, «να καταλάβω πώς να τα φτιάξω όλα σωστά». Αφού αυτή και ο Χαλ κατάφεραν να ταιριάξουν τα gadget τους μεταξύ τους, μπορούσαν να κωδικοποιήσουν όλα όσα χρειάζονταν σε πτυχώσεις χαρτιού, δείχνοντας έτσι ότι το origami είναι πλήρες.

Ένας υπολογιστής origami θα ήταν πολύ αναποτελεσματικός και μη πρακτικός. Αλλά κατ 'αρχήν, εάν είχατε ένα πολύ μεγάλο κομμάτι χαρτί και πολύ χρόνο στα χέρια σας, θα μπορούσατε να χρησιμοποιήσετε origami για να υπολογίσετε αυθαίρετα πολλά ψηφία $latex pi$, να καθορίσετε τον βέλτιστο τρόπο δρομολόγησης κάθε οδηγού παράδοσης στον κόσμο ή τρέξτε ένα πρόγραμμα για να προβλέψετε τον καιρό. «Στο τέλος, το σχέδιο τσάκισης είναι τεράστιο», είπε ο Χαλ. «Είναι δύσκολο να πάει πάσο, αλλά κάνει τη δουλειά».

Για δεκαετίες, οι μαθηματικοί έλκονταν από το origami επειδή «φαινόταν διασκεδαστικό και άχρηστο», είπε. Erik Demaine, επιστήμονας υπολογιστών στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης που έχει συμβάλει εκτενώς στα μαθηματικά του origami. Πρόσφατα όμως τράβηξε και τα βλέμματα των μηχανικών.

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

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