3 ms·
It still is applicable, as long as you have a bound on the number of unknown states, however the number of computation steps in this case is so high that it is
by xyzzyz 15y ago
It still is applicable, as long as you have a bound on the number of unknown states, however the number of computation steps in this case is so high that it is even less practical than the totally unpractical algorithm I proposed in my first comment.
Let's consider both computers (yours and 3rd party) as a single computational device, with a state represented by a pair of symbols, where the first represents your computer and the second the 3rd party's. Suppose your computer has N states and the other M. It's enough to run N * M + 1 computation steps -- if your program hasn't ended so far, it will never, for there's a certain state (a, b) that must have occured twice, by the pigeonhole principle.
Please keep in mind that this is all purely theoretical, and not at all practical. It's just a counterargument to other purely theoretical argument from unsolvability of halting problem.