On 21 Jan 2014, at 21:49, meekerdb wrote:
On 1/21/2014 4:33 AM, Bruno Marchal wrote:
That is already present in Gödel 1931, and today we know that even
just one diophantine (on integeres) polynomial of degree four can
emulated all computations; or be Turing universal.
Just to check that I understand what that means: There is a
diophantine equation such that you can parse a solution set of the
equation into an input and a result such that the set of all such
solutions sets correspond to all possible functions (in
arithmetice). Right?
Er... Well, I am not sure I can parse this :)
Let me restate the point a bit more precisely.
Let {phi_i, w_i} be an enumeration of the partial computable phi_i
with their respective domain w_i. A partial computable function with
w_i = N is called total. OK.
Now phi_i(x) = y can be translated into arithmetic (using for example
the Kleene predicate). In fact it can be put in the form of <x, y>
belongs to some w_i.
More simply, the set of finite computations (the set of the initial
segment of UD*, for example) is a recursively enumerable (RE) set, and
thus is a w_i itself (cf: the w_i enumerates also the RE sets, not
just the dom(phi_i)). Let us call it w_du
So I can translate "x is a computation" by "x belongs to w_du.
But now, I can use the Matiyasevitch-Jones Universal diophantine
relation.
(the unknowns range on the non negative integers (= 0 included)
There are 31 unknowns: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P,
Q, R, S, T, W, Z, U, Y, Al, Ga, Et, Th, La, Ta, Ph,
and two parameters: du itself and x.
So we can translate "x is in w_du", i.e. x is a finite computation, by
du = ((ZUY)^2 + U)^2 + Y (that's just coding)
ELG^2 + Al = (B - xY)Q^2
Qu = B^(5^60)
La + Qu^4 = 1 + LaB^5
Th + 2Z = B^5
L = U + TTh
E = Y + MTh
N = Q^16
R = [G + EQ^3 + LQ^5 + (2(E - ZLa)(1 + xB^5 + G)^4 + LaB^5 + +
LaB^5Q^4)Q^4](N^2 -N)
+ [Q^3 -BL + L + ThLaQ^3 + (B^5 - 2)Q^5] (N^2 - 1)
P = 2W(S^2)(R^2)N^2
(P^2)K^2 - K^2 + 1 = Ta^2
4(c - KSN^2)^2 + Et = K^2
K = R + 1 + HP - H
A = (WN^2 + 1)RSN^2
C = 2R + 1 Ph
D = BW + CA -2C + 4AGa -5Ga
D^2 = (A^2 - 1)C^2 + 1
F^2 = (A^2 - 1)(I^2)C^4 + 1
(D + OF)^2 = ((A + F^2(D^2 - A^2))^2 - 1)(2R + 1 + JC)^2 + 1
So all solutions of this will give the x which are computations.
Hope this helped a bit,
Bruno
Brent
--
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
