, ,

Some tasks, processes, “computations,” are too difficult to do in any practical context. Some are so intrinsically hard that, even while they don’t seem especially difficult, God herself could not do them. The first is the problem of computational complexity, the other of computability/solvability. The former, complexity, emerged from the latter, computability, because the problem of computability was more obvious to mathematicians who’d never seen, much less actually used, a computer. But after Alan Turing presented his own abstract model of a computing “machine” (the “Turing Machine,” or TM) to prove the existence of unsolvable mathematical problems, the difference between what could be solved in theory (computability) and what could be solved in practice (complexity) came into view, and methods were developed to investigate the latter as well as the former. This is all by way of summary of, and pointing forward from, the previous post.

Mechanical Turing Machine

There are theoretical &/or partial work arounds, ways of tricking out the game, for both complexity and computability. For complexity, it is unclear whether the trick can be realized in practice. For computability, it is unclear whether the trick (which is only a partial trick, really) is even physically possible. Still, I’m going to talk a little about both – in the preceding order – and finish with some comments on how these theoretical considerations can be manifested in our considerations of what does and what does not constitute legitimate scientific inquiry, and a few comments closing the circle on analysis versus ontology.