Return to Answer

Added explanation

Source Link

edited Aug 29, 2016 at 22:37

Unobfuscated Code

init2 * * r init2
init2 _ . l init0
init0 * * l init0
init0 _ * l init1
init1 * 0 r readop
readop _ * r readop
readop + _ l +
readop - _ l -
readop x _ l x
readop / _ l /
+ _ * l +
+ * * * inc
inc - * l dec
inc _ 1 r return
inc 0 1 l zero
inc 1 0 l inc
- _ * l -
- * * * dec
dec - * l inc
dec _ * r neg
dec 0 1 l dec
dec 1 0 l zero
x * * l x
x 1 0 l x1
x 0 0 l x0
x1 _ 1 r return
x1 1 1 l x1
x1 0 1 l x0
x0 _ _ r return
x0 1 0 l x1
x0 0 0 l x0
/ _ * l /
/ * * l //
// * * l //
// _ * r div
div 0 0 r div0
div 1 0 r div1
div0 * * l zero 
div0 0 0 r div0
div0 1 0 r div1
div1 _ * l zero
div1 - * l inc
div1 0 1 r div0
div1 1 1 r div1
neg * * r neg
neg - _ r readop
neg _ - r readop
zero * * l zero
zero _ * r zero1
zero1 0 _ r zero1
zero1 1 * r return
zero1 * _ l zero2
zero2 * 0 r return
return * * r return
return _ * r readop
readop . _ l fin
fin _ * l fin
fin - _ l min
fin * * l halt
min * * l min
min _ - r halt

Explanation of the states:

Initialization:
These states are visited once at the beginning of each run, starting with init2

init2: Move all the way to the right and put a '.'. That way the TM knows when to stop. Change to 'init0'.

init0: Move all the back to the left until the head reads a space. Then move one cell to the left. Change to 'init1'.

init1: Put a zero and move one cell to the right and change to 'readop'.

Reading instructions:
These states will be visited multiple times throughout the program

readop: Moves all the way to the right until it reads an operator or the '.'. If it hits an operator, change to the corresponding state (+,-,x,/). If it hits a '.', change to state 'fin'.

return: Returns the head to the empty space between the running total and the operators. Then changes to 'readop'.

Operations:
These operations do the actual dirty work

+: Move to the left until the head reads any non- whitespace character. If this character is a '-', move left and change to 'dec'. Otherwise, change to 'inc'.

-: Similar to '+', except change to 'inc' if there is a '-' and 'dec' otherwise.

inc: If the digit under the head is a 0 (or a whitespace), change it to 1 and change to 'zero'. If the digit is a 1, change it to 0, then repeat on the next digit.

dec: Similar to inc, except 1 goes to 0, 0 goes to 1, and if the head reads a whitespace, change to 'neg'.

x, x0, x1: Bitshift the number one to the left. Change to 'return'.

/, //, div, div0, div1: Move all the way to the right of the number, then bitshift one to the right. If there is a '-', change to 'inc'. This simulates rounding down negative numbers. Otherwise, change to 'zero'

neg: Place a '-' after the number then change to 'readop'

zero, zero1, zero2: Remove leading zeros and change to 'readop'

Cleanup: Makes the output presentable

fin, min: Move the '-' in front of the number if necessary. Halt.

Unobfuscated Code

