3 ms·
The meat of the paper is this short > Proof of the Main Theorem Using the standard model > let B be the set of programs that on input 0 either halt before rep
by tromp 3y ago
The meat of the paper is this short
> Proof of the Main Theorem Using the standard model
> let B be the set of programs that on input 0 either halt before repeating a state or fall off the tape before repeating a state. 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. It is equally clear that the halting problem is polynomial time decidable for programs p in B, since again we need only simulate p for n steps to know whether it halted or fell off. What remains is to prove that this behavior occurs with asymptotic probability one.
The proof also makes use of this
> Lemma 2.5 (Polya [2], see also, e.g., [1])
> In the random walk with equal likelihood
of moving left or right on a semi-infinite tape, beginning on the left-most cell, the
probability of eventually falling off the left edge is 1.
This suggests that the result crucially depends on having a one-sided infinite tape rather than the two-sided infinite tape that's used in the Turing Machine busy beaver.
It would be interesting to determine whether the result also holds for that other computational model, i.e. what about the set of lambda calculus terms with or without a normal form?
- calf 3y agoI 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 agoIn 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 agoYes 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 agoState 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 agoThe 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 agoOh, 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...