A Formal Notion of Computability

Another episode of Junferno directly monetising his undergraduate education.
Patreon: / junferno
Twitter: / junferno
Tumblr: www.tumblr.com...
Twitch: / junferno
Discord: / discord / discord
Footnotes:
- The origin of the Entscheidungsproblem was from Leibniz, who considered it after developing a mechanical calculating machine in the 17th century. Hilbert posed the problem with Wilhelm Ackermann in continution of his program of problems, which were problems he considered to be the most significant mathematical problems of the 20th century (which includes the Riemann hypothesis).
- General recursive functions (or mu-recursive functions) would later be the basis of recursion theory, founded by Rózsa Péter from Gödel's work.
- Church's lambda calculus would later influence the notation of the functional programming language Lisp, though Lisp was not originally derived from lambda calculus.
- Turing-complete means "able to simulate any Turing machine". Turing-complete machines existed before Turing, but were not used to their potential, such as Charles Babbage's analytical engine in 1837, which was designed for arithmetic calculation. Ada Lovelace was the first to recognise that Babbage's engine may be used for more complicated logical operations. Her note (1842-43) on using the engine to compute a sequence of Bernoulli numbers is often cited as the first computer program.
- Turing did not name his machines "Turing Machines" in his original paper, but rather Logical Computing Machines (LCMs). Rather than proving logical statements, they "computed numbers", as in they generated numbers digit-by-digit. Numbers that could be generated by LCM were "computable numbers". Turing's negative proof of the Entscheidungsproblem was not in regards to the Halting Problem, but rather in regards to computing whether a machine will ever output the digit 0. This was equivalent to computing problems however, as logical statements can be encoded with numbers (see Gödel numbering).
- Post's approach to computability was very much in the perspective of the human mind, as opposed to Gödel's rational approach. Post developed an equivalent model to Turing's machines independent to Turing just a few months after Turing's paper, which used a two-way infinite "symbol space". Hence, the video states that Post both "agrees and disagrees" with the Turing Machine, as (from what I can tell) Post's independent approach is equivalent mathematically but not so much philosophically.
- A common misconception is that Turing claimed that no machine could compute something that a Turing Machine can not. Turing never explicitly stated this, as he only proposed a definition of "effective computability", but it is a topic still debated on today. While there are theories for quantum "hypercomputation", quantum computing as we know it (Deutsch 1985 presented at 13:34) has the same computing power as Turing Machines, just faster. Deutsch, however, does claim that his Church-Turing-Deutsch principle encompasses every physical process.
- The Church-Turing thesis continues to be accepted as all alternative models of computability developed (Post, Schönfinkel, Curry, Markov) just end up being equivalent to Turing computability.
- Turing spent his later years conceptualising the design for the stored program computer alongside John von Neumann, who created the von Neumann architecture.
- David Hilbert's speech, "Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country", was in light of the exclusion of German mathematicians post-World War I. It is likely that he did not end up delivering it due to poor health. Nonetheless, Hilbert remained supportive of Jewish students and colleagues. A quote by Hilbert in 1934 to the Nazi Minister of Education in reference to the removal of Jews from academia was that "There is no mathematics in Göttingen anymore."
- In 1939, Kurt Gödel fled Nazi-occupied Austria to Princeton University, where he befriended German-born Jewish physicist Albert Einstein.
- In 1952, despite cracking messages crucial to British victory against fascism, Alan Turing was prosecuted for "homosexual acts" by the British government. He passed away in 1954.
References: www.junferno.c...
Photos courtesy of Wikimedia Commons, Sega
3D models via Sketchfab courtesy of cameronac
Licensed music Creative Commons Attribution license (reuse allowed) J-POP Karaoke - きただにひろし - ウィーアー!(アニメ『ONE PIECE』OP)
Gameplay footage courtesy of Cibley, Mayor Mori, Tiger
Junferno is not endorsed by nor associated with any artists or creators featured
Thank you Red Slendy for providing stylised English CC!
Music tracklist: • The Complete Junferno ...