Decoding The Church-Turing Thesis

Spire Digital
Spire Digital
May 8, 2017

Software is under increasing pressure to do more and do better. However, in computing, the major performance gain has been the mechanical size and speed of electrical machines. Yet, the mathematical power of programming remains constant. For this reason I believe successful software has less about code and more about creative organization. I want to reflect on this belief through the lens of computability.

Alan Turing imagined a machine, now called a Turing Machine, that demonstrated a definition of computability. It consisted of a tape with a head that had read/write access at one square.  Personally, I like to imagine Turing’s machine not with magnetic tape, but using fabric strings of infinite length. In any case, Alonso Church also found similar results using his lambda calculus. Both men had the same idea independent of one and other and each published their work in 1936. Together, they put forward the idea that there is no universal algorithm that can solve all mathematical problems.

Turing goes on to say that a Turing Machine can solve all computable problems, however, not all problems are computable. Until this can be disproved, which has not yet happened, we can, for the purpose of sanity, take this to include modern mechanical computers, because a Turing Machine can model any mechanical computer. Accepting this notion allows us to shift our thinking so that we engage programming with success.

Hundreds (maybe millions) of hours have been dedicated to debating the Church-Turing Thesis. Perhaps natural inquiry, competition, and academic interest are the reason. In any case, people often fail to realize that ‘facts’ alone cannot be used to determine the outcome of an event. This encourages me to keep something in mind: programs and programmers alike cannot anticipate with certainty the outcome of any executable code until after it has finished. For the regular workday, that means designing good tests.

Thinking a bit more about what it means when we mention that a Turing Machine can model all mechanical computers, we realize that this is the limit of computing power. The code language that runs these machines is also exposed to this limitation, but it also elevates nearly all our programing languages to equal power.

This is another rule I like to keep in the back of my mind because there is always a hot new code base or framework (more than likely by media pressures) that demands our time and attention.  These new solutions always offer success.  And I like to think: well of course you can write new code to do that and, in fact, if you couldn’t that would actually be interesting, since it’s all pretty much the same in the eye of a computing machine.

I recognize the need, or at least the advantage, for improved speed and performance. And here again, I like to think about the equality of computing. The real force behind speed and performance is human organization. A group familiar with a certain methodology may very well out perform a “more optimal” programming methodology. Human organization makes that happen. Programming trends are certainly not computable as defined by Church and Turing and I would like to explore the theory of structural transformation of computer programming due to media pressures, but that’s another post.

To leave off, I want to emphasize that if we look to the current, most accepted theses on computability, we find that computers do not make decisions outside a fairly limited world of computability. These wonderful machines enrich our lives because humans have organized them this way.  I believe that, in the development process, the organization and placement of the functions doing the actual computations is equally as important as designing the strategy that makes it look like the machine is doing all the work.

We use cookies to personalize content and ads, to provide social media features and to analyze our traffic. We also share information about your use of our site with our social media, advertising and analytics partners. Read our cookie policy here

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.