ANALYSIS of ALGORITHMS Bulletin Board
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Computing Huffman codes on a Turing Machine
- To: <aofa@xxxxxxxxxx>
- Subject: Computing Huffman codes on a Turing Machine
- From: "Alex Vinokur" <alexvn@xxxxxxxxxxxxxxxx>
- Date: Thu, 1 Jul 2004 16:46:02 +0300
- Disposition-notification-to: "Alex Vinokur" <alexvn@barak-online.net>
Description of a Turing Machine (Version 1.1) which computes Huffman codes.
%%============================================
%%============== Turing Machine ==============
%%========= Computing Huffman codes ==========
%%=============== Version 1.1 ================
%%======== Machine Definition : BEGIN ========
%%============================================
====== Description ======
Computing Huffman codes on a Turing Machine (Version 1.1)
Input:
Tape#0 : Weights
Tape#1 : Empty
Tape#2 : Empty
Output:
Tape#0 : Weights and its Huffman codes
Tape#1 : Empty
Tape#2 : Empty
====== States Definition ======
Initial states : q0
Halting states : qf
Internal states : qc01 qc02 qc03 qc04 qc05 qc06 qc07
qe01 qe02 qe03 qe04 qe05 qe06 qe07 qe08 qe09 qe10
qh01
qm01 qm02 qm03 qm04 qm05 qm06 qm07 qm08 qm09 qm10
qm11 qm12 qm13 qm14 qm15 qm16 qm17 qm18 qm19
qm20 qm21 qm22 qm23 qm24 qm25 qm26
qmif qmin
qs01 qs02 qs03 qs04 qs05 qs06 qs07 qs08
qst1 qst2 qst3
====== Alphabet Definition ======
------ Tape# 0 ------
Empty symbols alphabet : b
Input alphabet : a *
Internal alphabet : x c d 1 0 #
------ Tape# 1 ------
Empty symbols alphabet : b
Input alphabet : a *
Internal alphabet : x c d 1 0 #
------ Tape# 2 ------
Empty symbols alphabet : b
Input alphabet : a *
Internal alphabet : x c d 1 0 #
====== Transition Rules Definition ======
Rule# 0 : q0 [ a b b ] ---> q0 [ (a, L) (b, L) (b, L) ]
Rule# 1 : q0 [ b b b ] ---> qm01 [ (x, R) (x, R) (x, R) ]
Rule# 2 : qc01 [ b x * ] ---> qc02 [ (0, R) (x, N) (*, N) ]
Rule# 3 : qc01 [ b x 0 ] ---> qc03 [ (0, R) (x, N) (0, R) ]
Rule# 4 : qc01 [ b x 1 ] ---> qc03 [ (1, R) (x, N) (1, R) ]
Rule# 5 : qc01 [ b x a ] ---> qc01 [ (a, R) (x, N) (a, R) ]
Rule# 6 : qc02 [ b x * ] ---> qc04 [ (b, N) (x, N) (*, R) ]
Rule# 7 : qc03 [ b x * ] ---> qc02 [ (0, R) (x, N) (*, N) ]
Rule# 8 : qc03 [ b x 0 ] ---> qc03 [ (0, R) (x, N) (0, R) ]
Rule# 9 : qc03 [ b x 1 ] ---> qc03 [ (1, R) (x, N) (1, R) ]
Rule# 10 : qc03 [ b x a ] ---> qc01 [ (0, R) (x, N) (a, N) ]
Rule# 11 : qc04 [ b x * ] ---> qc06 [ (1, R) (x, N) (*, N) ]
Rule# 12 : qc04 [ b x 0 ] ---> qc05 [ (0, R) (x, N) (0, R) ]
Rule# 13 : qc04 [ b x 1 ] ---> qc05 [ (1, R) (x, N) (1, R) ]
Rule# 14 : qc04 [ b x a ] ---> qc04 [ (a, R) (x, N) (a, R) ]
Rule# 15 : qc04 [ b x b ] ---> qs07 [ (1, R) (x, N) (b, N) ]
Rule# 16 : qc05 [ b x * ] ---> qc06 [ (1, R) (x, N) (*, N) ]
Rule# 17 : qc05 [ b x 0 ] ---> qc05 [ (0, R) (x, N) (0, R) ]
Rule# 18 : qc05 [ b x 1 ] ---> qc05 [ (1, R) (x, N) (1, R) ]
Rule# 19 : qc05 [ b x a ] ---> qc04 [ (1, R) (x, N) (a, N) ]
Rule# 20 : qc05 [ b x b ] ---> qs06 [ (1, N) (x, N) (*, N) ]
Rule# 21 : qc06 [ b x * ] ---> qc07 [ (*, R) (x, N) (*, R) ]
Rule# 22 : qc07 [ b x * ] ---> qc07 [ (*, R) (x, N) (*, R) ]
Rule# 23 : qc07 [ b x 0 ] ---> qc07 [ (0, R) (x, N) (0, R) ]
Rule# 24 : qc07 [ b x 1 ] ---> qc07 [ (1, R) (x, N) (1, R) ]
Rule# 25 : qc07 [ b x a ] ---> qc07 [ (a, R) (x, N) (a, R) ]
Rule# 26 : qc07 [ b x b ] ---> qs07 [ (b, N) (x, N) (b, N) ]
Rule# 27 : qe01 [ 0 b x ] ---> qe01 [ (0, L) (b, N) (x, N) ]
Rule# 28 : qe01 [ 1 b x ] ---> qe01 [ (1, L) (b, N) (x, N) ]
Rule# 29 : qe01 [ a b x ] ---> qe01 [ (a, L) (b, N) (x, N) ]
Rule# 30 : qe01 [ x b x ] ---> qe02 [ (x, R) (b, N) (x, R) ]
Rule# 31 : qe02 [ 0 b b ] ---> qe03 [ (0, R) (b, N) (0, R) ]
Rule# 32 : qe02 [ 1 b b ] ---> qe03 [ (1, R) (b, N) (1, R) ]
Rule# 33 : qe02 [ a b b ] ---> qe02 [ (a, R) (b, N) (a, R) ]
Rule# 34 : qe03 [ 0 b b ] ---> qe03 [ (0, R) (b, N) (0, R) ]
Rule# 35 : qe03 [ 1 b b ] ---> qe03 [ (1, R) (b, N) (1, R) ]
Rule# 36 : qe03 [ a b b ] ---> qe04 [ (a, N) (b, N) (*, R) ]
Rule# 37 : qe03 [ b b b ] ---> qe05 [ (b, L) (b, N) (b, N) ]
Rule# 38 : qe04 [ a b b ] ---> qe02 [ (a, R) (b, N) (a, R) ]
Rule# 39 : qe05 [ 0 b b ] ---> qe05 [ (b, L) (b, N) (b, N) ]
Rule# 40 : qe05 [ 1 b b ] ---> qe05 [ (b, L) (b, N) (b, N) ]
Rule# 41 : qe05 [ a b b ] ---> qe05 [ (b, L) (b, N) (b, N) ]
Rule# 42 : qe05 [ x b b ] ---> qe06 [ (x, N) (b, N) (b, L) ]
Rule# 43 : qe06 [ x b * ] ---> qe06 [ (x, N) (b, N) (*, L) ]
Rule# 44 : qe06 [ x b 0 ] ---> qe06 [ (x, N) (b, N) (0, L) ]
Rule# 45 : qe06 [ x b 1 ] ---> qe06 [ (x, N) (b, N) (1, L) ]
Rule# 46 : qe06 [ x b a ] ---> qe06 [ (x, N) (b, N) (a, L) ]
Rule# 47 : qe06 [ x b x ] ---> qe07 [ (x, R) (b, N) (x, R) ]
Rule# 48 : qe07 [ b b * ] ---> qe07 [ (*, R) (b, N) (b, R) ]
Rule# 49 : qe07 [ b b 0 ] ---> qe07 [ (0, R) (b, N) (b, R) ]
Rule# 50 : qe07 [ b b 1 ] ---> qe07 [ (1, R) (b, N) (b, R) ]
Rule# 51 : qe07 [ b b a ] ---> qe07 [ (a, R) (b, N) (b, R) ]
Rule# 52 : qe07 [ b b b ] ---> qe08 [ (b, N) (b, N) (b, L) ]
Rule# 53 : qe08 [ b b b ] ---> qe08 [ (b, N) (b, N) (b, L) ]
Rule# 54 : qe08 [ b b x ] ---> qe09 [ (b, L) (b, N) (x, N) ]
Rule# 55 : qe09 [ * b x ] ---> qe09 [ (*, L) (b, N) (x, N) ]
Rule# 56 : qe09 [ 0 b x ] ---> qe09 [ (0, L) (b, N) (x, N) ]
Rule# 57 : qe09 [ 1 b x ] ---> qe09 [ (1, L) (b, N) (x, N) ]
Rule# 58 : qe09 [ a b x ] ---> qe09 [ (a, L) (b, N) (x, N) ]
Rule# 59 : qe09 [ x b x ] ---> qe10 [ (#, R) (b, N) (x, R) ]
Rule# 60 : qe10 [ a b b ] ---> qm01 [ (a, N) (b, N) (b, N) ]
Rule# 61 : qh01 [ b x * ] ---> qh01 [ (b, N) (x, N) (b, L) ]
Rule# 62 : qh01 [ b x 0 ] ---> qh01 [ (0, R) (x, N) (b, L) ]
Rule# 63 : qh01 [ b x 1 ] ---> qh01 [ (1, R) (x, N) (b, L) ]
Rule# 64 : qh01 [ b x a ] ---> qh01 [ (a, R) (x, N) (b, L) ]
Rule# 65 : qh01 [ b x x ] ---> qf [ (b, N) (b, N) (b, N) ]
Rule# 66 : qm01 [ * b b ] ---> qm01 [ (*, R) (b, N) (b, N) ]
Rule# 67 : qm01 [ 0 b b ] ---> qm01 [ (0, R) (b, N) (b, N) ]
Rule# 68 : qm01 [ 1 b b ] ---> qm01 [ (1, R) (b, N) (b, N) ]
Rule# 69 : qm01 [ a b b ] ---> qm02 [ (a, N) (b, N) (b, N) ]
Rule# 70 : qm01 [ b b b ] ---> qs01 [ (b, N) (b, L) (b, N) ]
Rule# 71 : qm01 [ d b b ] ---> qm01 [ (d, R) (b, N) (b, N) ]
Rule# 72 : qm02 [ * b b ] ---> qm03 [ (*, N) (b, L) (b, N) ]
Rule# 73 : qm02 [ 0 b b ] ---> qm02 [ (0, R) (b, N) (b, N) ]
Rule# 74 : qm02 [ 1 b b ] ---> qm02 [ (1, R) (b, N) (b, N) ]
Rule# 75 : qm02 [ a b b ] ---> qm02 [ (c, R) (a, R) (b, N) ]
Rule# 76 : qm02 [ b b b ] ---> qm04 [ (b, L) (b, N) (b, N) ]
Rule# 77 : qm03 [ * * b ] ---> qm06 [ (*, R) (*, R) (b, N) ]
Rule# 78 : qm03 [ * a b ] ---> qm03 [ (*, N) (a, L) (b, N) ]
Rule# 79 : qm03 [ * x b ] ---> qm06 [ (*, R) (x, R) (b, N) ]
Rule# 80 : qm04 [ * b b ] ---> qm05 [ (*, R) (b, N) (b, N) ]
Rule# 81 : qm04 [ 0 b b ] ---> qm04 [ (0, L) (b, N) (b, N) ]
Rule# 82 : qm04 [ 1 b b ] ---> qm04 [ (1, L) (b, N) (b, N) ]
Rule# 83 : qm04 [ c b b ] ---> qm04 [ (d, L) (b, N) (b, N) ]
Rule# 84 : qm05 [ 0 b b ] ---> qm05 [ (0, R) (b, N) (0, R) ]
Rule# 85 : qm05 [ 1 b b ] ---> qm05 [ (1, R) (b, N) (1, R) ]
Rule# 86 : qm05 [ b b b ] ---> qs01 [ (b, N) (b, N) (b, N) ]
Rule# 87 : qm05 [ d b b ] ---> qm05 [ (d, R) (b, N) (a, R) ]
Rule# 88 : qm06 [ * a b ] ---> qm08 [ (*, N) (b, R) (b, N) ]
Rule# 89 : qm06 [ * b b ] ---> qm07 [ (*, N) (b, L) (b, N) ]
Rule# 90 : qm06 [ 0 a b ] ---> qm06 [ (0, R) (a, N) (b, N) ]
Rule# 91 : qm06 [ 0 b b ] ---> qm06 [ (0, R) (b, N) (b, N) ]
Rule# 92 : qm06 [ 1 a b ] ---> qm06 [ (1, R) (a, N) (b, N) ]
Rule# 93 : qm06 [ 1 b b ] ---> qm06 [ (1, R) (b, N) (b, N) ]
Rule# 94 : qm06 [ a a b ] ---> qm06 [ (a, R) (a, R) (b, N) ]
Rule# 95 : qm06 [ a b b ] ---> qm12 [ (a, R) (b, N) (b, N) ]
Rule# 96 : qm06 [ b a b ] ---> qm14 [ (b, N) (b, R) (b, N) ]
Rule# 97 : qm06 [ b b b ] ---> qm13 [ (b, N) (*, R) (b, N) ]
Rule# 98 : qm06 [ d a b ] ---> qm25 [ (d, R) (a, N) (b, N) ]
Rule# 99 : qm07 [ * * b ] ---> qm06 [ (*, R) (*, R) (b, N) ]
Rule# 100 : qm07 [ * a b ] ---> qm07 [ (*, N) (a, L) (b, N) ]
Rule# 101 : qm07 [ * x b ] ---> qm06 [ (*, R) (x, R) (b, N) ]
Rule# 102 : qm07 [ b b b ] ---> qmif [ (b, N) (b, N) (b, N) ]
Rule# 103 : qm08 [ * a b ] ---> qm08 [ (*, N) (b, R) (b, N) ]
Rule# 104 : qm08 [ * b b ] ---> qm09 [ (*, N) (b, L) (b, N) ]
Rule# 105 : qm09 [ * * b ] ---> qm10 [ (*, L) (*, R) (b, N) ]
Rule# 106 : qm09 [ * a b ] ---> qm09 [ (*, N) (a, L) (b, N) ]
Rule# 107 : qm09 [ * b b ] ---> qm09 [ (*, N) (b, L) (b, N) ]
Rule# 108 : qm09 [ * x b ] ---> qm10 [ (*, L) (x, R) (b, N) ]
Rule# 109 : qm10 [ * a b ] ---> qm11 [ (*, R) (a, N) (b, N) ]
Rule# 110 : qm10 [ 0 a b ] ---> qm10 [ (0, L) (a, N) (b, N) ]
Rule# 111 : qm10 [ 1 a b ] ---> qm10 [ (1, L) (a, N) (b, N) ]
Rule# 112 : qm10 [ a a b ] ---> qm10 [ (c, L) (a, N) (b, N) ]
Rule# 113 : qm10 [ x a b ] ---> qm11 [ (x, R) (a, N) (b, N) ]
Rule# 114 : qm11 [ * a b ] ---> qm06 [ (*, R) (a, R) (b, N) ]
Rule# 115 : qm11 [ 0 a b ] ---> qm11 [ (0, R) (a, N) (b, N) ]
Rule# 116 : qm11 [ 1 a b ] ---> qm11 [ (1, R) (a, N) (b, N) ]
Rule# 117 : qm11 [ c a b ] ---> qm11 [ (c, R) (a, N) (b, N) ]
Rule# 118 : qm12 [ * * b ] ---> qm06 [ (*, R) (*, R) (b, N) ]
Rule# 119 : qm12 [ * a b ] ---> qm12 [ (*, N) (a, L) (b, N) ]
Rule# 120 : qm12 [ * b b ] ---> qm12 [ (*, N) (b, L) (b, N) ]
Rule# 121 : qm12 [ * x b ] ---> qm06 [ (*, R) (x, R) (b, N) ]
Rule# 122 : qm12 [ 0 b b ] ---> qm12 [ (0, R) (b, N) (b, N) ]
Rule# 123 : qm12 [ 1 b b ] ---> qm12 [ (1, R) (b, N) (b, N) ]
Rule# 124 : qm12 [ a b b ] ---> qm12 [ (a, R) (b, N) (b, N) ]
Rule# 125 : qm12 [ b b b ] ---> qm13 [ (b, N) (*, R) (b, N) ]
Rule# 126 : qm13 [ b b b ] ---> qmif [ (b, N) (b, N) (b, N) ]
Rule# 127 : qm14 [ b a b ] ---> qm14 [ (b, N) (b, R) (b, N) ]
Rule# 128 : qm14 [ b b b ] ---> qm15 [ (b, N) (b, L) (b, N) ]
Rule# 129 : qm15 [ b a b ] ---> qm16 [ (b, N) (a, R) (b, N) ]
Rule# 130 : qm15 [ b b b ] ---> qm15 [ (b, N) (b, L) (b, N) ]
Rule# 131 : qm16 [ b b b ] ---> qm17 [ (b, N) (*, R) (b, N) ]
Rule# 132 : qm17 [ b b b ] ---> qm18 [ (b, L) (b, N) (b, N) ]
Rule# 133 : qm18 [ * b b ] ---> qm19 [ (*, R) (b, N) (b, N) ]
Rule# 134 : qm18 [ 0 b b ] ---> qm18 [ (0, L) (b, N) (b, N) ]
Rule# 135 : qm18 [ 1 b b ] ---> qm18 [ (1, L) (b, N) (b, N) ]
Rule# 136 : qm18 [ a b b ] ---> qm18 [ (c, L) (b, N) (b, N) ]
Rule# 137 : qm19 [ 0 b b ] ---> qm19 [ (0, R) (b, N) (b, N) ]
Rule# 138 : qm19 [ 1 b b ] ---> qm19 [ (1, R) (b, N) (b, N) ]
Rule# 139 : qm19 [ b b b ] ---> qmif [ (b, N) (b, N) (b, N) ]
Rule# 140 : qm19 [ c b b ] ---> qm19 [ (c, R) (b, N) (b, N) ]
Rule# 141 : qm20 [ * b b ] ---> qm20 [ (*, L) (b, N) (b, N) ]
Rule# 142 : qm20 [ 0 b b ] ---> qm20 [ (0, L) (b, N) (b, N) ]
Rule# 143 : qm20 [ 1 b b ] ---> qm20 [ (1, L) (b, N) (b, N) ]
Rule# 144 : qm20 [ a b b ] ---> qm20 [ (a, L) (b, N) (b, N) ]
Rule# 145 : qm20 [ c b b ] ---> qm21 [ (d, L) (b, N) (b, N) ]
Rule# 146 : qm20 [ d b b ] ---> qm20 [ (d, L) (b, N) (b, N) ]
Rule# 147 : qm21 [ # b b ] ---> qm22 [ (#, R) (b, N) (b, N) ]
Rule# 148 : qm21 [ * b b ] ---> qm22 [ (*, R) (b, N) (b, N) ]
Rule# 149 : qm21 [ 0 b b ] ---> qm21 [ (0, L) (b, N) (b, N) ]
Rule# 150 : qm21 [ 1 b b ] ---> qm21 [ (1, L) (b, N) (b, N) ]
Rule# 151 : qm21 [ c b b ] ---> qm21 [ (d, L) (b, N) (b, N) ]
Rule# 152 : qm21 [ x b b ] ---> qm22 [ (x, R) (b, N) (b, N) ]
Rule# 153 : qm22 [ * b b ] ---> qm23 [ (*, L) (b, N) (*, R) ]
Rule# 154 : qm22 [ 0 b b ] ---> qm22 [ (0, R) (b, N) (0, R) ]
Rule# 155 : qm22 [ 1 b b ] ---> qm22 [ (1, R) (b, N) (1, R) ]
Rule# 156 : qm22 [ b b b ] ---> qm23 [ (b, L) (b, N) (*, R) ]
Rule# 157 : qm22 [ d b b ] ---> qm22 [ (d, R) (b, N) (a, R) ]
Rule# 158 : qm23 [ # b b ] ---> qmin [ (#, N) (b, N) (b, N) ]
Rule# 159 : qm23 [ * b b ] ---> qm24 [ (*, L) (b, N) (b, N) ]
Rule# 160 : qm23 [ 0 b b ] ---> qm23 [ (0, L) (b, N) (b, N) ]
Rule# 161 : qm23 [ 1 b b ] ---> qm23 [ (1, L) (b, N) (b, N) ]
Rule# 162 : qm23 [ d b b ] ---> qm23 [ (d, L) (b, N) (b, N) ]
Rule# 163 : qm23 [ x b b ] ---> qmin [ (x, N) (b, N) (b, N) ]
Rule# 164 : qm24 [ # b b ] ---> qmin [ (#, N) (b, N) (b, N) ]
Rule# 165 : qm24 [ * b b ] ---> qm24 [ (*, L) (b, N) (b, N) ]
Rule# 166 : qm24 [ 0 b b ] ---> qm24 [ (0, L) (b, N) (b, N) ]
Rule# 167 : qm24 [ 1 b b ] ---> qm24 [ (1, L) (b, N) (b, N) ]
Rule# 168 : qm24 [ a b b ] ---> qm24 [ (a, L) (b, N) (b, N) ]
Rule# 169 : qm24 [ c b b ] ---> qm24 [ (a, L) (b, N) (b, N) ]
Rule# 170 : qm24 [ d b b ] ---> qm24 [ (d, L) (b, N) (b, N) ]
Rule# 171 : qm24 [ x b b ] ---> qmin [ (x, N) (b, N) (b, N) ]
Rule# 172 : qm25 [ * a b ] ---> qm06 [ (*, R) (a, N) (b, N) ]
Rule# 173 : qm25 [ 0 a b ] ---> qm25 [ (0, R) (a, N) (b, N) ]
Rule# 174 : qm25 [ 1 a b ] ---> qm25 [ (1, R) (a, N) (b, N) ]
Rule# 175 : qm25 [ b a b ] ---> qm26 [ (b, N) (a, N) (b, N) ]
Rule# 176 : qm25 [ d a b ] ---> qm25 [ (d, R) (a, N) (b, N) ]
Rule# 177 : qm26 [ b a b ] ---> qm26 [ (b, N) (a, R) (b, N) ]
Rule# 178 : qm26 [ b b b ] ---> qmif [ (b, N) (*, R) (b, N) ]
Rule# 179 : qmif [ b b b ] ---> qm20 [ (b, L) (b, N) (b, N) ]
Rule# 180 : qmin [ # b b ] ---> qm01 [ (#, R) (b, N) (b, N) ]
Rule# 181 : qmin [ x b b ] ---> qm01 [ (x, R) (b, N) (b, N) ]
Rule# 182 : qs01 [ b * b ] ---> qs02 [ (b, N) (*, N) (b, L) ]
Rule# 183 : qs01 [ b b b ] ---> qs02 [ (b, N) (b, N) (b, L) ]
Rule# 184 : qs02 [ b * * ] ---> qs02 [ (b, N) (*, N) (b, N) ]
Rule# 185 : qs02 [ b * 0 ] ---> qs02 [ (b, N) (*, N) (0, R) ]
Rule# 186 : qs02 [ b * 1 ] ---> qs02 [ (b, N) (*, N) (1, R) ]
Rule# 187 : qs02 [ b * a ] ---> qs02 [ (b, N) (*, N) (a, R) ]
Rule# 188 : qs02 [ b * b ] ---> qs03 [ (b, N) (b, N) (b, N) ]
Rule# 189 : qs02 [ b b * ] ---> qs02 [ (b, N) (b, N) (b, N) ]
Rule# 190 : qs02 [ b b 0 ] ---> qs02 [ (b, N) (b, N) (0, R) ]
Rule# 191 : qs02 [ b b 1 ] ---> qs02 [ (b, N) (b, N) (1, R) ]
Rule# 192 : qs02 [ b b a ] ---> qs02 [ (b, N) (b, N) (a, R) ]
Rule# 193 : qs02 [ b b b ] ---> qs03 [ (b, N) (b, N) (b, N) ]
Rule# 194 : qs03 [ # b b ] ---> qs04 [ (#, N) (b, L) (b, N) ]
Rule# 195 : qs03 [ * b b ] ---> qs03 [ (b, L) (b, N) (b, N) ]
Rule# 196 : qs03 [ 0 b b ] ---> qs03 [ (b, L) (b, N) (b, N) ]
Rule# 197 : qs03 [ 1 b b ] ---> qs03 [ (b, L) (b, N) (b, N) ]
Rule# 198 : qs03 [ b b b ] ---> qs03 [ (b, L) (b, N) (b, N) ]
Rule# 199 : qs03 [ d b b ] ---> qs03 [ (b, L) (b, N) (b, N) ]
Rule# 200 : qs03 [ x b b ] ---> qs04 [ (x, N) (b, L) (b, N) ]
Rule# 201 : qs04 [ # * b ] ---> qs04 [ (#, N) (b, L) (b, N) ]
Rule# 202 : qs04 [ # a b ] ---> qs04 [ (#, N) (b, L) (b, N) ]
Rule# 203 : qs04 [ # x b ] ---> qh01 [ (x, R) (x, N) (b, L) ]
Rule# 204 : qs04 [ x * b ] ---> qs04 [ (x, N) (b, L) (b, N) ]
Rule# 205 : qs04 [ x a b ] ---> qs04 [ (x, N) (b, L) (b, N) ]
Rule# 206 : qs04 [ x x b ] ---> qs05 [ (x, N) (x, N) (b, L) ]
Rule# 207 : qs05 [ x x * ] ---> qs05 [ (x, N) (x, N) (*, L) ]
Rule# 208 : qs05 [ x x 0 ] ---> qs05 [ (x, N) (x, N) (0, L) ]
Rule# 209 : qs05 [ x x 1 ] ---> qs05 [ (x, N) (x, N) (1, L) ]
Rule# 210 : qs05 [ x x a ] ---> qs05 [ (x, N) (x, N) (a, L) ]
Rule# 211 : qs05 [ x x x ] ---> qc01 [ (x, R) (x, N) (x, R) ]
Rule# 212 : qs06 [ 0 x * ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 213 : qs06 [ 0 x 0 ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 214 : qs06 [ 0 x 1 ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 215 : qs06 [ 0 x a ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 216 : qs06 [ 0 x x ] ---> qe01 [ (1, N) (x, R) (x, N) ]
Rule# 217 : qs06 [ 1 x * ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 218 : qs06 [ 1 x 0 ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 219 : qs06 [ 1 x 1 ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 220 : qs06 [ 1 x a ] ---> qs06 [ (1, N) (x, N) (b, L) ]
Rule# 221 : qs06 [ 1 x x ] ---> qe01 [ (1, N) (x, R) (x, N) ]
Rule# 222 : qs07 [ * x b ] ---> qs07 [ (*, L) (x, N) (b, N) ]
Rule# 223 : qs07 [ 0 x b ] ---> qs07 [ (0, L) (x, N) (b, N) ]
Rule# 224 : qs07 [ 1 x b ] ---> qs07 [ (1, L) (x, N) (b, N) ]
Rule# 225 : qs07 [ a x b ] ---> qs07 [ (a, L) (x, N) (b, N) ]
Rule# 226 : qs07 [ b x b ] ---> qs07 [ (b, L) (x, N) (b, N) ]
Rule# 227 : qs07 [ x x b ] ---> qs08 [ (x, N) (x, N) (b, L) ]
Rule# 228 : qs08 [ x x * ] ---> qs08 [ (x, N) (x, N) (b, L) ]
Rule# 229 : qs08 [ x x 0 ] ---> qs08 [ (x, N) (x, N) (b, L) ]
Rule# 230 : qs08 [ x x 1 ] ---> qs08 [ (x, N) (x, N) (b, L) ]
Rule# 231 : qs08 [ x x a ] ---> qs08 [ (x, N) (x, N) (b, L) ]
Rule# 232 : qs08 [ x x x ] ---> qst1 [ (x, N) (x, N) (x, N) ]
Rule# 233 : qst1 [ x x x ] ---> qst2 [ (x, R) (x, N) (x, N) ]
Rule# 234 : qst2 [ * x x ] ---> qst3 [ (*, L) (x, N) (x, N) ]
Rule# 235 : qst2 [ 0 x x ] ---> qst2 [ (0, R) (x, N) (x, N) ]
Rule# 236 : qst2 [ 1 x x ] ---> qst2 [ (1, R) (x, N) (x, N) ]
Rule# 237 : qst2 [ a x x ] ---> qst2 [ (a, R) (x, N) (x, N) ]
Rule# 238 : qst2 [ b x x ] ---> qs06 [ (b, L) (x, N) (x, N) ]
Rule# 239 : qst3 [ 0 x x ] ---> qst3 [ (0, L) (x, N) (x, N) ]
Rule# 240 : qst3 [ 1 x x ] ---> qst3 [ (1, L) (x, N) (x, N) ]
Rule# 241 : qst3 [ a x x ] ---> qst3 [ (a, L) (x, N) (x, N) ]
Rule# 242 : qst3 [ x x x ] ---> qm01 [ (x, R) (x, R) (x, R) ]
%%============================================
%%========= Machine Definition : END =========
%%========= Computing Huffman codes ==========
%%=============== Version 1.1 ================
%%============== Turing Machine ==============
%%============================================
C++ Simulator of a Turing Machine
* http://sourceforge.net/projects/turing-machine
* http://alexvn.freeservers.com/s1/turing.html
has been used to compute several Huffman codes.
Raw Log :
* http://groups-beta.google.com/group/misc.test/msg/af70d2465227f10d
(Computing Huffman codes for Fibonacci numbers on a Turing Machine)
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn