FRACTRAN

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. FRACTRAN 프로그램의 이해
- 2.1. 작동 원리
- 2.2. 제약 조건
3. FRACTRAN 프로그래밍 예제
4. 콘웨이의 소수 생성 알고리즘
5. 다른 FRACTRAN 프로그램 예제
- 5.1. 피보나치 수열 생성 프로그램
- 5.2. 해밍 거리 계산 프로그램
참조

1. 개요

FRACTRAN은 정수의 소인수 지수를 레지스터 값으로 사용하는 계산 모델이다. 양의 분수 목록으로 구성된 FRACTRAN 프로그램은 각 분수를 입력 정수에 곱하여 정수를 생성하는 과정을 반복하며, 분수의 분모는 조건을, 분자는 연산을 나타낸다. FRACTRAN은 덧셈, 뺄셈, 곱셈과 같은 기본적인 연산을 포함하여 피보나치 수열 생성, 소수 생성 등 다양한 계산을 수행할 수 있으며, 특히 존 콘웨이가 제시한 소수 생성 프로그램이 유명하다.

더 읽어볼만한 페이지

난해한 프로그래밍 언어 - HQ9+
HQ9+는 간단한 인터프리터 구현이 가능한 난해한 프로그래밍 언어로, 'Hello, world!' 출력, 소스 코드 출력, "99 Bottles of Beer" 가사 출력, 누산기 값 증가의 네 가지 명령을 제공한다.
난해한 프로그래밍 언어 - JSFuck
JSFuck은 제한된 문자만을 사용하여 JavaScript 코드를 표현하는 난해한 프로그래밍 스타일로, 웹 보안 공격에 악용될 수 있으며, 기본값 조합과 `Function` 생성자를 활용하여 코드를 실행하고 난독화하여 악성 코드 탐지를 어렵게 만든다.
계산 모형 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 모형 - 양자 회로
양자 회로는 양자 컴퓨팅에서 양자 논리 게이트들을 연결한 회로로, 큐비트의 양자역학적 특성을 활용하여 계산을 수행하며 양자 계산의 핵심 요소로서 연구가 활발히 진행되고 있다.

2. FRACTRAN 프로그램의 이해

FRACTRAN 프로그램은 괴델 넘버링을 사용해 입력값과 출력값을 하나의 소인수분해로 표현한다. 예를 들어 a=2, b=1, c=1 을 입력하면 $2^2 \times 3^1 \times 5^1$ 와 같은 형태로 표현한다. FRACTRAN 프로그램은 인자 $n$ 의 소수 지수에 레지스터가 저장되는 일종의 레지스터 머신이며, 괴델 수를 사용하여 양의 정수 ''n''은 임의의 수와 크기의 양의 정수 변수를 부호화할 수 있다.

2. 1. 작동 원리

FRACTRAN 프로그램은 입력된 정수의 소인수 지수를 레지스터 값으로 사용하는 일종의 레지스터 머신으로 볼 수 있다.^[1] 괴델 넘버링을 사용하면 양의 정수 ''n''은 여러 개의 양의 정수 변수를 인코딩할 수 있다. 각 변수의 값은 정수의 소인수 분해에서 소수의 지수로 표현된다. 예를 들어,

:60 = 2² × 3¹ × 5¹

위의 수는

v_2

변수가 2,

v_3

과

v_5

변수가 1의 값을 가지며, 다른 모든 변수는 0의 값을 갖는 레지스터 상태를 나타낸다.

FRACTRAN 프로그램은 양의 분수들의 정렬된 목록이다. 각 분수는 분모의 소인수로 표현되는 하나 이상의 변수에 대한 테스트를 나타낸다. 예를 들어:

:

f_1

= 21/20 = (3 × 7) / (2² × 5¹)

위의 식은

v_2

와

v_5

를 테스트한다. 만약

v_2

≥ 2이고

v_5

≥ 1이면,

