Skip to content

Instantly share code, notes, and snippets.

@TarVK
Last active September 12, 2022 20:17
Show Gist options
  • Save TarVK/ab3795714ba1940dc9f28303d395c37e to your computer and use it in GitHub Desktop.
Save TarVK/ab3795714ba1940dc9f28303d395c37e to your computer and use it in GitHub Desktop.
https://turingmachinesimulator.com/ example input 1101__1011
name: binaryAddition
init: init0
accept: done
// if cursor is started between 2 values:
// init: return2
// Example input: 11011_10101
// 13 states, 34 instructions (when removing init: 12 states, 31 instructions)
// Init that's not needed if input is left and right of the cursor
init0,_
start,0,<
init0,0
init0,0,>
init0,1
init0,1,>
// Return to the start
return,0
return2,_,<
return,1
return2,_,<
return2,0
return2,0,<
return2,1
return2,1,<
return2,_
start,0,<
// Start the bit adding
start,0
add0,_,>
start,1
add1,_,>
start,_
finish,_,>
// Add 0
add0,0
add0,0,>
add0,1
add0_1,1,>
add0_1,0
add0,0,>
add0_1,1
add0_1,1,>
add0,_
return,0,<
add0_1,_
return,1,<
// Add 1
add1,0
add1,0,>
add1,1
add1_1,1,>
add1_1,0
add1,0,>
add1_1,1
add1_1,1,>
add1,_
return,1,<
add1_1,_
carryShift,0,<
carryShift,1
carry,_,<
carry,0
return2,1,<
carry,1
carry,0,<
// Cleaning up
finish,0
finish,_,>
finish,1
finish2_1,_,>
finish2,0
finish2,0,>
finish2,_
done,0,>
finish2,1
finish2_1,0,>
finish2_1,0
finish2,1,>
finish2_1,1
finish2_1,1,>
finish2_1,_
done,1,>
@TarVK
Copy link
Author

TarVK commented May 27, 2020

Dual tape version:

name: adder
init: init0
accept: 11111

init0,0,_
init0,_,0,>,>

init0,1,_
init0,_,1,>,>

init0,+,_
init1,_,_,>,-

init1,0,_
init1,0,_,>,-

init1,1,_
init1,1,_,>,-

init1,_,_
00000,_,_,<,<

// Add 0
00000,0,0
00000,_,0,<,<

00000,0,_
00000,_,0,<,<

00000,0,1
00000,_,1,<,<

00001,0,0
00000,_,1,<,<

00001,0,_
00000,_,1,<,<

00001,0,1
00001,_,0,<,<

// Add 1
00000,1,0
00000,_,1,<,<

00000,1,_
00000,_,1,<,<

00000,1,1
00001,_,0,<,<

00001,1,0
00001,_,0,<,<

00001,1,_
00001,_,0,<,<

00001,1,1
00001,_,1,<,<

// Finish
00000,_,0
11111,_,0,<,<

00000,_,_
11111,_,_,<,<

00000,_,1
11111,_,1,<,<

00001,_,0
11111,_,1,<,<

00001,_,_
11111,_,1,<,<

00001,_,1
00001,_,0,<,<

example input: 1101+1011

@TarVK
Copy link
Author

TarVK commented May 28, 2020

Binary multiply, 35 states, prematurely doubles
Example input 1011_1100

name: binary multiplier
init: init0
accept: d

// Example input 1011_1100

init0,0
init0,0,>

init0,1
init0,1,>

init0,_
detect,_,>

// Detect whether to add
detect,0
shiftStart,_,<

detect,1
addStart,_,<

detect,_
finish,_,<

// Only shift the number
shiftStart,_
shift,_,<

shift,0
shift,0,<

shift,1
shift,1,<

shift,_
shiftMul2,_,<

shiftMul2,_
shiftRet,0,>

shiftRet,_
shiftRetCarry,_,>

shiftRetCarry,0
shiftRetCarry0,_,>

shiftRetCarry,1
shiftRetCarry1,_,>

shiftRetCarry0,0
shiftRetCarry0,0,>

shiftRetCarry0,1
shiftRetCarry1,0,>

shiftRetCarry0,_
return2,0,>

