图灵机二进制计数器

Question

为了练习，我决定创建一个模拟图灵机方法的二进制计数器。具体来说，我打算从这个模仿第一个例子：(https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/four.html) 然后我会更进一步为我的机器创建更多！

我对这个例子的适应是，我希望有一个设定的数字来计数，然后停止——而不是一次递增 1。

我正在使用 switch 案例，因为我有一段时间没有使用它们了，早些时候，我有相同的（改编的）代码用于 if-else 块。

我目前遇到的问题是，我的计数器似乎没有超过 "tape." 的 2 个进步，下面显示它可能卡在某个地方。我怀疑它在这里：

case 2:
    switch (symbol) {
        case ' ':
            s[i] = ' ';
            state = 0;
            i++;
            break; // here?

如上例所示，在此 class 中放置一个递增函数并在 while (c<8) 中调用该递增函数是否更明智？但这不需要调用静态变量吗？稍后，当我为我的机器创建更多操作时，会产生问题，是吗？

public class TuringMachineSimulations {

    private static void print(char[] s) {
        for (int i = 0; i < s.length; i++) {
            System.out.print(s[i] + "_");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        int n = 8; // number to count up to in binary 
        int c = 0; // counter
        int i = 0; // index counter within 'string'
        int state = 0; // state control
        char symbol = ' '; // what symbol is currently being read - starting is blank
        char[] s = new char[4]; // 4 bits needed to hold the integer "8" in binary

        while (c < 8) {
            switch (state) {
            case 0:
                switch (symbol) {
                case ' ':
                    s[i] = ' ';
                    state = 1;
                    i++;
                    break;
                case '0':
                    s[i] = '0';
                    state = 0;
                    i--;
                    break;
                case '1':
                    s[i] = '1';
                    state = 0;
                    i--;
                    break;
                default:
                    break;
                }
            case 1:
                switch (symbol) {
                case ' ':
                    s[i] = '1';
                    state = 2;
                    i--;
                    break;
                case '0':
                    s[i] = '1';
                    state = 2;
                    i++;
                    break;
                case '1':
                    s[i] = '0';
                    state = 1;
                    i++;
                    break;
                default:
                    break;
                }
            case 2:
                switch (symbol) {
                case ' ':
                    s[i] = ' ';
                    state = 0;
                    i++;
                    break;
                case '0':
                    s[i] = '0';
                    state = 1;
                    i--;
                    break;
                case '1':
                    s[i] = '1';
                    state = 1;
                    i--;
                    break;
                default:
                    break;
                }
            }
            symbol = s[i];
            print(s);
            c++;
        }
    }
}

P.S。我希望得到它，使得最低有效位是第一位。

Answer 1

在我看来，您似乎假设每一步都涉及二进制数的递增。你是运行你的 'steps' 只有 8 次。但是其中许多步骤根本不涉及更改 'tape' - 在状态 0 和 2 中移动 'head' 并且状态已更改但磁带没有更改。

如果您知道您想要的 's' 的最终状态（大概是“1000”），那么最简单的方法就是将 while (c < 8) 替换为 while (!String.valueOf(s).equals("1000"))。

图灵机二进制计数器

Turing Machine Binary Counter

java

binary

turing-machines