종이 접기 컴퓨터를 만드는 방법 | 콴타 매거진

1936년 영국의 수학자 앨런 튜링(Alan Turing)은 범용 컴퓨터에 대한 아이디어를 내놓았습니다. 그것은 간단한 장치였습니다. XNUMX과 XNUMX로 덮인 무한한 테이프 스트립과 테이프를 따라 앞뒤로 이동할 수 있는 기계와 함께 일부 규칙에 따라 XNUMX을 XNUMX로 또는 그 반대로 변경할 수 있는 기계였습니다. 그는 그러한 장치가 모든 계산을 수행하는 데 사용될 수 있음을 보여주었습니다.

튜링은 자신의 아이디어가 문제 해결에 실용적이기를 바라지 않았습니다. 오히려 그것은 계산의 본질과 그 한계를 탐구하는 귀중한 방법을 제공했습니다. 그 획기적인 아이디어 이후 수십 년 동안 수학자들은 훨씬 덜 실용적인 컴퓨팅 계획 목록을 작성했습니다. 원칙적으로 Minesweeper나 Magic: The Gathering과 같은 게임은 범용 컴퓨터로 사용될 수 있습니다. 존 콘웨이(John Conway)와 같은 소위 세포 자동 장치도 마찬가지입니다. 삶의 게임, 2차원 격자에서 검은색과 흰색 사각형을 진화시키기 위한 일련의 규칙입니다.

9월 2023에서, 이나 자카레비치 코넬대학교와 토마스 헐 프랭클린 앤 마샬 칼리지(Franklin & Marshall College)는 계산할 수 있는 모든 것을 보여주었습니다. 종이를 접어서 계산할 수 있다. 그들은 종이접기가 "튜링 완전성"이라는 것을 증명했습니다. 즉, 튜링 기계처럼 충분한 시간이 주어지면 다루기 힘든 계산 문제를 해결할 수 있다는 의미입니다.

평생 종이접기를 좋아했던 자카레비치(Zakharevich)는 생명 게임의 튜링 완전성을 설명하는 비디오를 우연히 발견한 후 2021년에 이 문제에 대해 생각하기 시작했습니다. Zakharevich는 "저는 종이접기가 인생 게임보다 훨씬 더 복잡하다고 생각했습니다."라고 말했습니다. “인생 게임이 튜링 완성이라면 종이접기도 튜링 완성이어야 합니다.”

그러나 이것은 그녀의 전문 분야가 아니었습니다. 그녀는 어렸을 때부터 종이접기를 접해왔지만 "24인치 종이 한 장과 400개의 계단이 필요한 매우 복잡한 것을 나에게 주고 싶다면 나는 그 모든 일을 다 할 수 있습니다"라고 그녀는 말했습니다. 수학적 연구는 대수 위상수학과 범주 이론의 훨씬 더 추상적인 영역을 다루었습니다. 그래서 그녀는 종이접기 수학을 풀타임으로 공부하고 있는 Hull에게 이메일을 보냈습니다.

"그녀가 갑자기 나에게 이메일을 보냈고 나는 '대수 위상학자가 왜 나에게 이것에 대해 묻는가?'라고 생각했습니다." 헐이 말했다. 그러나 그는 종이접기가 튜링 완성이 될 수 있는지 실제로 생각해 본 적이 없다는 것을 깨달았습니다. "아마 그럴 것 같지만 실제로는 모르겠습니다."

그래서 그와 Zakharevich는 종이접기로 컴퓨터를 만들 수 있다는 것을 증명하기 시작했습니다. 먼저 컴퓨터 입력 및 출력은 물론 AND 및 OR와 같은 기본 논리 연산을 종이 접기로 인코딩해야 했습니다. 그런 다음 그들의 계획이 이미 튜링 완전하다고 알려진 다른 계산 모델을 시뮬레이션할 수 있다는 것을 보여줄 수 있다면 목표를 달성할 수 있을 것입니다.

