> On 5 Jun 2019, at 12:21, Philip Thrift <[email protected]> wrote: > > > Computational self-reference and the universal algorithm > Queen Mary University of London, June 2019 > > via @JDHamkins > > This was a talk for the Theory Seminar for the theory research group in > Theoretical Computer Science at Queen Mary University of London. The talk was > held 4 June 2019 1:00 pm. > > > Abstract. Curious, often paradoxical instances of self-reference inhabit deep > parts of computability theory, from the intriguing Quine programs and > Ouroboros programs to more profound features of the Gödel phenomenon. In this > talk, I shall give an elementary account of the universal algorithm, showing > how the capacity for self-reference in arithmetic gives rise to a Turing > machine program e, which provably enumerates a finite set of numbers, but > which can in principle enumerate any finite set of numbers, when it is run in > a suitable model of arithmetic. In this sense, every function becomes > computable, computed all by the same universal program, if only it is run in > the right world. Furthermore, the universal algorithm can successively > enumerate any desired extension of the sequence, when run in a suitable > top-extension of the universe. An analogous result holds in set theory, where > Woodin and I have provided a universal locally definable finite set, which > can in principle be any finite set, in the right universe, and which can > furthermore be successively extended to become any desired finite superset of > that set in a suitable top-extension of that universe. > > http://jdh.hamkins.org/computational-self-reference-and-the-universal-algorithm-queen-mary-university-of-london-june-2019/ > slides: > http://jdh.hamkins.org/wp-content/uploads/Computational-self-reference-and-the-universal-algorithm-QMUL-2019-1.pdf
I found sometime, during the June-exams, to read a bit of it. The first part is an introduction to what I have called in this list (and some of my papers) third person self-reference, which is based on the second recursion theorem of Kleene (but somehow present in Gödel’s “famous” diagonal lemma. It is the classical theory of self-reference (that I have exposed and use for biological self-reproduction, but also, thank to a generalisation by Jon Case, to self-regeneration (cf my paper “amoeba, planaria, dreaming machine”. The second part lack a bit of motivation, and seem to generalise such theory in set theory, or in non mechanist context. I have to dig more. I was expecting more from the mention of Woodin, who has interesting contribution in the theory of large cardinal (almost close to sensfull non-mechanist" theology”!). Note that “universal” here is not the usual computer-science notion of universality. But the result here shows well how much relation is the notion of third person self-reference. Bruno > > > @philipthrift > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/aff13ede-4051-4509-aa52-4a9a1484dd31%40googlegroups.com > > <https://groups.google.com/d/msgid/everything-list/aff13ede-4051-4509-aa52-4a9a1484dd31%40googlegroups.com?utm_medium=email&utm_source=footer>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/183DB644-7103-4A25-AF91-88A0CF9BAE31%40ulb.ac.be.
