algorithm - 在 O(n) 中证明图灵机计数？

Question

所以在过去的几天里，我一直在设计一个图灵机，并发现在我的实现中，我的二进制计数运行在大约 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) = aC(1) = bC(2) = c

设 k 为常数 - 根据我的代码实验假设为 4。

c = k + bb = k + a

他说我们必须证明 c(i+1) = c(i) + k然后我给出了我对它的含义的解释？ (我不明白他的入职案例)

Answer 1

如果我正确理解了您的问题，那么您是在尝试确定您的图灵机是否停止，如果没有停止，那么最坏的时间复杂度是无限的，对吗？如果这是你的问题，那么你不能在两者之间架起一座桥梁，为什么？因为停机问题(确定程序是否停机的问题)在图灵机上是不可判定的，这意味着用于确定 TM 是否停机的算法不存在(并且永远不会存在)。