R・ペンローズ著『皇帝の新しい心』第二章より。
自然数を連続した 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:0が一個余計なのが気になるw