Computable or not computable?

[Bruno Marchal]

1, 3, 14, 173, 16951, ...

Computable or not computable?

I would conjecture that it is not computable.

It is the number of way to ‘configure’ circles (in the affine plane)

It gives pretty pictures. 

Explanation by Neil Sloane:

https://youtu.be/bRIL9kMJJSc

Note that the predicate “computable”, (on the incites I of the phi_i) is itself an exemple of well defined but  (highly) non computable number property, as I have shown many times.

It is pi_2 complete. Riemann hypothesis is pi_1.

Bruno

[Lawrence Crowell]

Could you elaborate on this?

LC

[Bruno Marchal]

On 23 Mar 2021, at 02:27, Lawrence Crowell <goldenfield...@gmail.com> wrote:

Could you elaborate on this?

I cannot really elaborate on Sloane question. It takes time to show the undecidability of simple combinatorial system, and showing this in geometry might be as hard, if not harder than showing the undecidability of the equality of Diophantine Polynomial equation.

What I can show quickly is the non computability of the predicate computable. It is not well known, except by the best like Judson Webb and Stephen Kleene and myself (grin), but incompleteness and (essential) undecidability is a simple (one diagonalisation) consequence of the Church-Turing thesis, actually from weaker version of Church-Turing Thesis.

Church’s thesis asserts that a function from N to N is computable if an only it can be defined by a lambda expression (or a combinator if you prefer).

Turing’s thesis asserts that a function from N to N is computable if an only it can be defined by a set of quadruplets (with shape q_i S_j S_k q_r, etc. I have explained this before).

It is a well know theorem that Church’s thesis and Turing’s thesis are equivalent.

The weaker thesis asserts only that such a universal language/system, or universal machinery, exists, in which we can indeed describe how to compute all computable function from N to N.

Indeed, if such a universal language exists, it will compute much more than the computable functions. It will compute also the partial functions from N to N, which are defined possibly on some subset of N.

Why? Because either your language truly describes only computable functions from N to N, but then you can enumerate the expression of your language, lexicographically (by order length, and then alphabetically for those having the same length) and you get all computable functions from N to N in a computably enumerable list F_0, F_1, F_2, F_3, … But then the function

G(n) = F_n(n) + 1 is computable, and so admit a program in your list, and so is equal to some F_k,

But then G(k) = F_k(k) = F_k(k) + 1. 

All the F_k are computable, by the assumption above, so either that language is not universal, and indeed cannot define G, or … your language compute more than the computable function from N to N: it computes also the non computable one, that is, the partial computable functions, (although they are more like computable partial functions). In that case, you can still claim to have a universal language (for the computable functions (and partial computable functions)), and what will have to happen is that G, will be programmable/describable, but run forever on its own code F_k(k) will not stop.

Nor could any effective theory be complete on the question "is x the code of a computable or strictly partial computable”? As if it was, we could use it to extract a computable enumeration of all computable function (from N to N), and the contradiction above occur.

The predicate “computable” can be shown very complex, PI_2 complete, that is why it is easier to prove its undecidability, in one diagonalisation from the Church or the Turing thesis.

CT => incompleteness, so you can see incompleteness as saving the Church’s thesis from diagonalisation, and confirming it inductively (a completeness theorem for arithmetic would have made no Church’s-like theses possible, and computability would be, like provability, a relative notion.

The absoluteness of computability is the most amazing mathematical (but unprovable) fact. Gödel, who was quite skeptical on the Church-Turing thesis, but got it in 1936 after studying a paper by Turing, is right to call it a “miracle”: i.e. the closure of the partial computable functions (including all non partial, total, from N to N) for the diagonalisation procedure. The price is high: it is the liberty to search for number which might not exist, making you never halting…

To get Gödel, on arithmetic, it is enough to show that it can represents all partial computable functions. I did it for the combinators here, but for arithmetic it is much longer and tedious. The more simple is some notion (like diophanine polynomial, circles configurations) the more complex it is to prove their essential undecidability. Essential means you can never get completeness by adding computable or even partial computable sets of axioms.

I hope I was not to short, or to long. But that’s the key to get right the impact of Gödel’s theorem about what a physical reality can look like, from the universal machine’s perspective, and indeed, they understands already that the probability of going from state A to state B, whatever they are (as long as locally digitally encodable) involves infinitely many computations.

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/de0c9d85-d467-48e6-aadd-5c9bc09eba54n%40googlegroups.com.