기술 요약: 튜링 완전 신경망의 PyTorch 라이브러리

문제 제기

이론적 문헌은 순환 신경망 (Siegelmann & Sontag, 1995) 과 하드 어텐션을 갖는 트랜스포머 (Pérez et al., 2021; Wei, Chen, & Ma, 2021) 를 통해 신경망이 튜링 기계 (TM) 를 시뮬레이션할 수 있음을 오랫동안 입증해 왔습니다. 그러나 가중치 행렬을 명시하는 수학적 증명과 실행 가능한 구체적 구현 사이에는 여전히 큰 격차가 존재합니다. 기존 증명들은 종종 무한 정밀도나 표준 딥러닝 프레임워크에서 구체화하기 어려운 추상적 구성에 의존합니다. 본 논문은 튜링 기계 설명을 고정되고 해석 가능한 가중치를 가진 신경망으로 직접 컴파일하여, 훈련 없이도 기호 영역과 신경 영역을 연결하는 "구체적이고 실행 가능한 참조"의 필요성을 해결합니다.

방법론

저자들은 주어진 TM 전이 함수 ($\delta$) 와 종료 상태 집합으로부터 신경망을 구축하는 PyTorch 패키지를 제시합니다. 컴파일은 구성 요소의 계층 구조를 통해 진행되며, 네트워크의 순전파가 지정된 기계의 한 단계를 정확히 구현하도록 보장합니다. 서로 다른 두 가지 아키텍처가 구현되었으며, 각각 다른 이론적 결과를 실현합니다:

1. 핵심 구성 요소

구축은 기본 ReLU 활성화 게이트로부터 복잡한 논리를 구성하는 데 의존합니다:

• 부울 논리: 논문은 ReLU 네트워크가 기본 게이트 (AND, OR, NOT, XOR) 를 구현하고 이를 분합 정규식 (DNF) 회로로 구성하는 방법을 보여줍니다.
• 전이 함수: 유한한 룩업 테이블 $\delta$는 각 상태 - 심볼 쌍에 대해 하나의 은닉 뉴런이 존재하는 2 층 DNF 회로로 구현됩니다.
• 이진 산술: 반가산기와 전가산기로 구성된 파이프라인 캐리 더더는 헤드 위치를 업데이트 (이진 인코딩된 정수의 증감) 하는 데 사용됩니다.
• 위치 기반 룩업: 고온 소프트맥스를 통해 근사화된 하드 어텐션 메커니즘은 이진 키 - 쿼리 벡터를 매칭하여 테이프 기록과 원본 입력에 대한 정확한 위치 룩업을 수행합니다.

2. 아키텍처 A: WCM21 (트랜스포머 기반)

Wei, Chen, 그리고 Ma (2021) 의 구성에 기반한 이 아키텍처는 인코더 - 디코더 트랜스포머입니다:

• 인코더: 원초적 테이프를 원핫 심볼 인코딩과 이진 위치 인덱스를 가진 고정 행렬로 저장합니다.
• 디코더: 계산 기록을 자기회귀적으로 추적합니다. 각 단계는 다음 파이프라인을 포함합니다:
  1. 전이: DNF 를 통해 TM 전이 함수를 구현하는 순방향 레이어.
  2. 산술: 파이프라인 캐리 더더 체인이 헤드 위치를 업데이트합니다.
  3. 기록 검색: 자기 어텐션 레이어가 디코더 기록에서 이진 탐색을 수행하여 현재 헤드 위치에 대한 가장 최근의 쓰기를 찾습니다.
  4. 테이프 검색: 교차 어텐션이 인코더에서 원본 테이프 심볼을 읽습니다.
  5. 심볼 조립: 우선순위 기반 순방향 레이어가 올바른 심볼 (최종 쓰기 > 원본 테이프 > 빈 공간) 을 선택합니다.
• 정밀도: 어텐션 점수에서의 분수 동점을 피하기 위해 이진 위치 인코딩을 사용하여 유한 정밀도 (float32) 로 구현이 가능합니다.

