algorithm - 证明图灵机计入O(n)？

所以在过去的几天里，我一直在设计一个图灵机器，发现在我的实现中，我的二进制计数运行在4n左右，其中n是我计数的数字。所以O（4n）－>O（n）我不是很擅长证明复杂性，但从我从研究中了解到的是，如果你有一个图灵机M，对于{0,1} *中的每个n，T{{M}（n）将需要多长时间来计数n，对吗？如果它不停止，那么它的最高极限是无穷大有没有办法在这两者之间架起一座桥梁，从而得出结论：拥有N个步骤确实是最糟糕的情况？我不知道从哪里开始校对，有什么想法吗？
更新：
下面是我的图灵机二进制计数表示：

import java.util.Scanner;
public class TuringMachine {

/**
 * Divide a number n by 2 shifting right (shift-right-logical)
 * to figure out the minimum number of bits needed to represent
 * the number in binary.
 */
private static int getNumBits(int n) {
    int c = 0;
    while (n > 0) {
        c++;
        n = n >> 1;
    }
    return c;
}

private static void computeBinaryValues(int n) {
    System.out.println();

    int i, c, state;
    char symbol;
    String t;

    System.out.println("Computed binary values for:");

    // Compute values of n = 1 to n
    for (int j = 1; j <= n; j++) {
        t = ""; // temp string
        state = 0; // current state
        symbol = ' '; // current symbol being read
        c = getNumBits(j) + 1; // minimum number of bits needed + 1 for a buffer
        i = c - 1; // indexing starting from end of the string

        // initialize temp string to contain all ' ' characters
        for (int k = 0; k < c; k++) {
            t += " ";
        }

        // String builder off "empty" t string
        StringBuilder s = new StringBuilder(t);
        // The actual binary representation of n + end space buffer
        String a = Integer.toBinaryString(j) + " ";

        // Turing Cycle
        while (!(s.toString()).equals(a)) { // if the binary build is successful, these match.
            if (state == 0) {
                if (symbol == ' ') {
                    state = 1;
                    i--; // left
                } else { // symbols 0 and 1 rewrite themselves && move right 1
                    i++; // right
                }
            } else if (state == 1) {
                if (symbol == ' ') {
                    s.setCharAt(i, '1');
                    state = 0;
                    i++; // right
                } else if (symbol == '0') {
                    s.setCharAt(i, '1');
                    state = 0;
                    i++; // right
                } else {
                    s.setCharAt(i, '0');
                    i--; // left
                }
            }
            symbol = s.charAt(i); // get symbol to read from
        }
        System.out.println(j + " -> " + s); // print binary string created from machine
    }
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.println("Enter value for n >= 1: ");;
    computeBinaryValues(in.nextInt());
}
}

因此，使用Ishtar的建议进行归纳：
C(0) = a
C(1) = b
C(2) = c
设k为常数，假设为4。
c = k + b
b = k + a
他说我们必须证明，然后我解释了它的含义？（我不明白他的理由）

最佳答案

如果我正确地理解了你的问题，你正在试图确定你的图灵机器是否停止，如果它不比最坏的时间复杂度无限，对吗？
如果这是你的问题，你不能在两者之间画一座桥，为什么因为停机问题（解决程序是否停止的问题）在图灵机上是不可判定的，这意味着一个决定是否停止TM的算法不存在（并且永远不会存在）。