> On 28 Jun 2018, at 02:16, Brent Meeker <[email protected]> wrote: > > > > On 6/27/2018 2:02 AM, Bruno Marchal wrote: >>> Which is certainly shorter than providing a degree 4 universal Diophantine >>> equation, like below (I can’t resist): >>> >>> (unknowns range on the non negative integers (= 0 included) >>> 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: Nu and X. >>> >>> X is in W_Nu iff phi_Nu(X) stop if and only if >>> >>> >>> >>> I don't quite follow what W_Nu is here. >> >> The domain of the function phi_Nu. Nu is just a natural number, and phi_i is >> an enumeration of all partial computable functions. You can generate it by >> generating all programs (of one variable) in any programming language. >> >> >> >>> >>> I am guessing from the context that this means for a given machine/program >>> Nu, and input X, this equation has a solution IFF Nu halts given X as >>> input, but I am not sure what it means to say X is in W_Nu. >> >> You got it. It means nothing more than the Nu-th program P_Nu (or simply Nu) >> stops on input X. >> It can be proved that the W_i (the domain of the phi_i) enumerates all >> recursively enumerable set. > > You seem to have shifted from the Diophantine equations to an enumerated set > of all partial functions.
I do that all the time indeed. Sometimes I use “universal machinery” for the enumeration of the partial computable functions, or the machine/program/number, that is the phi_i. I don’t use the enumeration of the programs P_i as I identify them with i. And sometimes I use “universal machine” to specifically name one machine, which is universal and can generate (enumerate) all programs. When you have the universal machine, u, you have automatically a machinery: indeed its is given by phi_u(1, x), phi_u(2, x), phi_u(3, x) ….. And of course, when you have a universal machinery, you have a universal machine. If phi_i is a universal machinery, it exists u such that phi_u(x,y) = phi_x(y), by definition of “universal”. For example, a Turing machine is just a finite set of quadruplets with the shape q_i S_j S_k q_r, … But a universal Turing machine will be one finite set of quadruple such that when given two number x and y that universal machine will mimic the nth machine of the Turing universal machinery on the input y. Similarly with the combinators, the game-of-life, the Diophantine equations, etc. > Just to check that I understand the universal Diophantine equation: If I > specify a value of Nu then there is an X for which the equations have a > solution in terms of the 31 unknowns, and the relation Nu -> X instantiates > all recursively enumerable functions (that's the sense in which the equations > are universal)? It is the question "X belongs to W_nu", or "phi_Nu(X) converges" which can be shown to be Turing universal (in a weaker sense that in most of the literature in recursion theory). The two senses are explained in Rogers’ book, but I don’t want to bother your with too much details. Note that the self-referential question "x belongs to W_x” is also Turing universal. If you can solve such question you can enumerate all recursively enumerable sets, and you can compute all partial computable function. And the universal Diophantine equation is such that you can compute “X belongs to W_nu”? You give X and Nu, and search if there are solution in the 31 remaining variable. If there is one, it means that X belongs to W_nu. If you don’t find one, it means that you don’t know, like when you run a non stopping program. By dovetailing on the sequence of the 31 variables, you can guess that a Diophantine equation is a sigma_1 proposition: if there is a solution, you will find it. But by being Turing universal, we know that if there is no solution, you might not been able to prove it. Of course, in some case you can, like you can know that x + 1 = x has no solution. 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] > <mailto:[email protected]>. > To post to this group, send email to [email protected] > <mailto:[email protected]>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- 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 https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
