Computational self-reference and the universal algorithm

[Philip Thrift]

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

@philipthrift

[Cosmin Visan]

Self-reference is not what you think it is.

[Philip Thrift]

You mean: ... is not what this professor of mathematical logic thinks it is.

@philipthrift

[Cosmin Visan]

 Or that.

[Bruno Marchal]

Yes, that’s beautiful work. Quite advanced, though. The wonderful world of ZFC + Determinacy. 

But most people have already difficulties for the extremely simple first order arithmetic of for the combinatory algebra, so set theory, … well, my student asks me to do a little bit of it, and I took pleasure explains the behavior  of the Goodstein sequences, which motivates in arithmetic for using transfinite induction.

It might take month of work to get that paper right, so I will stay mute on its relation with Indexical Digital Mechanism, at least for some period. But it is excellent theology!

I have thousand of extraordinary paper on arithmetical and set-theoretical self-reference, it is a blooming subject, even if sometimes, the fashion carried a bit away, but it always comes back, and self-reference is where mathematical logic taught the most fascinating discovery, to begin with Gödel 1931.

Bruno

--
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 everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/aff13ede-4051-4509-aa52-4a9a1484dd31%40googlegroups.com.

[Lawrence Crowell]

It occurred to me that the Quine statement is one which in a quantum computer would duplicate a state. A quantum state ψ that is a set of qubits and a set of operations {O} will as a Quine Q = {O, ψ} result in producing itself with ψ → ψψ and Q^2 = {O×O,.ψψ}. This is not something permissible in QM, so there must be a Hadamard gate operation that demolishes quantum phase. 

The reason why this duplication of quantum states is not quantum mechanical is that for ψ = a|+> + b|-> then a duplication ψψ is

ψψ = a^2|++> + b^2|--> + ab(|+-> + |-+>). 

However, if this duplication is unitary I can transform to a basis so the duplicated state is a^2|++> + b^2|-->, bu just duplicating on these basis elements. But no such unitary transformation exists. 

LC

[Bruno Marchal]

On 5 Jun 2019, at 12:21, Philip Thrift <cloud...@gmail.com> wrote:

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

[Bruno Marchal]

On 5 Jun 2019, at 15:22, 'Cosmin Visan' via Everything List <everyth...@googlegroups.com> wrote:

Self-reference is not what you think it is.

That is a weird statement, almost comical!

But I guess I agree with you somehow. Hamkins' paper exposed what I would call the classical theory of third person self-reference. It is more about or bodies or our representations than about the indexical owner of the experiences: the first person self. 

Your notion of self-reference seems to correspond to that one. With mechanism, the first person “I” is not a machine, nor anything 3p. It is pure 1p. It has no description, at least from his/her perspective. God knows they are the same, but here, only god knows that. More precisely, with “beweisbar” ([]p) playing the role of the 3p self, the 1p self is given by the Theaetus’ definition ([]p & p), and we have:

G* proves []p <-> []p & p,

But G does not prove this in general and the logic of []p and []p & p associate to the machine are very different. From the 1p view, “[]p & p” is not even definable by the self-referentially correct entities. 

The universal machine has a soul, and she knows already that her soul is not a machine.

Bruno 

--
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 everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/42fd1e62-385f-4f92-ae1a-058f5ff3be47%40googlegroups.com.

[John Clark]

On Thu, Jun 6, 2019 at 4:09 AM Bruno Marchal <mar...@ulb.ac.be> wrote:

On 5 Jun 2019, at 15:22, 'Cosmin Visan' via Everything List <everyth...@googlegroups.com> wrote:

>> Self-reference is not what you think it is.

> That is a weird statement, almost comical!

I could not fail to disagree with you less. To define recursion you must first define recursion.

John K Clark

[Bruno Marchal]

On 7 Jun 2019, at 15:58, John Clark <johnk...@gmail.com> wrote:

On Thu, Jun 6, 2019 at 4:09 AM Bruno Marchal <mar...@ulb.ac.be> wrote:

On 5 Jun 2019, at 15:22, 'Cosmin Visan' via Everything List <everyth...@googlegroups.com> wrote:

>> Self-reference is not what you think it is.

> That is a weird statement, almost comical!

I could not fail to disagree with you less.

Hmm Two negations, after a day of oral exam! You really want to kill me, don’t you?

To define recursion you must first define recursion.

I don’t even see the relationship with my comment.

What can I say? 

I have define recursion using the combinators, some month ago.

I can also define/implement recursion/recursive procedure using only very elementary, arithmetic (first order arithmetic without the induction axioms). It is already much longer than with the combinators, which needed a bit more than an half-dozen posts.

Now, in computer science, there is two theorems of recursion: the first one concerns extensional functions, the second one concerns the code of the functions, but again, both are verified/satisfied in elementary arithmetic.

