FRACTRAN

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

  1. 입력값 n과 목록의 분수 f에 대해 nf가 처음으로 자연수가 되는 수이면,n대신 nf를 입력한다.
  2. 더 이상 자연수 nf가 없을 때까지 이 과정을 반복했다면,프로그램을 정지한다.

간단한 FRACTRAN 프로그래밍 예제[편집]

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

와 같은 형태로 표현한다

덧셈 프로그램

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

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

상태 행동
2의 지수>0 2의 지수에서 1을빼고

3의 지수에 1을 더한다

2의 지수 = 0 정지

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

뺄셈 프로그램

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


최댓값 구하기 프로그램

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

소수 생성 프로그램

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

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

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (OEIS의 수열 A007542)

을 생성하다가, 2의 소수 거듭제곱을 포함한다.

(OEIS의 수열 A034785)

곱셈 프로그램

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

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

피보나치 프로그램

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


참고 문헌[편집]

  • Havil, Julian (2007). 《Nonplussed!》. Princeton University Press. ISBN 0-691-12056-0. 
  • Conway, John (2010). 〈FRACTRAN: A simple universal programming language for arithmetic〉. Jeffrey C. Lagarias. 《The Ultimate Challenge: the 3x+1 problem》. American Mathematical Society. 249–264쪽. ISBN 978-0-8218-4940-8. Zbl 1216.68068. 
  • Roberts, Siobhan (2015). 〈Criteria of virtue〉. 《Genius At Play - The Curious Mind of John Horton Conway》. Bloomsbury. 115–119쪽. ISBN 978-1-62040-593-2. 
  • Conway, John H. (1987). 《Open Problems in Communication and Computation》. Springer-Verlag New York, Inc. ISBN 978-1-4612-9162-6. 

외부 링크[편집]