// Input: a binary string s
// Ouput: accepts if s is a palindrome
// Example: accepts 10101
//
// Palindrome Algorithm from slides
// for Turing Machine Simulator 
// turingmachinesimulator.com
//
// Tapes:
// #1      input tape
// #2      working tape
//
// States:
// qinit   initial state
// qcopy   copy input tape to working tape
// qleft   rewind input tape cursor to left position
// qtest   check correspondance letter-by-letter
// qyes    accepting state
// qno     rejecting state
//
//
// NB: input word must start with $

name: Palindrome MT from slides
init: qinit
accept: qyes

// Set initial $ symbol
qinit,$,_,
qcopy,$,$,>,>

// Copy input tape to work tape
qcopy,0,_
qcopy,0,0,>,>

qcopy,1,_
qcopy,1,1,>,>

qcopy,_,_
qleft,_,_,<,-

// Rewind cursor of input tape
qleft,0,_
qleft,0,_,<,-

qleft,1,_
qleft,1,_,<,-

qleft,$,_
qtest,$,_,>,<

// Testing
qtest,_,$
qyes,_,$,-,-

qtest,0,0
qtest,0,0,>,<

qtest,1,1
qtest,1,1,>,<

qtest,0,1
qno,0,1,-,-

qtest,1,0
qno,1,0,-,-