init2 * * r init2
init2 _ . l init0
init0 * * l init0
init0 _ * l init1
init1 * 0 r readop
readop _ * r readop
readop + _ l +
readop - _ l -
readop x _ l x
readop / _ l /
+ _ * l +
+ * * * inc
inc - * l dec
inc _ 1 r return
inc 0 1 l zero
inc 1 0 l inc
- _ * l -
- * * * dec
dec - * l inc
dec _ * r neg
dec 0 1 l dec
dec 1 0 l zero
x * * l x
x 1 0 l x1
x 0 0 l x0
x1 _ 1 r return
x1 1 1 l x1
x1 0 1 l x0
x0 _ _ r return
x0 1 0 l x1
x0 0 0 l x0
/ _ * l /
/ * * l //
// * * l //
// _ * r div
div 0 0 r div0
div 1 0 r div1
div0 * * l zero 
div0 0 0 r div0
div0 1 0 r div1
div1 _ * l zero
div1 - * l inc
div1 0 1 r div0
div1 1 1 r div1
neg * * r neg
neg - _ r readop
neg _ - r readop
zero * * l zero
zero _ * r zero1
zero1 0 _ r zero1
zero1 1 * r return
zero1 * _ l zero2
zero2 * 0 r return
return * * r return
return _ * r readop
readop . _ l fin
fin _ * l fin
fin - _ l min
fin * * l halt
min * * l min
min _ - r halt

Explanation of the states:

Initialization:
These states are visited once at the beginning of each run, starting with init2

init2: Move all the way to the right and put a '.'. That way the TM knows when to stop. Change to 'init0'.

init0: Move all the back to the left until the head reads a space. Then move one cell to the left. Change to 'init1'.

init1: Put a zero and move one cell to the right and change to 'readop'.

Reading instructions:
These states will be visited multiple times throughout the program

readop: Moves all the way to the right until it reads an operator or the '.'. If it hits an operator, change to the corresponding state (+,-,x,/). If it hits a '.', change to state 'fin'.

return: Returns the head to the empty space between the running total and the operators. Then changes to 'readop'.

Operations:
These operations do the actual dirty work

+: Move to the left until the head reads any non- whitespace character. If this character is a '-', move left and change to 'dec'. Otherwise, change to 'inc'.

-: Similar to '+', except change to 'inc' if there is a '-' and 'dec' otherwise.

inc: If the digit under the head is a 0 (or a whitespace), change it to 1 and change to 'zero'. If the digit is a 1, change it to 0, then repeat on the next digit.

dec: Similar to inc, except 1 goes to 0, 0 goes to 1, and if the head reads a whitespace, change to 'neg'.

x, x0, x1: Bitshift the number one to the left. Change to 'return'.

/, //, div, div0, div1: Move all the way to the right of the number, then bitshift one to the right. If there is a '-', change to 'inc'. This simulates rounding down negative numbers. Otherwise, change to 'zero'

neg: Place a '-' after the number then change to 'readop'

zero, zero1, zero2: Remove leading zeros and change to 'readop'

Cleanup: Makes the output presentable

fin, min: Move the '-' in front of the number if necessary. Halt.

Source Link

created Aug 29, 2016 at 15:05

KoreanwGlasses

Turing Machine - 23 states (684 bytes)

Try it here - permalink

0 * * r 0
0 _ . l 1
1 * * l 1
1 _ * l 2
2 * 0 r 3
3 _ * r 3
3 + _ l +
3 - _ l -
3 x _ l x
3 / _ l /
+ _ * l +
+ * * * 4
4 - * l 5
4 _ 1 r 6
4 0 1 l 7
4 1 0 l 4
- _ * l -
- * * * 5
5 - * l 4
5 _ * r 8
5 0 1 l 5
5 1 0 l 7
x * * l x
x 1 0 l 9
x 0 0 l a
9 _ 1 r 6
9 1 1 l 9
9 0 1 l a
a _ _ r 6
a 1 0 l 9
a 0 0 l a
/ _ * l /
/ * * l b
b * * l b
b _ * r c
c 0 0 r d
c 1 0 r e
d * * l 7 
d 0 0 r d
d 1 0 r e
e _ * l 7
e - * l 4
e 0 1 r d
e 1 1 r e
8 * * r 8
8 - _ r 3
8 _ - r 3
7 * * l 7
7 _ * r f
f 0 _ r f
f 1 * r 6
f * _ l g
g * 0 r 6
6 * * r 6
6 _ * r 3
3 . _ l h
h _ * l h
h - _ l i
h * * l halt
i * * l i
i _ - r halt

Input should not contain any '*' since it is a special character in Turing machine code. Use 'x' instead. Outputs the answer in binary.