v_2

에서 2를 빼고,

v_5

에서 1을 빼고,

v_3

에 1을 더하고,

v_7

에 1을 더한다. 예를 들어:

:60 ⋅

f_1

= 2² × 3¹ × 5¹ ⋅ (3 × 7) / (2² × 5¹) = 3² × 7¹

FRACTRAN 프로그램은 분수 목록이므로, 이러한 테스트-감소-증가 명령은 FRACTRAN 언어에서 허용되는 유일한 명령이다. 또한 다음 제한 사항이 적용된다.

각 명령이 실행될 때마다 테스트되는 변수도 감소한다.
동일한 변수는 단일 명령에서 감소와 증가를 동시에 할 수 없다(그렇지 않으면 해당 명령을 나타내는 분수가 기약 분수가 아닐 것이다). 따라서 각 FRACTRAN 명령은 변수를 테스트하면서 소비한다.
FRACTRAN 명령은 변수가 0인지 직접 테스트하는 것은 불가능하다(그러나 특정 변수를 테스트하는 다른 명령 다음에 배치되는 기본 명령을 생성하여 간접 테스트를 구현할 수 있다.).^[7]

2. 2. 제약 조건

FRACTRAN 프로그램은 양의 분수 목록으로 구성되므로, 테스트-감소-증가 명령만이 유일하게 허용되는 명령이다. 또한 다음과 같은 제약 조건이 따른다.^[1]

각 명령이 실행될 때마다 테스트되는 변수도 감소한다.
동일한 변수는 단일 명령에서 감소되면서 동시에 증가될 수 없다. 이는 해당 명령을 나타내는 분수가 기약 분수가 아니기 때문이다. 따라서 각 FRACTRAN 명령은 변수를 테스트함과 동시에 소비한다.
FRACTRAN 명령은 변수가 0인지 직접적으로 테스트하는 것은 불가능하다. 그러나 특정 변수를 테스트하는 다른 명령 뒤에 기본 명령을 배치하여 간접적으로 테스트를 구현할 수 있다.

3. FRACTRAN 프로그래밍 예제

FRACTRAN은 기본적인 사칙연산을 수행할 수 있도록 프로그래밍될 수 있다. 예를 들어 덧셈, 뺄셈, 곱셈 등이 가능하다.
최댓값 구하기 프로그램a와 b를 입력하면 a와 b 중 더 큰 값을 출력하는 프로그램은 다음과 같다.

: $(\frac{5}{6}, \frac{5}{2}, \frac{5}{3})$
소수 생성 프로그램다음은 존 콘웨이가 제시한 소수 생성 프로그램이다.

: $\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)$

n=2를 입력하면, 이 프로그램은 다음과 같은 수열을 생성한다.

:2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...

이 수열은 2의 소수 거듭제곱을 포함한다.

: $2^2=4,\, 2^3=8,\, 2^5=32,\, 2^7=128,\, 2^{11}=2048,\, 2^{13}=8192,\, 2^{17}=131072,\, 2^{19}=524288,\, \dots$
피보나치 수열 프로그램피보나치 수열을 생성하는 프로그램은 다음과 같다.

: $\left( \frac{33}{91}, \frac{13}{11}, \frac{11}{1}, \frac{34}{399}, \frac{19}{17}, \frac{17}{1}, \frac{7}{2}, \frac{5}{187}, \frac{3}{1} \right)$

3. 1. 덧셈 프로그램

3의 지수에 1을 더한다2의 지수 = 0정지

FRACTRAN 명령	상태	상태 지표	조건	동작	다음 상태
$\frac{3}{7}$	A	없음	$v_7$ > 0	$v_7$ 에서 1을 빼고 $v_3$ 에 1을 더한다	A
$\frac{11}{2}$			$v_7$ = 0 이고 $v_2$ > 0	$v_2$ 에서 1을 뺀다	B
$\frac{1}{3}$			$v_7$ = 0 이고 $v_2$ = 0 이고 $v_3$ > 0	$v_3$ 에서 1을 뺀다	A
			$v_7$ = 0 이고 $v_2$ = 0 이고 $v_3$ = 0	정지
