FRACTRAN 문서 원본 보기

{{위키데이터 속성 추적}}
'''FRACTRAN'''은 수학자 [[존 호턴 콘웨이]]가 고안한 [[난해한 프로그래밍 언어]]이다. FRACTRAN 프로그램은 양의 [[분수]]들로 이루어진 하나의 목록의 형태이다. 이 프로그램은 다음의 규칙으로 [[자연수]] 입력값 n을 갱신하며 작동한다.
# 목록의 분수들 중에서 ''nf''가 자연수인 가장 첫번째 분수가 ''f''일 때, 입력값 ''n''을 ''nf''로 바꿔쓴다.
# 더 이상 ''nf''가 자연수인 분수 ''f''가 없을때까지 위 과정을 반복한 후, 프로그램을 정지한다.

== 간단한 FRACTRAN 프로그래밍 예제 ==

FRACTRAN 프로그램은 [[괴델 넘버링]]을 사용해 입력값과 출력값을 하나의 [[소인수분해]]로 표현한다. 예를 들어 a=2, b=1, c=1 을 입력하면
: <math> 2^2 \times 3^1 \times 5^1</math>

와 같은 형태로 표현한다

'''덧셈 프로그램'''

a와 b를 입력하면 a+b를 출력하는 프로그램은 다음과 같다
: <math>\left( \frac{3}{2} \right)</math>

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

: {| class="wikitable"
!
! 상태
! 행동
|-
| align="center" | <math>\frac{3}{2}</math>
| 2의 지수>0
| 2의 지수에서 1을빼고<br />
3의 지수에 1을 더한다
|-
|
| 2의 지수 = 0
| 정지
|}

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

'''뺄셈 프로그램'''

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

<math>\left( \frac{1}{6} \right)</math>


'''최댓값 구하기 프로그램'''

a와 b를 입력하면 a와 b중 더 큰 값을 출력하는 프로그램은 다음과 같다
: <math>(\frac{5}{6}, \frac{5}{2}, \frac{5}{3})</math>

'''소수 생성 프로그램'''

다음은 존 콘웨이가 제시한 소수 생성 프로그램이다.
: <math>\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)</math>

n=2를 입력하면,이 프로그램은 다음과 같은 수열
:2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... {{OEIS|id=A007542}}
을 생성하다가, 2의 소수 거듭제곱을 포함한다.
:<math>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</math> {{OEIS|id=A034785}}

'''곱셈 프로그램'''

두 자연수 a,b를 입력했을 때, ab를 출력하는 프로그램은 다음과 같다.
:<math>\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right)</math>
[[파일:FRACTRANmult0.gif|섬네일|544px|가운데|FRACTRAN프로그램으로 3곱하기2을 계산하는 과정,a=3,b=2를 괴델 수 <math>2^{3}3^{2}</math>로 변환 후 입력하여, 괴델 수 <math>5^{6}</math>,곧 6을 출력한다.]]

'''피보나치 프로그램'''

[[레오나르도 피보나치|피보나치]] 수열을 생성하는 프로그램은 다음과 같다.
:<math>\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)</math>


== 같이 보기 ==
* [[콜라츠 추측]]
== 각주 ==
{{각주}}
{{참고 자료 시작}}
* {{서적 인용|last=Havil|first=Julian|title=Nonplussed!|url=https://archive.org/details/nonplussedmathem00havi|publisher=Princeton University Press|year=2007|isbn=0-691-12056-0}}
* {{서적 인용|title=The Ultimate Challenge: the 3x+1 problem|url=https://archive.org/details/isbn_9780821849408|editor=Jeffrey C. Lagarias|last=Conway|first=John|authorlink=John Horton Conway|chapter=FRACTRAN: A simple universal programming language for arithmetic|pages=[https://archive.org/details/isbn_9780821849408/page/249 249]–264|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-4940-8|zbl=1216.68068}}
* {{서적 인용|title=Genius At Play - The Curious Mind of John Horton Conway|url=https://archive.org/details/geniusatplaycuri0000robe|last=Roberts|first=Siobhan|chapter=Criteria of virtue|pages=[https://archive.org/details/geniusatplaycuri0000robe/page/115 115]–119|publisher=Bloomsbury|year=2015|isbn=978-1-62040-593-2}}
* {{서적 인용|last=Conway|first=John H.|title=Open Problems in Communication and Computation|publisher=Springer-Verlag New York, Inc.|year=1987|isbn=978-1-4612-9162-6}}
{{참고 자료 끝}}

== 외부 링크 ==
{{위키공용분류}}
* [http://scienceblogs.com/goodmath/2006/10/27/prime-number-pathology-fractra/ "Prime Number Pathology: Fractran"]
* {{매스월드|urlname=FRACTRAN|title=FRACTRAN}}
* [http://brainwagon.org/?p=2207 ''Prime Number Pathology'']
* [http://www.esolangs.org/wiki/Fractran FRACTRAN] - (Esolang wiki)
* [https://web.archive.org/web/20130125232746/http://www.dev.gd/20130121-fun-with-john-conways-fractran.html Ruby implementation and example programs]
* [https://projecteuler.net/problem=308 Project Euler Problem 308]
* [http://malisper.me/2016/06/11/building-fizzbuzz-fractran-bottom/ "Building Fizzbuzz in Fractran from the Bottom Up"]
* [https://web.archive.org/web/20180104084828/http://clomont.com/a-universal-fractran-interpreter-in-fractran/ Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"]

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