shiftRetCarry1,0
shiftRetCarry0,1,>

shiftRetCarry1,1
shiftRetCarry1,1,>

shiftRetCarry1,_
return2,1,>

// Add number
addStart,_
addDetect,_,<

addDetect,0
add0,_,>

addDetect,1
add1,_,>

addDetect,_
addMult2,_,<

// Add 0 seek
add0,_
add0shift,0,<

add0shift,_
add0seek,_,<

add0seek,0
add0seek,0,<

add0seek,1
add0seek,1,<

add0seek,_
add0seekBit,_,<

add0seekBit,0
add0seekBit,0,<

add0seekBit,1
add0seekBit,1,<

add0seekBit,_
addShiftBit,_,<

// Add 1 seek
add1,_
add1shift,1,<

add1shift,_
add1seek,_,<

add1seek,0
add1seek,0,<

add1seek,1
add1seek,1,<

add1seek,_
add1seekBit,_,<

add1seekBit,0
add1seekBit,0,<

add1seekBit,1
add1seekBit,1,<

add1seekBit,_
add1bit,_,<

// Add 1
add1bit,0
add1return,1,>

add1bit,_
add1return,1,>

add1bit,1
add1bit,0,<

add1return,1
add1return,1,>

add1return,0
add1return,0,>

add1return,_
addShiftBit,_,<

// Shift bit
addShiftBit,0
addShiftBit0,_,>

addShiftBit,_
addShiftBit0,_,>

addShiftBit0,_
addReturn,0,>

addShiftBit,1
addShiftBit1,_,>

addShiftBit1,_
addReturn,1,>

// Return from adding a digit
addReturn,0
addReturn,0,>

addReturn,1
addReturn,1,>

addReturn,_
addReturn2,_,>

addReturn2,0
addReturn2,0,>

addReturn2,1
addReturn2,1,>

addReturn2,_
addDetect,_,<

// Multiply with 2
addMult2,0
addMult2carry0,0,<

addMult2,1
addMult2carry1,0,<

addMult2carry0,0
addMult2carry0,0,<

addMult2carry0,1
addMult2carry1,0,<

addMult2carry0,_
return,0,>

addMult2carry1,0
addMult2carry0,1,<

addMult2carry1,1
addMult2carry1,1,<

addMult2carry1,_
return,1,>

return,0
return,0,>

return,1
return,1,>

return,_
return1,_,>

return1,_
return2,_,>

return2,0
return2,0,>

return2,1
return2,1,>

return2,_
detect,_,>

// Finish up
finish,_
finish2,_,<

finish2,0
finish2,_,<

finish2,1
finish2,_,<

finish2,_
finish3,_,<

finish3,_
finish3,_,<

finish3,0
d,_,<

@TarVK
Copy link
Author

TarVK commented Feb 23, 2021

I created a tower of hanoi solver, based on the approach as seen here: https://www.youtube.com/watch?v=qsW5xmd9XCY&t=49s&ab_channel=aeh5040

The tape contains values of which pole each disk is on (poles 0 to 2), disk in increasing size order (first number is smallest disk)

name: tower of hanoi
init: not2
accept: done

// Not pole 2 transitions
not2, 0
not2reset, 1, <

not2, 1
not2reset, 0, <

not2, 2
not2, 2, >

not2reset, 0
not2reset, 0, <

not2reset, 1
not2reset, 1, <

not2reset, 2
not2reset, 2, <

not2reset, _
not1, _, >

// Not pole 1 transitions
not1, 0
not1reset, 2, <

not1, 2
not1reset, 0, <

not1, 1
not1, 1, >

not1reset, 0
not1reset, 0, <

not1reset, 1
not1reset, 1, <

not1reset, 2
not1reset, 2, <

not1reset, _
not0, _, >

// Not pole 0 transitions
not0, 1
not0reset, 2, <

not0, 2
not0reset, 1, <

not0, 0
not0, 0, >

not0reset, 0
not0reset, 0, <

not0reset, 1
not0reset, 1, <

not0reset, 2
not0reset, 2, <

not0reset, _
not2, _, >

And the same program with a binary encoding, where every pole is represented using 2 binary digits:

name: tower of hanoi
init: not2
accept: done

// Not pole 2 transitions
not2, 1
not2v2, 1, >

not2v2, 0
not2, 0, >

not2, 0
not2v0, 0, >

not2v0, 0
not2reset, 1, <

not2v0, 1
not2reset, 0, <

not2reset, 0
not2reset, 0, <

not2reset, 1
not2reset, 1, <

not2reset, _
not1, _, >

// Not pole 1 transitions
not1, 1
not1reset, 0, <

not1, 0
not1v0, 0, >

not1v0, 1
not1, 1, >

not1v0, 0
not1v1, 0, <

not1v1, 0
not1reset, 1, <

not1reset, 0
not1reset, 0, <

not1reset, 1
not1reset, 1, <

not1reset, _
not0, _, >

// Not pole 0 transitions
not0, 1
not0v2, 0, >

not0v2, 0
not0reset, 1, <

not0, 0
not0v0, 0, >

not0v0, 0
not0, 0, >

not0v0, 1
not0v1, 0, <

not0v1, 0
not0reset, 1, <

not0reset, 0
not0reset, 0, <

not0reset, 1
not0reset, 1, <

not0reset, _
not2, _, >

@TarVK
Copy link
Author

TarVK commented Sep 12, 2022

Binary multiplication using a 4 symbol alphabet:

name: binaryMultiply
init: returnStart
accept: done

// Example input: 11011_10101

// Uses 19 states and 59 transitions

// Returning to the 2nd value
returnStart,0
return0,_,>

returnStart,1
return1,_,>

return0,0
return0,0,>

return0,1
return1,0,>

return1,0
return0,1,>

return1,1
return1,1,>

return0,_
start,0,>

return1,_
start,1,>

// Check whether to add then shift, or only shift
start,_
finish,_,<

start,0
shift,_,<

start,1
add,_,<

// Check what bit to add
add,0
add0,_,<

add,1
add1,*,<

add,_
outputCleanup,_,<

// Return after adding bit
addBitReturn,0
addBitReturn,0,>

addBitReturn,1
addBitReturn,1,>

addBitReturn,_
add,0,<

addBitReturn,*
add,1,<

// Add 1 bit
add1,0
add1,0,<

add1,1
add1,1,<

add1,_
add1SearchBit,_,<

add1SearchBit,0
add1SearchBit,0,<

add1SearchBit,1
add1SearchBit,1,<

add1SearchBit,_
markBit,1,<

add1SearchBit,*
carryMarkBit,0,<

carryMarkBit,_
addBitReturnStart,*,>

carryMarkBit,0
addBitReturnStart,*,>

carryMarkBit,1
carry,_,<

carry,1
carry,0,<

carry,_
carryReturn,1,>

carry,0
carryReturn,1,>

carryReturn,0
carryReturn,0,>

carryReturn,_
addBitReturnStart,_,>

addBitReturnStart,0
addBitReturnStart,0,>

addBitReturnStart,1
addBitReturnStart,1,>

addBitReturnStart,_
addBitReturn,_,>

// Add 0 bit
add0,0
add0,0,<

add0,1
add0,1,<

add0,_
add0SearchBit,_,<

add0SearchBit,0
add0SearchBit,0,<

add0SearchBit,1
add0SearchBit,1,<

add0SearchBit,_
markBit,0,<

add0SearchBit,*
markBit,1,<

markBit,_
addBitReturnStart,_,>

markBit,0
addBitReturnStart,_,>

markBit,1
addBitReturnStart,*,>

// Cleanup output after modifying output, and return after
outputCleanup,0
outputCleanup,0,<

outputCleanup,1
outputCleanup,1,<

outputCleanup,*
outputCleanupReturn,1,>

outputCleanup,_
outputCleanupReturn,0,>

outputCleanupReturn,0
outputCleanupReturn,0,>

outputCleanupReturn,1
outputCleanupReturn,1,>

outputCleanupReturn,_
returnStart,_,>

// Shift value
shift,0
shift,0,<

shift,1
shift,1,<

shift,_
outputCleanup,_,<

// Finish up
finish,0
finish,_,<

finish,1
finish,_,<

finish,_
done,_,<

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment