java/ch/wlkl/div/TuringMachine.java

package ch.wlkl.div;

import java.util.Arrays;

import ch.wlkl.wsh.Top;



public class TuringMachine extends Top {
    public char cur = 0;
    public char wri = 0;
    public boolean right = true;
    public char end = 0;
    public char displayNull = '/';
    private char [] tape = null;
    private int tape0x = 0;
    private int tapeIx = 0;
    
    public void copy (char[] dst, int start, char[] src) {
        for (int ix = 0; ix < src.length; ix++) 
            dst[start + ix] = src[ix];    
    }
    
    public void copy (char[] dst, int start, CharSequence src) {
        for (int ix = 0; ix < src.length(); ix++) 
            dst[start + ix] = src.charAt(ix);    
    }
    
    
    public String run(CharSequence inp) {
        int tCnt = 0;
        end = 0;
        tapeIx = tape0x = 10;
        if (tape == null || tape.length < 2 * tapeIx+ inp.length())
            tape = new char[2 * tapeIx+ inp.length()];
        Arrays.fill(tape, (char) 0);
        copy(tape, tape0x, inp);
        reset();
        while (end == 0) {
            wri = cur = tape[tapeIx];
            transition();
            tCnt++;
            tape[tapeIx] = wri;
            if (right ? ++tapeIx >= tape.length : --tapeIx < 0) {
                char [] newTape = new char[2 * tape.length];
                Arrays.fill(newTape, (char) 0);
                if (right) {
                    copy(newTape, 0, tape);
                } else {
                    copy(newTape, tape.length, tape);
                    tapeIx += tape.length;
                    tape0x += tape.length;
                }
                tape = newTape;
            }
        }
        int ex = tape.length;
        while (--ex >= tape0x && tape[ex] == 0 )
            ;            
        StringBuffer buf = new StringBuffer(++ex - tape0x);
        for (int ix = tape0x; ix < ex; ix ++)
            buf.append(tape[ix] == 0 ? displayNull : tape[ix]);
        return String.valueOf(tCnt) + ' ' + end + " -> " + buf;        
    }
    
    public void transition () {
        end = 'e';
    }
    
    public void reset () {
        
    }
    
    public static void main(String ... args) {
        String s = "abcdefghij";
        sSay(new TuringMachine$Test().run(s));
        TuringMachine tm = new TuringMachine$Reverse();
        for (int ix = s.length(); ix >= 0; ix--)
            sSay(tm.run(s.substring(0,ix)));
    }
}

class TuringMachine$Test extends TuringMachine {
    StringBuffer buf = new StringBuffer();
    int st = 0;
    
    public void reset () {
        buf.setLength(0);
        st = 0;
    }
    
    public void transition () {
        switch (st) {
        case 0:
            if (cur == 0)
                st++;
            else
                buf.append(cur);
            break;
        default:
            if (buf.length() > 0) {
                wri = buf.charAt(buf.length() -1);
                buf.setLength(buf.length() -1);
            } else {
                if (st++ > 1)
                    end = 'z';
                buf.append("end").append((char) 0).append("fertig").append((char) 0).append((char) 0).append('?');
                buf = buf.reverse();
            }
        }        
    }
}

class TuringMachine$Reverse extends TuringMachine {
    char carry = 0;
    char st = 0;
    
    public void reset () {
        carry = 0;
        st = 'r';
    }
    
    public void transition () {
        switch (st) {
        case 'r':
            if (carry == 0) {
                if (cur == 0) {
                    right = true;
                    st = '<';
                    carry = 1;
                } else {
                    carry = cur;
                    wri = 0;
                }
            } else {
                if (cur == 0) {
                    wri = carry;
                    carry = 0;
                    right = ! right;
                }
            }
            break;
        case '<':
            if (right) {
                if (carry == 0) {
                    carry = 1;
                } else if (cur == 0) {
                    end = 'e';
                } else {
                    carry = cur;
                    right = false;
                    wri = 0;
                }
            } else {
                wri = carry;
                right = true;
                carry = 0;
            }
            break;
        default:
            fail("state " + st);
        }        
    }
}