3 ms·

I got confused here: > Clearly, B is polynomial time decidable, since we need only run a program p for at most n steps, where n is the number of states in p, t

by calf 3y ago

I got confused here: > Clearly, B is polynomial time decidable, since we need only run a program p for at most n steps, where n is the number of states in p, to determine whether or not it is in B. Couldn't program p have an exponential number of states, e.g. 2^|p| distinct program states? Then running the program for O(2^|p|) steps is clearly not polynomial time decidable in the size of the instance. I thought polynomial time, for the decision algorithm, meant O(|p|^c) for some c. Am I mistaken about something?

tromp 3y ago
In this case p is the standard encoding of a Turing Machine with n states, so |p| = n * 2 * (1 + 1 + log(n+1)), so necessarily n < |p|.
- calf 3y ago
  Yes thanks I figured that out later; they define the "state" as what in CS we would call the lines of code or control flow blocks. What I'm curious about is with our usual "modern programmer's" understanding of a state, the state space is exponential in the size of the program. That's why we have model checking and software verification. Whereas this theorem is about programs B whose state space is linear in the length of the encoding of the program, because they're allowed to visit each Turing machine state at most once before halting. At first glance seems like a very specialized case of a class of programs to talk about.
  - tromp 3y ago
    State space refers to the number of states of not just the program counter, but more importantly, the data operated on by that program, which in case of TMs is the tape contents. This theorem is not about programs B whose tape contents is linear in the length of the encoding of the program.
    - calf 3y ago
      The criterion is that p in B must halt before returning to a Program Counter value (what they define as repeating a Turing machine "state"). That's the length of the program text. So, I have no idea why they are talking about polynomials, it looks linear because the program counter has 1 value per line of code in a program text. If not, I would like to know where my misunderstanding could be. Clearly the authors think the paragraph is a simple, obvious step not worth discussing clearly (they say something about running the program for n steps being sufficient, but they do not outright, explicitly say why it would be polynomial, etc.)
      - tromp 3y ago
        Oh, you're right that the criterion for B seems to ignore tape contents. I agree that B is a very uninteresting subset of programs from a programming perspective...

by calf 3y ago

tromp 3y ago

In this case p is the standard encoding of a Turing Machine with n states, so |p| = n * 2 * (1 + 1 + log(n+1)), so necessarily n < |p|.

calf 3y ago
Yes thanks I figured that out later; they define the "state" as what in CS we would call the lines of code or control flow blocks. What I'm curious about is with our usual "modern programmer's" understanding of a state, the state space is exponential in the size of the program. That's why we have model checking and software verification. Whereas this theorem is about programs B whose state space is linear in the length of the encoding of the program, because they're allowed to visit each Turing machine state at most once before halting. At first glance seems like a very specialized case of a class of programs to talk about.
- tromp 3y ago
  State space refers to the number of states of not just the program counter, but more importantly, the data operated on by that program, which in case of TMs is the tape contents. This theorem is not about programs B whose tape contents is linear in the length of the encoding of the program.
  - calf 3y ago
    The criterion is that p in B must halt before returning to a Program Counter value (what they define as repeating a Turing machine "state"). That's the length of the program text. So, I have no idea why they are talking about polynomials, it looks linear because the program counter has 1 value per line of code in a program text. If not, I would like to know where my misunderstanding could be. Clearly the authors think the paragraph is a simple, obvious step not worth discussing clearly (they say something about running the program for n steps being sufficient, but they do not outright, explicitly say why it would be polynomial, etc.)
    - tromp 3y ago
      Oh, you're right that the criterion for B seems to ignore tape contents. I agree that B is a very uninteresting subset of programs from a programming perspective...