$\frac{5 \cdot 7 \cdot 13}{3 \cdot 11}, \frac{11}{13}$	B	$v_{11}$ , $v_{13}$	$v_3$ > 0	$v_3$ 에서 1을 빼고 $v_5$ 에 1을 더하고 $v_7$ 에 1을 더한다	B
$\frac{1}{11}$	B	$v_{11}$ , $v_{13}$	$v_3$ = 0	없음	A

FRACTRAN 명령어	현재 상태	상태 지표	조건	동작	다음 상태
frac\|7 · 13/2 · 3 · 11^영어, frac\|11/13^영어	A	$v_{11}$ , $v_{13}$	$v_2 > 0$ 이고 $v_3 > 0$	$v_2$ 에서 1 빼기 $v_3$ 에서 1 빼기 $v_7$ 에 1 더하기	A
frac\|1/3 · 11^영어			$v_2$ = 0 이고 $v_3$ > 0	$v_3$ 에서 1 빼기	X
frac\|5 · 17/11^영어			$v_3$ = 0	$v_5$ 에 1 더하기	B
frac\|3 · 19/7 · 17^영어, frac\|17/19^영어	B	$v_{17}$ , $v_{19}$	$v_7$ > 0	$v_7$ 에서 1 빼기 $v_3$ 에 1 더하기	B
frac\|11/17^영어	B	$v_{17}$ , $v_{19}$	$v_7$ = 0	없음	A
frac\|1/3^영어	X	rowspan="2" \|	$v_3$ > 0	$v_3$ 에서 1 빼기	X
	X	$v_3$ = 0	중지

FRACTRAN 명령어	현재 상태	상태 지표	조건	동작	다음 상태
$\frac{3 \cdot 11}{2^2 \cdot 5}, \frac{5}{11}$	A	$v_5$ , $v_{11}$	$v_2$ > 1	$v_2$ 에서 2 빼기 $v_3$ 에 1 더하기	A
$\frac{13}{2 \cdot 5}$			$v_2$ = 1	$v_2$ 에서 1 빼기 $v_{13}$ 에 1 더하기	B
$\frac{1}{5}$			$v_2$ = 0	없음	B
$\frac{2}{3}$	B	없음	$v_3$ > 0	$v_3$ 에서 1 빼기 $v_2$ 에 1 더하기	B
$\frac{2 \cdot 5}{7}$			$v_3$ = 0 그리고 $v_7$ > 0	$v_7$ 에서 1 빼기 $v_2$ 에 1 더하기	A
$\frac{7}{2}$			$v_3$ = 0 그리고 $v_7$ = 0 그리고 $v_2$ > 0	$v_2$ 에서 1 빼기 $v_7$ 에 1 더하기	B
			$v_2$ = 0 그리고 $v_3$ = 0 그리고 $v_7$ = 0	중지

FRACTRAN

1. 개요

더 읽어볼만한 페이지

2. FRACTRAN 프로그램의 이해

2. 1. 작동 원리

2. 2. 제약 조건

3. FRACTRAN 프로그래밍 예제

3. 1. 덧셈 프로그램

3. 2. 뺄셈 프로그램

3. 3. 곱셈 프로그램

3. 4. 나눗셈 프로그램

3. 5. 최댓값 구하기 프로그램

4. 콘웨이의 소수 생성 알고리즘

4. 1. 알고리즘 개요

4. 2. 작동 방식

4. 3. 소수 생성 프로그램의 변형

5. 다른 FRACTRAN 프로그램 예제

5. 1. 피보나치 수열 생성 프로그램

5. 2. 해밍 거리 계산 프로그램

참조