Post by Alex Vinokur[snip]
/**************************************************************************/
/*
* This is an entry for the Obfuscated C contest. It computes
* Fibonacci numbers with a Turing machine simulation. If an
* operand is given, that string is used as the Turing machine
* program.
*
*/
/**************************************************************************/
[snip]
Is there any transitions table for computing Fibonacci numbers on a Turing Machine?
Latest version of C++ Simulator of a Turing Machine (Version 1-0-3)
performs several Turing programs.
One of them is "Computing a Fibonacci number".
http://sourceforge.net/projects/turing-machine
http://alexvn.freeservers.com/s1/turing.html
Here is description of a Turing Machine which computes Fibonacci numbers.
%%============================================
%%============== Turing Machine ==============
%%======= Computing a Fibonacci number =======
%%======== Machine Definition : BEGIN ========
%%============================================
====== Description ======
Computing Fibonacci numbers.
The program computes a Fibonacci number.
A number 'n' is represented by n 1-s.
Sample :
5 is represented as 1 1 1 1 1
3 is represented as 1 1 1
Input : number 'n'
Sample (n = 7) :
1 1 1 1 1 1 1
Output : Fibonacci#n
Sample (Fibonacci#7) :
1 1 1 1 1 1 1 1 1 1 1 1 1
Created by Alex Vinokur <mailto:***@connect.to>
====== States ======
Initial state : q0
Halting state : qf
Internal states : q101 q102 q103 q104 q105 q106 q107 q108 q109 q201 q202 q203 q204 q301 q302 q303 q304 q305 q306 q307 q308 q309 q310
q311 q401 q402 q403 q404 q501 q502 q503 q601 q602 q603 q604 q701 q702 q703 q704 q801 q802 q803 q804 q805 q806 q807 q808 q809
====== Alphabet ======
Empty symbols alphabet : b
Input alphabet : 1
Internal alphabet : x *
====== Transition Table ======
Rule# 0 : q0 [ 1 ] ---> q101 [ (x, R) ]
Rule# 1 : q101 [ 1 ] ---> q101 [ (1, R) ]
Rule# 2 : q101 [ b ] ---> q102 [ (1, R) ]
Rule# 3 : q102 [ b ] ---> q103 [ (*, R) ]
Rule# 4 : q103 [ b ] ---> q104 [ (1, R) ]
Rule# 5 : q104 [ b ] ---> q601 [ (*, L) ]
Rule# 6 : q105 [ b ] ---> q106 [ (1, L) ]
Rule# 7 : q106 [ * ] ---> q701 [ (*, L) ]
Rule# 8 : q107 [ * ] ---> q108 [ (*, L) ]
Rule# 9 : q107 [ 1 ] ---> q107 [ (1, L) ]
Rule# 10 : q108 [ * ] ---> q109 [ (*, N) ]
Rule# 11 : q108 [ 1 ] ---> q108 [ (1, L) ]
Rule# 12 : q109 [ * ] ---> q109 [ (*, R) ]
Rule# 13 : q109 [ 1 ] ---> q109 [ (1, R) ]
Rule# 14 : q109 [ b ] ---> q201 [ (*, N) ]
Rule# 15 : q201 [ * ] ---> q202 [ (*, L) ]
Rule# 16 : q201 [ 1 ] ---> q201 [ (1, L) ]
Rule# 17 : q202 [ * ] ---> q203 [ (*, R) ]
Rule# 18 : q202 [ 1 ] ---> q202 [ (1, L) ]
Rule# 19 : q202 [ b ] ---> q203 [ (b, R) ]
Rule# 20 : q203 [ * ] ---> q301 [ (*, N) ]
Rule# 21 : q203 [ 1 ] ---> q204 [ (b, R) ]
Rule# 22 : q204 [ * ] ---> q204 [ (*, R) ]
Rule# 23 : q204 [ 1 ] ---> q204 [ (1, R) ]
Rule# 24 : q204 [ b ] ---> q201 [ (1, L) ]
Rule# 25 : q301 [ * ] ---> q302 [ (*, L) ]
Rule# 26 : q302 [ * ] ---> q303 [ (*, L) ]
Rule# 27 : q302 [ b ] ---> q302 [ (b, L) ]
Rule# 28 : q303 [ * ] ---> q304 [ (*, R) ]
Rule# 29 : q303 [ 1 ] ---> q303 [ (1, L) ]
Rule# 30 : q303 [ b ] ---> q304 [ (b, R) ]
Rule# 31 : q304 [ * ] ---> q308 [ (b, N) ]
Rule# 32 : q304 [ 1 ] ---> q305 [ (b, R) ]
Rule# 33 : q305 [ * ] ---> q306 [ (*, R) ]
Rule# 34 : q305 [ 1 ] ---> q305 [ (1, R) ]
Rule# 35 : q306 [ * ] ---> q307 [ (*, L) ]
Rule# 36 : q306 [ 1 ] ---> q307 [ (1, L) ]
Rule# 37 : q306 [ b ] ---> q306 [ (b, R) ]
Rule# 38 : q307 [ b ] ---> q302 [ (1, L) ]
Rule# 39 : q308 [ 1 ] ---> q309 [ (1, L) ]
Rule# 40 : q308 [ b ] ---> q308 [ (b, R) ]
Rule# 41 : q309 [ b ] ---> q310 [ (*, L) ]
Rule# 42 : q310 [ * ] ---> q311 [ (*, R) ]
Rule# 43 : q310 [ b ] ---> q310 [ (1, L) ]
Rule# 44 : q311 [ * ] ---> q501 [ (*, R) ]
Rule# 45 : q311 [ 1 ] ---> q311 [ (1, R) ]
Rule# 46 : q401 [ * ] ---> q402 [ (*, L) ]
Rule# 47 : q401 [ 1 ] ---> q401 [ (1, L) ]
Rule# 48 : q402 [ * ] ---> q403 [ (*, L) ]
Rule# 49 : q402 [ 1 ] ---> q402 [ (1, L) ]
Rule# 50 : q403 [ * ] ---> q403 [ (*, L) ]
Rule# 51 : q403 [ 1 ] ---> q404 [ (*, L) ]
Rule# 52 : q404 [ * ] ---> q404 [ (*, R) ]
Rule# 53 : q404 [ 1 ] ---> q404 [ (1, R) ]
Rule# 54 : q404 [ b ] ---> q201 [ (*, N) ]
Rule# 55 : q404 [ x ] ---> q801 [ (x, N) ]
Rule# 56 : q501 [ * ] ---> q502 [ (1, N) ]
Rule# 57 : q501 [ 1 ] ---> q501 [ (1, R) ]
Rule# 58 : q502 [ 1 ] ---> q502 [ (1, R) ]
Rule# 59 : q502 [ b ] ---> q503 [ (b, L) ]
Rule# 60 : q503 [ 1 ] ---> q401 [ (b, L) ]
Rule# 61 : q601 [ * ] ---> q602 [ (*, L) ]
Rule# 62 : q601 [ 1 ] ---> q601 [ (1, L) ]
Rule# 63 : q602 [ 1 ] ---> q603 [ (*, L) ]
Rule# 64 : q603 [ 1 ] ---> q604 [ (1, R) ]
Rule# 65 : q603 [ x ] ---> q801 [ (x, N) ]
Rule# 66 : q604 [ * ] ---> q604 [ (*, R) ]
Rule# 67 : q604 [ 1 ] ---> q604 [ (1, R) ]
Rule# 68 : q604 [ b ] ---> q105 [ (b, N) ]
Rule# 69 : q701 [ * ] ---> q702 [ (*, L) ]
Rule# 70 : q701 [ 1 ] ---> q701 [ (1, L) ]
Rule# 71 : q702 [ * ] ---> q702 [ (*, L) ]
Rule# 72 : q702 [ 1 ] ---> q703 [ (*, L) ]
Rule# 73 : q703 [ 1 ] ---> q704 [ (1, R) ]
Rule# 74 : q703 [ x ] ---> q801 [ (x, N) ]
Rule# 75 : q704 [ * ] ---> q704 [ (*, R) ]
Rule# 76 : q704 [ 1 ] ---> q704 [ (1, R) ]
Rule# 77 : q704 [ b ] ---> q107 [ (b, L) ]
Rule# 78 : q801 [ * ] ---> q801 [ (*, R) ]
Rule# 79 : q801 [ 1 ] ---> q801 [ (1, R) ]
Rule# 80 : q801 [ b ] ---> q802 [ (b, L) ]
Rule# 81 : q801 [ x ] ---> q801 [ (x, R) ]
Rule# 82 : q802 [ * ] ---> q808 [ (b, L) ]
Rule# 83 : q802 [ 1 ] ---> q808 [ (1, L) ]
Rule# 84 : q803 [ * ] ---> q803 [ (*, L) ]
Rule# 85 : q803 [ 1 ] ---> q803 [ (*, L) ]
Rule# 86 : q803 [ x ] ---> q804 [ (x, R) ]
Rule# 87 : q804 [ * ] ---> q804 [ (*, R) ]
Rule# 88 : q804 [ 1 ] ---> q805 [ (*, L) ]
Rule# 89 : q804 [ b ] ---> q809 [ (b, N) ]
Rule# 90 : q805 [ * ] ---> q805 [ (*, L) ]
Rule# 91 : q805 [ 1 ] ---> q806 [ (1, R) ]
Rule# 92 : q805 [ x ] ---> q806 [ (*, N) ]
Rule# 93 : q806 [ * ] ---> q807 [ (1, R) ]
Rule# 94 : q807 [ * ] ---> q804 [ (*, R) ]
Rule# 95 : q808 [ * ] ---> q803 [ (*, L) ]
Rule# 96 : q808 [ 1 ] ---> q808 [ (1, L) ]
Rule# 97 : q809 [ * ] ---> q809 [ (b, L) ]
Rule# 98 : q809 [ 1 ] ---> qf [ (1, N) ]
Rule# 99 : q809 [ b ] ---> q809 [ (b, L) ]
%%============================================
%%======== Machine Definition : BEGIN ========
%%======= Computing a Fibonacci number =======
%%============== 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 Fibonacci numbers.
Raw Logs :
* http://groups.google.com/groups?th=1e653c4ef60faa44
=====================================
Alex Vinokur
mailto:***@connect.to
http://mathforum.org/library/view/10978.html
=====================================