사용자:Bestmountian/FRACTRAN

FRACTRAN 은 수학자 존 호턴 콘웨이가 발명한 튜링 완전한 난해한 프로그래밍 언어이다. FRACTRAN 프로그램은 자연수 입력값 n과 양의 유리수로 정렬 된 수열의 형태를 갖는다. 이 프로그램은 다음과 같이 n의 값을 갱신하면서 작동한다.

1. 프로그램의 유리수 f에 대해, nf가 첫 번째 정수이면, n 대신 nf를 입력한다.
2. 1.을 반복하다가 프로그램의 어떠한 유리수도 n 과 곱했을 때 자연수가 되지 않을 때 정지한다.

존 콘웨이와 리처드 가이는 Book of Numbers에서 다음과 같은 소수 생성 FRACTRAN 프로그램을 제시했다:

${\displaystyle }$

n=2일때, 이 FRACTRAN 프로그램은 다음과 같은 수열을 생성한다.

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

n=2 이후, 이 수열은 다음과 같은 2의 소수 거듭제곱들을 생성한다.

4, 8, 32${\displaystyle }$, 128, 2048, ...

예시

덧셈 프로그램 예시

변수 a와 b를 더하는 프로그램은 FRACTRAN 언어로 다음과 같이 표현할 수 있다.

${\displaystyle }$

이 프로그램은 아래와 같은 과정을 거친다.

FRACTRAN 유리수항	상태	실행
${\displaystyle }$	2의지수>0
2의지수=0	정지

 ${\displaystyle }$을 입력하면 프로그램은  ${\displaystyle }$, ${\displaystyle }$ 결국까지 한 후, ${\displaystyle }$ 단계가 없는 요인의 2 및 제품 ${\displaystyle }$ 더 이상 수확량 정수라고 기계 다음 정지와의 최종 출력 ${\displaystyle }$니다. 따라서 그것은 두 개의 정수를 추가 함께한다.

References

[[분류:난해한 프로그래밍 언어]] [[분류:계산 모형]] [[분류:유희 수학]]