Comment by cantankerous

Yes, but our memory is so big and our machines can have so many states that the problem is still intractable in the general case.