The first quarter of 20th Century is often thought as a revolutionary time in mathematics and science. Just as Newtonian physics was rocked by general relativity and quantum physics, in late 1920s fundamentals of computability theory was written by Ackermann and Sudan, mathematician David Hilbert’s graduate students. Mathematician David Hilbert had published list of greatest unsolved mathematical problems at the international math conference in 1900.
The “Fundamentals of Computability Theory” was branch of mathematical logic and was logical analysis of what can be computed versus what cannot be. The basic building blocks of computability theory were computable functions. The quest was to find a largest number in mathematics, which gave rise to computable functions those are recursive in nature.
Thus, the computable “function” kept the same name as function in mathematics which takes input and produces a output. And function was further extended to a logic that a process that enforces this transformation of input to output, in short it is algorithm. A computable function was termed as the function that can be expressed in an algorithm.
Ackerman-Sudan function, as can be simply put, was to create computable functions that can generate large numbers, yet it was more focused to prove those are not primitive recursive. Primitive recursive function means a function that can be computed running using count-controlled loops, such as FOR loops in computer science. In other words the upper bound of the number of times the loop has to be gone through, must be specified in advance.
Multiplication, Exponentiation, Tetration and pentation are various other functions to generate large numbers. These hyperoperators in their broad category falls into recursive functions. Ackerman functions were sufficiently broad to encompass the entirety of hyperoperator sequence. Recursive function if fed back to input, magnifies its capacity to compute endlessly without adding more steps, making never-ending infinite loops.
Alan Turing, an undergraduate student from Cambridge took course in logic and decided to focus on Entscheidungsproblem “decision problem”, (10th problem from David Hilbert’s published list on unsolved mathematical problems) for his graduate research. Decision problem was about a possibility if a step-by-step computability function can decide a output in finite time, if a mathematical statement is true or not. Turing wanted to generalize the solution to decision problem. Turing invented “A” (automatic), machine which was a abstract concept that could visualize computable functionality. By the time, it was started being called as “Turing” machine, Turing decided to build a physical device for such decision making.
Turing through experimentation and American Logician named Alonzo Church through Lambda calculus, that a generalized decision-making process where number is computable or not computable, is impossible. Turing machine made this conjecture provable by showing if a number is computable by Turing machine it is computable. If it is not computable by Turing machine it is a non-computable big number.
Thus a number, how infinite or big, is unreachable if it cannot be computed by human cognitive capacity as well as computing machines. So, can we thought of such numbers as non-existential?
This is to be discussed some other time.
Comments