We need only to assume one universal machinery, to get them all, with all their relative implementations, to get us to the formulation of the mind-body problem, or first person view/third person reality relation problem, which indeed, as some have intuited in this list is a measure problem.

You seem to assume that the universal machinery *is* the physical universe, but then you need to define it properly and explain how it selects your consciousness from all the infinitely many Turing equivalent computations realised in elementary arithmetic or/and combinator algebra.

Using the physical universe, in a metaphysical discussion, to say that it is the one who makes that selection is as much informative as saying, because god made it.

Bruno

John K Clark

--
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 everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv2njpq83sNu%3DvP%2BBkzncBrkom1gCq28XWS2ZHnMGeS%3DVg%40mail.gmail.com.

[John Clark]

On Fri, Jun 7, 2019 at 1:13 PM Bruno Marchal <mar...@ulb.ac.be> wrote:

>> I could not fail to disagree with you less.

 

> Hmm Two negations, after a day of oral exam! You really want to kill me, don’t you?

Nothing as violent as that, it's just that I ran across that phrase a few years ago and for some reason it stuck in my head even though I couldn't make heads or tails out of of it. Does it mean I agree with you or disagree?

John K Clark

 

To define recursion you must first define recursion.

I don’t even see the relationship with my comment.

What can I say? 

I have define recursion using the combinators, some month ago.

I can also define/implement recursion/recursive procedure using only very elementary, arithmetic (first order arithmetic without the induction axioms). It is already much longer than with the combinators, which needed a bit more than an half-dozen posts.

Now, in computer science, there is two theorems of recursion: the first one concerns extensional functions, the second one concerns the code of the functions, but again, both are verified/satisfied in elementary arithmetic.

We need only to assume one universal machinery, to get them all, with all their relative implementations, to get us to the formulation of the mind-body problem, or first person view/third person reality relation problem, which indeed, as some have intuited in this list is a measure problem.

You seem to assume that the universal machinery *is* the physical universe, but then you need to define it properly and explain how it selects your consciousness from all the infinitely many Turing equivalent computations realised in elementary arithmetic or/and combinator algebra.

Using the physical universe, in a metaphysical discussion, to say that it is the one who makes that selection is as much informative as saying, because god made it.

Bruno

John K Clark

--
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 everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv2njpq83sNu%3DvP%2BBkzncBrkom1gCq28XWS2ZHnMGeS%3DVg%40mail.gmail.com.

--
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 everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/79F1B71F-4AF5-444B-8D17-07F34AED819D%40ulb.ac.be.

[Bruno Marchal]

On 9 Jun 2019, at 18:03, John Clark <johnk...@gmail.com> wrote:

On Fri, Jun 7, 2019 at 1:13 PM Bruno Marchal <mar...@ulb.ac.be> wrote:

>> I could not fail to disagree with you less.

 

> Hmm Two negations, after a day of oral exam! You really want to kill me, don’t you?

Nothing as violent as that, it's just that I ran across that phrase a few years ago and for some reason it stuck in my head even though I couldn't make heads or tails out of of it. Does it mean I agree with you or disagree?

That you agree with me, I would say.

Bruno

John K Clark

 

To define recursion you must first define recursion.

I don’t even see the relationship with my comment.

What can I say? 

I have define recursion using the combinators, some month ago.

I can also define/implement recursion/recursive procedure using only very elementary, arithmetic (first order arithmetic without the induction axioms). It is already much longer than with the combinators, which needed a bit more than an half-dozen posts.

Now, in computer science, there is two theorems of recursion: the first one concerns extensional functions, the second one concerns the code of the functions, but again, both are verified/satisfied in elementary arithmetic.

We need only to assume one universal machinery, to get them all, with all their relative implementations, to get us to the formulation of the mind-body problem, or first person view/third person reality relation problem, which indeed, as some have intuited in this list is a measure problem.

You seem to assume that the universal machinery *is* the physical universe, but then you need to define it properly and explain how it selects your consciousness from all the infinitely many Turing equivalent computations realised in elementary arithmetic or/and combinator algebra.

Using the physical universe, in a metaphysical discussion, to say that it is the one who makes that selection is as much informative as saying, because god made it.

Bruno

John K Clark

--
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 everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv2njpq83sNu%3DvP%2BBkzncBrkom1gCq28XWS2ZHnMGeS%3DVg%40mail.gmail.com.

--
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 everything-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/79F1B71F-4AF5-444B-8D17-07F34AED819D%40ulb.ac.be.

--
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 everything-li...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv0Zgqg7CQ3yWMDLpfpF71fNGsbHYg0M5SdPkSZDrg7dWQ%40mail.gmail.com.