> To be truly Turing complete requires infinite memory. That clearly doesn't hold for any current programming language. > Indeed I have a simple algorithm (alt

> To be truly Turing complete requires infinite memory. That clearly doesn't hold for any current programming language. > Indeed I have a simple algorithm (although relatively inefficient) to solve the halting problem where memory size is fixed and finite: enumerate every state until either a state is repeated or the program halts. This completes in O(2^N) time where N is the size of the memory. "Relatively inefficient" is a colossal understatement. Anything that we would nowadays categorize as a "computer" has a state space so huge that, while technically finite, it is effectively infinite for all practical purposes. For example: the ATmega328 microcontroller in an Arduino has 2KB of RAM (assuming we ignore registers and the possibility of storing data in Flash). That's a total of 2^16384 possible states. If every cubic Planck length of the observable universe was capable of checking one of these states per Planck time, and did so from the Big Bang until the heat death of the universe (let's say 10^100 years in the future), they would still have enumerated only a googol'th of a googol'th of a googol'th of a googol'th [... repeat about 10 more times...] of the state space. We could of course imagine trying to find a better algorithm, but since this problem is easily shown to be NP-hard, it is very unlikely that we will find something that guarantees good enough performance to make this kind of analysis possible. We haven't "given up" on automated program analysis. It's just that the fully general case is intractable, and it takes a lot of hard work and ingenuity to find strategies that can separate the tractable problems we care about from the intractable ones.