논리 연산은 하나 이상의 입력(각 입력은 TRUE 또는 FALSE로 기록됨)을 취하고 주어진 규칙에 따라 출력(TRUE 또는 FALSE)을 내보냅니다. 종이로 작업을 수행하기 위해 수학자들은 종이를 접을 위치를 지정하는 주름 패턴이라는 선 다이어그램을 디자인했습니다. 종이의 주름은 입력을 나타냅니다. 주름 패턴의 한 선을 따라 접으면 주름이 한쪽으로 뒤집어 입력 값이 TRUE임을 나타냅니다. 그러나 다른(가까운) 선을 따라 종이를 접으면 주름이 반대쪽으로 뒤집어서 FALSE를 나타냅니다.

이러한 입력 주름 중 두 개는 가젯이라고 불리는 복잡한 주름으로 이어집니다. 가젯은 논리 연산을 인코딩합니다. 이러한 모든 접기를 만들고 여전히 종이를 평평하게 접기 위해(Hull과 Zakharevich가 부과한 요구 사항) 그들은 특정 방식으로 접혀야 하는 세 번째 주름을 포함했습니다. 주름이 한 방향으로 뒤집히면 출력이 TRUE임을 의미합니다. 반대 방향으로 뒤집으면 출력은 FALSE입니다.

수학자들은 다양한 논리 연산에 따라 입력을 출력으로 바꾸는 다양한 장치를 설계했습니다. Hull은 "종이를 가지고 놀고 서로에게 사진을 보내고... 그런 다음 이러한 일이 우리가 말한 대로 작동한다는 엄격한 증거를 작성하는 일이 많았습니다."라고 말했습니다.

1990년대 후반부터 더 간단한 것으로 알려졌습니다. 1차원 아날로그 Conway의 Game of Life는 Turing이 완성되었습니다. Hull과 Zakharevich는 논리 연산 측면에서 이 버전의 Life를 작성하는 방법을 알아냈습니다. Zakharevich는 두 개의 추가 단순 게이트를 언급하면서 “결국 AND, OR, NAND 및 NOR의 4개 게이트만 사용하면 되었습니다.”라고 말했습니다. 그러나 이러한 서로 다른 게이트를 결합하려면 외부 신호를 흡수하고 다른 신호가 서로 간섭하지 않고 회전하고 교차할 수 있도록 하는 새로운 장치를 만들어야 했습니다. Zakharevich는 "모든 것을 올바르게 정렬하는 방법을 찾는 것이 가장 어려운 부분이었습니다."라고 말했습니다. 그녀와 Hull은 장비를 서로 맞춰 놓은 후 필요한 모든 것을 종이 접기로 인코딩하여 종이접기가 Turing 완성되었음을 보여줄 수 있었습니다.

종이접기 컴퓨터는 엄청나게 비효율적이고 비실용적입니다. 그러나 원칙적으로 매우 큰 종이 조각과 많은 시간을 할애할 수 있는 경우 종이접기를 사용하여 $latex pi$의 임의의 많은 자릿수를 계산하거나 전 세계 모든 배달 드라이버를 라우팅하는 최적의 방법을 결정할 수 있습니다. 날씨를 예측하는 프로그램을 실행해 보세요. Hull은 "결국 주름 패턴이 엄청나게 커졌습니다."라고 말했습니다. "접기는 어렵지만 작업은 완료됩니다."

수십 년 동안 수학자들은 종이접기가 재미있고 쓸모없어 보였기 때문에 종이접기에 끌렸다고 말했습니다. 에릭 데 메인, 매사추세츠 공과대학의 컴퓨터 과학자로 종이접기 수학에 광범위하게 기여했습니다. 그러나 최근에는 엔지니어들의 시선도 사로잡았습니다.

종이접기의 수학은 접어서 우주로 운반할 수 있는 거대한 태양 전지판, 물 속을 헤엄쳐 환경 데이터를 수집하는 로봇, 작은 혈관을 통해 이동하는 스텐트 등을 설계하는 데 사용되었습니다. Demaine은 "이제 우리가 새로운 기계 구조 설계에 개발한 모든 종이접기 수학 및 알고리즘을 사용하는 사람은 수천 명은 아니더라도 수백 명에 달합니다"라고 말했습니다.

그래서 Hull은 "이런 일을 더 많이 할수록 종이접기와 잘 확립된 수학 분야 사이에 깊은 교차점을 구축할 가능성이 더 높아질 것"이라고 말했습니다.