3. 아키텍처 B: SS95 (순환 기반)

Siegelmann 과 Sontag (1995) 에 기반한 이 접근법은 TM 을 스택 기계로 재형식화합니다:

• 인코딩: 스택은 칸토르 집합 내의 단일 유리수 (기저 $b=4$ 및 매개변수 $\rho=1/2$ 사용) 로 인코딩됩니다.
• 연산: 스택 연산 (push, pop, peek) 은 행렬 곱셈과 포화 선형 활성화 ($\sigma(x) = \text{clamp}(x, 0, 1)$) 를 통해 조작되는 인코딩된 값의 선형 또는 조각별 선형 함수로 실현됩니다.
• 구현: 두 가지 버전이 제공됩니다:
  • 4 층 명시적 파이프라인 버전.
  • 1 층 "실시간" 순환 버전.
• 정밀도: 1 층 변형은 반올림 오차 (기저 $b$에 의해 증폭됨) 에 민감하여 float64 가 필요하며, 4 층 변형에 비해 신뢰할 수 있는 연산 횟수가 제한됩니다.

주요 기여

1. 구성적 설명: 개별 게이트에서 DNF 공식과 이진 더더로 진행하는 ReLU 네트워크가 부울 회로를 실현하는 방식의 체계적 유도.
2. 실행 가능한 구현: TM 설명을 입력받아 기계 정의에서 직접 가중치를 지정된 모델을 출력하는 완전한 PyTorch 패키지. 훈련이 필요 없으며, 네트워크는 "구축에 의해 정확"합니다.
3. 오픈 소스 기반: 코드베이스는 교란 및 그래디언트 기반 미세 조정 하에서 구성된 솔루션의 안정성을 연구하기 위한 기준선으로 기능하며, 이론적 존재와 실제 최적화 사이의 격차를 해소합니다.

결과 및 기능

이 패키지는 균형 잡힌 괄호 검사기를 통해 튜링 기계를 성공적으로 시뮬레이션합니다.

• WCM21: 6 개 상태, 5 개 심볼, 100 단계로 구성된 기계의 경우, 모델의 임베딩 너비는 59 입니다. 모든 중간 값이 $\{0, 1\}$에 머무르기 때문에 float32 에서 수치적 정확도로 작동합니다.
• SS95: 4 층 버전은 일반적인 입력에 대해 안정적입니다. 1 층 버전은 원래 이론적 구성에 더 가깝지만, 칸토르 인코딩에서의 반올림 오차 누적으로 인해 약 8 번의 pop 연산 후 정밀도 저하가 나타납니다.

중요성 및 주장

본 논문은 새로운 응용 프로그램 제안이나 훈련된 모델 대비 우수한 성능 주장을 하는 것이 아니라, 해석 가능성과 이론적 검증을 위한 기초 도구로 자신을 위치시킵니다.

• 구축에 의한 해석 가능성: 그래디언트 하강을 통해 훈련된 네트워크와 달리 뉴런이 재배열되거나 얽힐 수 있는 것과 달리, 이러한 구성된 네트워크의 모든 가중치는 알려진 해석 가능한 목적 (예: 특정 게이트, 더더의 특정 비트) 을 가집니다.
• 이론과 실무를 연결: 이 작업은 튜링 완전성의 추상적 증명과 실행 가능한 코드 사이의 격차를 해소하여 "기호 - 신경 연결"에 대한 구체적인 참조를 제공합니다.
• 미래 활용성: 저자들은 이러한 모델이 구성된 솔루션 주변의 손실 지형을 연구하기 위한 초기화로 기능할 것을 제안하며, 특히 시뮬레이션이 견딜 수 있는 가중치 교란의 정도와 미세 조정이 일반 구성이 놓친 단축 경로를 제공하는지 여부를 조사합니다.

본 논문은 이러한 구성들이 이론적으로 타당하고 실제로 실행 가능하지만, 유한 정밀도 산술의 맥락에서 이론적 튜링 완전성과 실제 수치적 안정성 사이의 내재적 트레이드오프를 강조한다고 결론지었습니다.