Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.08490 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916296995635200 |
|---|---|
| author | Assis, Michael |
| author_facet | Assis, Michael |
| contents | It has been known since 1996 that deciding whether a collection of creases on a piece of paper can be fully folded flat without causing self-intersection or adding new creases is an NP-Hard problem (Bern and Hayes). In their proof, a binary state was implemented as a pleat, with the state corresponding to the pleat layering order; states then interact via pleat intersections. Building on some of the machinery of their result, we will present a method for constructing an origami NAND logic gate, leading to a theoretical origami Universal Turing Machine. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08490 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An origami Universal Turing Machine design Assis, Michael Computational Complexity It has been known since 1996 that deciding whether a collection of creases on a piece of paper can be fully folded flat without causing self-intersection or adding new creases is an NP-Hard problem (Bern and Hayes). In their proof, a binary state was implemented as a pleat, with the state corresponding to the pleat layering order; states then interact via pleat intersections. Building on some of the machinery of their result, we will present a method for constructing an origami NAND logic gate, leading to a theoretical origami Universal Turing Machine. |
| title | An origami Universal Turing Machine design |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2406.08490 |