A Formal Notion of Computability

Another episode of Junferno directly monetising his undergraduate education. Patreon: Twitter: Twitch: Discord: Footnotes: - The origin of the Entscheidungsproblem was from Gottfried 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 an arbitrary 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. A common argument against it is the ability to generate something “truly random“ which may be possible with a quantum computer. A quantum computer cannot, however, solve the Halting Problem. - 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, appointing Jewish professors such as Hermann Minkowski in 1902 and Edmund Landau in 1909 to the University of Göttingen despite anti-semetic discrimination. A famous quote by Hilbert after the rise of Nazism in 1934 to the 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 Austria to Princeton in New Jersey, where he became lifelong friends with German-born Jewish physicist Albert Einstein. In 1952, after cracking messages crucial to British victory in the war against the Nazis, Alan Turing was prosecuted for “homosexual acts“ by the British government, barred from consultancy, and denied entry to the United States. He passed away in 1954. References: #list-4 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 Music tracklist: