Helena Louise Collert: Vad skulle vi göra utan Turingmaskiner

Abstract: Even though we have been using calculations for thousands of years, it is a young discipline in mathematics to understand what it actually means to be computable. Is 2 · 4 = 8? Of course! everyone except the very youngest would probably answer. But it is not obvious. The fact is that there are few self evident calculations. One calculation that everyone has been able to agree on is that after 0 comes 1 and after 1 comes 2 . . . Or not really that one either. What is agreed upon is that after a number comes a number that is 1 more than that particular number. That definition of a calculation is one of three so called Base functions forming the basis of all calculations in the entire world.. This work will try to explain how Church-Turing thesis, the very definition of what is computable, emerged. My main task is to present ONE form of computability, the theory of Partial Recursive functions. But we will also look at the λ-calculus, which form the basis of several, still current, computer languages. And for the more tangible understanding of how computability is built up we will study the URM, a simplified version of the modern computer’s predecessor, the Turing machine. I will also present two of the proofs showing that the so called Decision problem has no solution.