FRACTRAN

틀:위키데이터 속성 추적 FRACTRAN은 수학자 존 호턴 콘웨이가 고안한 난해한 프로그래밍 언어이다. FRACTRAN 프로그램은 양의 분수들로 이루어진 하나의 목록의 형태이다. 이 프로그램은 다음의 규칙으로 자연수 입력값 n을 갱신하며 작동한다.

1. 목록의 분수들 중에서 nf가 자연수인 가장 첫번째 분수가 f일 때, 입력값 n을 nf로 바꿔쓴다.
2. 더 이상 nf가 자연수인 분수 f가 없을때까지 위 과정을 반복한 후, 프로그램을 정지한다.

간단한 FRACTRAN 프로그래밍 예제

FRACTRAN 프로그램은 괴델 넘버링을 사용해 입력값과 출력값을 하나의 소인수분해로 표현한다. 예를 들어 a=2, b=1, c=1 을 입력하면

$2^2\times 3^1\times 5^1$

와 같은 형태로 표현한다

덧셈 프로그램

a와 b를 입력하면 a+b를 출력하는 프로그램은 다음과 같다

$\left(\frac{3}{2}\right)$

이 프로그램은 다음 알고리즘을 따른다.

	상태	행동
$\frac{3}{2}$	2의 지수>0	2의 지수에서 1을빼고 3의 지수에 1을 더한다
	2의 지수 = 0	정지

a와 b를 입력하면 다음과 같은 소인수분해 $2^a{3}^b$가 입력된다, 이 프로그램은 다음과 같은 수열 $2^{a-1}{3}^{b+1}$, $2^{a-2}{3}^{b+2}$...을 생성하다가, 결국에 $3^{a+b}$ 곧, $a+b$를 출력한다.

뺄셈 프로그램

a와 b를 입력하면 a-b를 출력하는 프로그램은 다음과 같다.

$\left(\frac{1}{6}\right)$

최댓값 구하기 프로그램

a와 b를 입력하면 a와 b중 더 큰 값을 출력하는 프로그램은 다음과 같다

$(\frac{5}{6},\frac{5}{2},\frac{5}{3})$

소수 생성 프로그램

다음은 존 콘웨이가 제시한 소수 생성 프로그램이다.

$(\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})$

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

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

을 생성하다가, 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$ 틀:OEIS

곱셈 프로그램

두 자연수 a,b를 입력했을 때, ab를 출력하는 프로그램은 다음과 같다.

$(\frac{455}{33},\frac{11}{13},\frac{1}{11},\frac{3}{7},\frac{11}{2},\frac{1}{3})$

FRACTRAN프로그램으로 3곱하기2을 계산하는 과정,a=3,b=2를 괴델 수 $2^3{3}^2$로 변환 후 입력하여, 괴델 수 $5^6$,곧 6을 출력한다.

피보나치 프로그램

피보나치 수열을 생성하는 프로그램은 다음과 같다.

$(\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})$

같이 보기

• 콜라츠 추측

각주

• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용
• 틀:서적 인용

외부 링크

• "Prime Number Pathology: Fractran"
• 틀:매스월드
• Prime Number Pathology
• FRACTRAN - (Esolang wiki)
• Ruby implementation and example programs
• Project Euler Problem 308
• "Building Fizzbuzz in Fractran from the Bottom Up"
• Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"