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. 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)?
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 https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
