2
$\begingroup$

Sorry for being so informal, but I was thinking a bit about how the Halting Problem is solvable on a LBA but very very slow, in that if you have gone though more states in execution then the total number of states possible, the program would be hanging by the pigeonhole principle. But this has the time complexity of O(2^N).

Well, the idea is instead to think of the machine's execution of code as a linked list of states, having a way to quantify the state in an easily comparable manner, and then make use of the Floyd's cycle-finding algorithm. So you can run two instances of the program to be tested at once, where one instance executes a single instruction, and the other instance will execute two instructions, and compare the states. If the states are ever the same, the program has hung. And if I remember right this would be a much much faster process, being a time complexity of just O(N).

Would using my method be feasible or faster, and is there even any use of coming up with a faster methodology?

$\endgroup$
  • 2
    $\begingroup$ The time complexity of Floyd is $O(N)$ where $N$ is the number of possible states, which is exponential in the size of the automata. $\endgroup$ – GMB Oct 28 '14 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.