■

Ｒ・ペンローズ著『皇帝の新しい心』第二章より。

自然数を連続した 1 の並びで表すとして、0 で区切られた二つの数の最大公約数をユークリッドの互除法で求める。

以下の例では 6 と 8 の最大公約数を求めている。答えは 2。

PROGRAM EUC
USE m_turing
IMPLICIT NONE
INTEGER, PARAMETER :: ninst = 22
TYPE(t_instruction) :: instruction_table(ninst)
!
instruction_table( 1) = t_instruction(B'0000', 0, B'0000', 0, +1)
instruction_table( 2) = t_instruction(B'0000', 1, B'0001', 1, -1)
instruction_table( 3) = t_instruction(B'0001', 0, B'0010', 1, +1)
instruction_table( 4) = t_instruction(B'0001', 1, B'0001', 1, -1)
instruction_table( 5) = t_instruction(B'0010', 0, B'1010', 0, +1)
instruction_table( 6) = t_instruction(B'0010', 1, B'0011', 0, +1)
instruction_table( 7) = t_instruction(B'0011', 0, B'0100', 0, +1)
instruction_table( 8) = t_instruction(B'0011', 1, B'0011', 1, +1)
instruction_table( 9) = t_instruction(B'0100', 0, B'0100', 0, +1)
instruction_table(10) = t_instruction(B'0100', 1, B'0101', 0, +1)
instruction_table(11) = t_instruction(B'0101', 0, B'0111', 0, -1)
instruction_table(12) = t_instruction(B'0101', 1, B'0110', 1, -1)
instruction_table(13) = t_instruction(B'0110', 0, B'0110', 0, -1)
instruction_table(14) = t_instruction(B'0110', 1, B'0001', 1, -1)
instruction_table(15) = t_instruction(B'0111', 0, B'0111', 0, -1)
instruction_table(16) = t_instruction(B'0111', 1, B'1000', 1, -1)
instruction_table(17) = t_instruction(B'1000', 0, B'1001', 0, -1)
instruction_table(18) = t_instruction(B'1000', 1, B'1000', 1, -1)
instruction_table(19) = t_instruction(B'1001', 0, B'0010', 0, +1)
instruction_table(20) = t_instruction(B'1001', 1, B'0001', 1, -1)
instruction_table(21) = t_instruction(B'1010', 0, B'0000', 0,  0)
instruction_table(22) = t_instruction(B'1010', 1, B'1010', 1, +1)
!
CALL punch_tape('0001111110011111111')
!
CALL dump_tape(1, 20)
CALL turing(instruction_table)
STOP
END PROGRAM EUC

アルゴリズムは途中のテープをダンプさせると分かりやすい*1。

*1:０が一個余計なのが気になるｗ