Christophe HENRY

Ce site ne comporte aucune information d’intérêt, sauf pour celui qui la cherche — Ĉi-retejo ne enhavas informon interesan, krom por iu kiu ĝin serĉas — This website doesn’t have any information of interest, except for who looks for it

Permutation sans variable intermédiaire

09/10/2011 - Commentaires fermés

Dans de nombreux environnements, on ne dispose pas toujours de variables intermédiaires. Il est donc nécessaire de recourir à des subterfuges.

Avec une variable intermédiaire

Soient deux variables a et b qu'il faut permuter. L'opération est classique si on dispose d'une variable intermédiaire X :

X = a
a = b
b = X

En déroulant l'exécution à la main, cela donne :

actionabX
initialisation47
X = a474
a = b774
b = X744

Ce qui requiert 3 étapes.

Sans variable intermédiaire

Il y a un problème avec

a = b
b = a

qui ne marche pas car la valeur de b est simplement copiée dans a.
Alors, peut faire ceci :

a = a + b
b = a - b
a = a - b

Ça marche, mais il y a deux formules différentes : a + b et a - b.
On peut faire plus simple :

a = - a - b
b = - a - b
a = - a - b

Ce qui donne l'exécution suivante :

actionab
initialisation47
a = - a - b-117
a = - a - b-114
a = - a - b74

Il y a le même nombre d'opérations que précédemment, mais l'action est identique pour tous.

Généralisation

Aux entiers

La permutation circulaire se généralise avec un nombre arbitraire de variables. Soit x1, x2, ..., xn les variables sur lesquelles on veut effectuer une permutation circulaire. Pour mettre la valeur de x1 and x2, x2 dans x3, ..., xn dans x1, on applique l'algorithme suivant :

Pour i de 1 à n Faire: xi = - ∑(Xj | j de 1 à n)
x1 = - ∑(Xj;j;1;n)

L'algorithme exploite le fait que le calcul se répète à l'identique pour tous.

Aux booléens

Le symbole ⊻ (XOR) a la même principe que le ∑ car l'opérateur ⊻ possède les propriétés d'associativité et de commutativité.

Pour i de 1 à n Faire: xi = ⊻(Xj | j de 1 à n)
x1 = - ⊻(Xj;j;1;n)

Le fait qu'en informatique les booléens sont utilisés pour stocker les données permet de généraliser la permutation à n'importe quel type de données.

Tags de l'article :

Primes, 26 letters inequality

08/10/2011 - Commentaires fermés

This inequality with 26 letters generates all the primes! But there's a trap. First, not all n-uples of the 26 variables return a prime. Second, there's no way to guess what subset of variable values returns primes.

(k + 2)*(1 − (w*z + h + j − q)^2 − ((g*k + 2*g + k + 1)*(h + j) + h − z)^2 − (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 − f^2)^2 − (2*n + p + q + z − e)^2 − (e^3*(e + 2)*(a + 1)^2 + 1 − o^2)^2 − ((a^2 − 1)*y^2 + 1 − x^2)^2 − (16*r^2*y^4*(a^2 − 1) + 1 − u^2)^2 − (n + l + v − y)^2 − ((a^2 − 1)*l^2 + 1 − m^2)^2 − (a*i + k + 1 − l − i)^2 − (((a + u^2*(u^2 − a))^2 − 1)*(n + 4*d*y)^2 + 1 − (x + c*u)^2)^2 − (p + l*(a − n − 1) + b*(2*a*n + 2*a − n^2 − 2*n − 2) − m)^2 − (q + y*(a − p − 1) + s*(2*a*p + 2*a − p^2 − 2*p − 2) − x)^2 − (z + p*l(a − p) + t(2*a*p − p^2 − 1) − p*m)^2) > 0

Indeed, k + 2 is prime if and only if this equation has a solution in the natural numbers (cf Wikipedia). Yes, it's a detail, but all the variables must be natural numbers ;-)

The question is: did anyone tried to develop this expression?

Yes, using giac :

expand((k + 2)*(1 − (w*z + h + j − q)^2 − ((g*k + 2*g + k + 1)*(h + j) + h − z)^2 − (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 − f^2)^2 − (2*n + p + q + z − e)^2 − (e^3*(e + 2)*(a + 1)^2 + 1 − o^2)^2 − ((a^2 − 1)*y^2 + 1 − x^2)^2 − (16*r^2*y^4*(a^2 − 1) + 1 − u^2)^2 − (n + l + v − y)^2 − ((a^2 − 1)*l^2 + 1 − m^2)^2 − (a*i + k + 1 − l − i)^2 − (((a + u^2*(u^2 − a))^2 − 1)*(n + 4*d*y)^2 + 1 − (x + c*u)^2)^2 − (p + l*(a − n − 1) + b*(2*a*n + 2*a − n^2 − 2*n − 2) − m)^2 − (q + y*(a − p − 1) + s*(2*a*p + 2*a − p^2 − 2*p − 2) − x)^2 − (z + p*l(a − p) + t(2*a*p − p^2 − 1) − p*m)^2))

32*c*d*k*n*u*x*y*(-2*u^2)^2+16*c^2*d*k*n*u^2*y*(-2*u^2)^2+64*c*d^2*k*u*x*y^2*(-2
*u^2)^2+64*c*d*n*u*x*y*(-2*u^2)^2+32*c*d*k*n*u^9*x*y-128*c*d*k*n*u^7*x*y+128*c*d
*k*n*u^5*x*y-256*c*d*k*n*u^3*x*y+96*c*d*k*n*u*x*y-512*d^3*k*n*u^8*y^3*(-2*u^2)^2
+2048*d^3*k*n*u^6*y^3*(-2*u^2)^2-2048*d^3*k*n*u^4*y^3*(-2*u^2)^2+4096*d^3*k*n*u^
2*y^3*(-2*u^2)^2-192*d^2*k*n^2*u^8*y^2*(-2*u^2)^2+768*d^2*k*n^2*u^6*y^2*(-2*u^2)
^2-768*d^2*k*n^2*u^4*y^2*(-2*u^2)^2+1536*d^2*k*n^2*u^2*y^2*(-2*u^2)^2+32*c^2*d^2
*k*u^2*y^2*(-2*u^2)^2+32*c^2*d*n*u^2*y*(-2*u^2)^2+16*c^2*d*k*n*u^10*y-64*c^2*d*k
*n*u^8*y+64*c^2*d*k*n*u^6*y-128*c^2*d*k*n*u^4*y+48*c^2*d*k*n*u^2*y-32*d*k*n^3*u^
8*y*(-2*u^2)^2+128*d*k*n^3*u^6*y*(-2*u^2)^2-128*d*k*n^3*u^4*y*(-2*u^2)^2+256*d*k
*n^3*u^2*y*(-2*u^2)^2+16*d*k*n*x^2*y*(-2*u^2)^2+16*d*k*n*u^8*x^2*y-64*d*k*n*u^6*
x^2*y+64*d*k*n*u^4*x^2*y-128*d*k*n*u^2*x^2*y+128*c*d^2*u*x*y^2*(-2*u^2)^2+64*c*d
^2*k*u^9*x*y^2-256*c*d^2*k*u^7*x*y^2+256*c*d^2*k*u^5*x*y^2-512*c*d^2*k*u^3*x*y^2
+192*c*d^2*k*u*x*y^2+4*c*k*n^2*u*x*(-2*u^2)^2+64*c*d*n*u^9*x*y-256*c*d*n*u^7*x*y
+256*c*d*n*u^5*x*y-512*c*d*n*u^3*x*y+192*c*d*n*u*x*y-512*d^4*k*u^8*y^4*(-2*u^2)^
2+2048*d^4*k*u^6*y^4*(-2*u^2)^2-2048*d^4*k*u^4*y^4*(-2*u^2)^2+4096*d^4*k*u^2*y^4
*(-2*u^2)^2-1024*d^3*n*u^8*y^3*(-2*u^2)^2+4096*d^3*n*u^6*y^3*(-2*u^2)^2-4096*d^3
*n*u^4*y^3*(-2*u^2)^2+8192*d^3*n*u^2*y^3*(-2*u^2)^2-256*d^3*k*n*y^3*(-2*u^2)^4-
1536*d^3*k*n*y^3*(-2*u^2)^2-256*d^3*k*n*u^16*y^3+2048*d^3*k*n*u^14*y^3-6144*d^3*
k*n*u^12*y^3+12288*d^3*k*n*u^10*y^3-22016*d^3*k*n*u^8*y^3+22528*d^3*k*n*u^6*y^3-
22528*d^3*k*n*u^4*y^3+12288*d^3*k*n*u^2*y^3-384*d^2*n^2*u^8*y^2*(-2*u^2)^2+1536*
d^2*n^2*u^6*y^2*(-2*u^2)^2-1536*d^2*n^2*u^4*y^2*(-2*u^2)^2+3072*d^2*n^2*u^2*y^2*
(-2*u^2)^2+32*d^2*k*x^2*y^2*(-2*u^2)^2+32*d^2*k*u^8*x^2*y^2-128*d^2*k*u^6*x^2*y^
2+128*d^2*k*u^4*x^2*y^2-256*d^2*k*u^2*x^2*y^2-96*d^2*k*n^2*y^2*(-2*u^2)^4-576*d^
2*k*n^2*y^2*(-2*u^2)^2-96*d^2*k*n^2*u^16*y^2+768*d^2*k*n^2*u^14*y^2-1280*d^2*k*n
^2*u^12*y^2+4608*d^2*k*n^2*u^10*y^2-8256*d^2*k*n^2*u^8*y^2+8448*d^2*k*n^2*u^6*y^
2-4352*d^2*k*n^2*u^4*y^2+4608*d^2*k*n^2*u^2*y^2+64*c^2*d^2*u^2*y^2*(-2*u^2)^2+32
*c^2*d^2*k*u^10*y^2-128*c^2*d^2*k*u^8*y^2+128*c^2*d^2*k*u^6*y^2-256*c^2*d^2*k*u^
4*y^2+96*c^2*d^2*k*u^2*y^2+2*c^2*k*n^2*u^2*(-2*u^2)^2+32*c^2*d*n*u^10*y-128*c^2*
d*n*u^8*y+128*c^2*d*n*u^6*y-256*c^2*d*n*u^4*y+96*c^2*d*n*u^2*y-64*d*n^3*u^8*y*(-
2*u^2)^2+256*d*n^3*u^6*y*(-2*u^2)^2-256*d*n^3*u^4*y*(-2*u^2)^2+512*d*n^3*u^2*y*(
-2*u^2)^2+32*d*n*x^2*y*(-2*u^2)^2+32*d*n*u^8*x^2*y-128*d*n*u^6*x^2*y+128*d*n*u^4
*x^2*y-256*d*n*u^2*x^2*y-16*d*k*n^3*u^16*y+128*d*k*n^3*u^14*y-384*d*k*n^3*u^12*y
+768*d*k*n^3*u^10*y-1376*d*k*n^3*u^8*y+1408*d*k*n^3*u^6*y-1408*d*k*n^3*u^4*y+768
*d*k*n^3*u^2*y-16*d*k*n^3*y*(-2*u^2)^4-96*d*k*n^3*y*(-2*u^2)^2+48*d*k*n*x^2*y-16
*d*k*n*u^8*y+64*d*k*n*u^6*y-64*d*k*n*u^4*y+128*d*k*n*u^2*y-16*d*k*n*y*(-2*u^2)^2
+8*c*n^2*u*x*(-2*u^2)^2+128*c*d^2*u^9*x*y^2-512*c*d^2*u^7*x*y^2+512*c*d^2*u^5*x*
y^2-1024*c*d^2*u^3*x*y^2+384*c*d^2*u*x*y^2+4*c*k*n^2*u^9*x-16*c*k*n^2*u^7*x+16*c
*k*n^2*u^5*x-32*c*k*n^2*u^3*x+12*c*k*n^2*u*x-2*g^2*h*j*k^3-12*g^2*h*j*k^2-24*g^2
*h*j*k-1024*d^4*u^8*y^4*(-2*u^2)^2+4096*d^4*u^6*y^4*(-2*u^2)^2-4096*d^4*u^4*y^4*
(-2*u^2)^2+8192*d^4*u^2*y^4*(-2*u^2)^2-256*d^4*k*y^4*(-2*u^2)^4-1536*d^4*k*y^4*(
-2*u^2)^2-256*d^4*k*u^16*y^4+2048*d^4*k*u^14*y^4-2048*d^4*k*u^12*y^4+12288*d^4*k
*u^10*y^4-22016*d^4*k*u^8*y^4+22528*d^4*k*u^6*y^4-6144*d^4*k*u^4*y^4+12288*d^4*k
*u^2*y^4-512*d^3*n*y^3*(-2*u^2)^4-3072*d^3*n*y^3*(-2*u^2)^2-512*d^3*n*u^16*y^3+
4096*d^3*n*u^14*y^3-12288*d^3*n*u^12*y^3+24576*d^3*n*u^10*y^3-44032*d^3*n*u^8*y^
3+45056*d^3*n*u^6*y^3-45056*d^3*n*u^4*y^3+24576*d^3*n*u^2*y^3-2304*d^3*k*n*y^3+
64*d^2*x^2*y^2*(-2*u^2)^2+64*d^2*u^8*x^2*y^2-256*d^2*u^6*x^2*y^2+256*d^2*u^4*x^2
*y^2-512*d^2*u^2*x^2*y^2-192*d^2*n^2*y^2*(-2*u^2)^4-1152*d^2*n^2*y^2*(-2*u^2)^2-
192*d^2*n^2*u^16*y^2+1536*d^2*n^2*u^14*y^2-2560*d^2*n^2*u^12*y^2+9216*d^2*n^2*u^
10*y^2-16512*d^2*n^2*u^8*y^2+16896*d^2*n^2*u^6*y^2-8704*d^2*n^2*u^4*y^2+9216*d^2
*n^2*u^2*y^2-32*d^2*k*y^2*(-2*u^2)^2+96*d^2*k*x^2*y^2-32*d^2*k*u^8*y^2+128*d^2*k
*u^6*y^2-128*d^2*k*u^4*y^2+256*d^2*k*u^2*y^2-864*d^2*k*n^2*y^2-4*c^3*k*u^3*x+4*c
^2*n^2*u^2*(-2*u^2)^2+64*c^2*d^2*u^10*y^2-256*c^2*d^2*u^8*y^2+256*c^2*d^2*u^6*y^
2-512*c^2*d^2*u^4*y^2+192*c^2*d^2*u^2*y^2-2*c^2*k*u^2*x^2+2*c^2*k*n^2*u^10-8*c^2
*k*n^2*u^8+8*c^2*k*n^2*u^6-16*c^2*k*n^2*u^4+6*c^2*k*n^2*u^2+96*k*r^2*u^2*y^4-2*k
*p^3*s*y+6*k*p^2*s*y-2*k*p^2*s*x+2*k*p^2*q*s+18*k*o^2*exp(1)*exp(3)-2*k*n^4*u^8*
(-2*u^2)^2+8*k*n^4*u^6*(-2*u^2)^2-8*k*n^4*u^4*(-2*u^2)^2+16*k*n^4*u^2*(-2*u^2)^2
+2*k*n^2*x^2*(-2*u^2)^2+2*k*n^2*u^8*x^2-8*k*n^2*u^6*x^2+8*k*n^2*u^4*x^2-16*k*n^2
*u^2*x^2+2*k*q*w*z-2*k*p*l(-p+2)*t(-p^2+4*p-1)-2*k*p*z*l(-p+2)-2*k*p*x*y+4*k*p*s
*x+2*k*p*q*y-4*k*p*q*s+2*k*m*p^2*l(-p+2)+2*k*m*p*t(-p^2+4*p-1)+2*k*m*p*z+2*k*l*n
*p-2*k*l*m*n-2*j*k*w*z-2*h*k*w*z+2*g*j*k^2*z+8*g*j*k*z+2*g*h*k^2*z+8*g*h*k*z-4*g
*h*j*k^3-22*g*h*j*k^2-40*g*h*j*k-32*d*n^3*u^16*y+256*d*n^3*u^14*y-768*d*n^3*u^12
*y+1536*d*n^3*u^10*y-2752*d*n^3*u^8*y+2816*d*n^3*u^6*y-2816*d*n^3*u^4*y+1536*d*n
^3*u^2*y-32*d*n^3*y*(-2*u^2)^4-192*d*n^3*y*(-2*u^2)^2+96*d*n*x^2*y-32*d*n*u^8*y+
128*d*n*u^6*y-128*d*n*u^4*y+256*d*n*u^2*y-32*d*n*y*(-2*u^2)^2-144*d*k*n^3*y-48*d
*k*n*y+8*c*n^2*u^9*x-32*c*n^2*u^7*x+32*c*n^2*u^5*x-64*c*n^2*u^3*x+24*c*n^2*u*x-4
*c*k*u*x^3+4*c*k*u*x+2*b*k*n^2*p-4*b*k*n*p-2*b*k*m*n^2+4*b*k*m*n-2*b*k*l*n^3+6*b
*k*l*n^2-(-c^2)^2*k*u^4+192*r^2*u^2*y^4-4*p^3*s*y+12*p^2*s*y-4*p^2*s*x+4*p^2*q*s
+36*o^2*exp(1)*exp(3)-4*n^4*u^8*(-2*u^2)^2+16*n^4*u^6*(-2*u^2)^2-16*n^4*u^4*(-2*
u^2)^2+32*n^4*u^2*(-2*u^2)^2+4*n^2*x^2*(-2*u^2)^2+4*n^2*u^8*x^2-16*n^2*u^6*x^2+
16*n^2*u^4*x^2-32*n^2*u^2*x^2-g^2*j^2*k^3-6*g^2*j^2*k^2-12*g^2*j^2*k-g^2*h^2*k^3
-6*g^2*h^2*k^2-12*g^2*h^2*k-16*g^2*h*j+32*f^2*k^5*n^2+64*f^2*k^5*n+224*f^2*k^4*n
^2+448*f^2*k^4*n+608*f^2*k^3*n^2+1216*f^2*k^3*n+800*f^2*k^2*n^2+1600*f^2*k^2*n+
512*f^2*k*n^2+1024*f^2*k*n-512*d^4*y^4*(-2*u^2)^4-3072*d^4*y^4*(-2*u^2)^2-512*d^
4*u^16*y^4+4096*d^4*u^14*y^4-4096*d^4*u^12*y^4+24576*d^4*u^10*y^4-44032*d^4*u^8*
y^4+45056*d^4*u^6*y^4-12288*d^4*u^4*y^4+24576*d^4*u^2*y^4-2304*d^4*k*y^4-4608*d^
3*n*y^3-64*d^2*y^2*(-2*u^2)^2+192*d^2*x^2*y^2-64*d^2*u^8*y^2+256*d^2*u^6*y^2-256
*d^2*u^4*y^2+512*d^2*u^2*y^2-1728*d^2*n^2*y^2-96*d^2*k*y^2-8*c^3*u^3*x-4*c^2*u^2
*x^2+4*c^2*n^2*u^10-16*c^2*n^2*u^8+16*c^2*n^2*u^6-32*c^2*n^2*u^4+12*c^2*n^2*u^2+
2*c^2*k*u^2-b^2*k*(-n^2)^2+4*b^2*k*n^3-8*b^2*k*n+4*q*w*z-4*p*l(-p+2)*t(-p^2+4*p-
1)-4*p*z*l(-p+2)-4*p*x*y+8*p*s*x+4*p*q*y-8*p*q*s+4*m*p^2*l(-p+2)+4*m*p*t(-p^2+4*
p-1)+4*m*p*z+4*l*n*p-4*l*m*n-18*k*exp(1)*exp(3)-324*k*exp(1)*exp(3)^2-81*k*exp(1
)^2*exp(3)^2+k*z^2*(-w^2-1-1)+k*y^2*(-(-p)^2-6-1)+6*k*x^2*y^2+k*s^2*(-(-p^2)^2-4
)-2304*k*r^4*y^8-96*k*r^2*y^4+4*k*p^3*s^2+k*p^2*(-(-m)^2-1-1)-k*p^2*(l(-p+2))^2+
36*k*o^2*exp(3)-k*n^4*(-2*u^2)^4-6*k*n^4*(-2*u^2)^2-k*n^4*u^16+8*k*n^4*u^14-8*k*
n^4*u^12+48*k*n^4*u^10-86*k*n^4*u^8+88*k*n^4*u^6-24*k*n^4*u^4+48*k*n^4*u^2-2*k*n
^2*(-2*u^2)^2+6*k*n^2*x^2-2*k*n^2*u^8+8*k*n^2*u^6-8*k*n^2*u^4+16*k*n^2*u^2-k*l^2
*(-n)^2+6*k*l^2*m^2+2*k*l^2*n-2*k*z*t(-p^2+4*p-1)+2*k*z*exp(1)+2*k*x*y+2*k*v*y-4
*k*s*y+4*k*s*x+2*k*q*exp(1)-2*k*q*z-2*k*q*y+2*k*q*x-4*k*q*s+2*k*p*exp(1)+2*k*p*y
^2-8*k*p*s^2-2*k*p*z-2*k*p*q+4*k*n*exp(1)-4*k*n*z+2*k*n*y-2*k*n*v-4*k*n*q-4*k*n*
p+2*k*m*p+2*k*l*y-2*k*l*v-2*k*l*p-2*k*l*n+2*k*l*m+2*j*k^2*z-4*j*w*z+6*j*k*z+2*j*
k*q+2*h*k^2*z-4*h*w*z+8*h*k*z+2*h*k*q-2*h*j*k^3-10*h*j*k^2-18*h*j*k-2*g*j^2*k^3-
10*g*j^2*k^2-16*g*j^2*k-2*g*h^2*k^3-12*g*h^2*k^2-24*g*h^2*k+8*g*j*z+8*g*h*z-24*g
*h*j-288*d*n^3*y-96*d*n*y-8*c*u*x^3+8*c*u*x+4*b*n^2*p-8*b*n*p-4*b*m*n^2+8*b*m*n-
4*b*l*n^3+12*b*l*n^2-4*b*k*p+4*b*k*m-4*b*k*l-36*exp(1)*exp(3)-648*exp(1)*exp(3)^
2-162*exp(1)^2*exp(3)^2+(-(-f^2)^2)*k-2*(-c^2)^2*u^4+2*z^2*(-w^2-1-1)+2*y^2*(-(-
p)^2-6-1)+12*x^2*y^2+2*s^2*(-(-p^2)^2-4)-4608*r^4*y^8-192*r^2*y^4+8*p^3*s^2+2*p^
2*(-(-m)^2-1-1)-2*p^2*(l(-p+2))^2+72*o^2*exp(3)-2*n^4*(-2*u^2)^4-12*n^4*(-2*u^2)
^2-2*n^4*u^16+16*n^4*u^14-16*n^4*u^12+96*n^4*u^10-172*n^4*u^8+176*n^4*u^6-48*n^4
*u^4+96*n^4*u^2-4*n^2*(-2*u^2)^2+12*n^2*x^2-4*n^2*u^8+16*n^2*u^6-16*n^2*u^4+32*n
^2*u^2-2*l^2*(-n)^2+12*l^2*m^2+4*l^2*n-256*k^9*n^4-1024*k^9*n^3-1536*k^9*n^2-
1024*k^9*n-3072*k^8*n^4-12288*k^8*n^3-18432*k^8*n^2-12288*k^8*n-16128*k^7*n^4-
64512*k^7*n^3-96768*k^7*n^2-64512*k^7*n-48640*k^6*n^4-194560*k^6*n^3-291840*k^6*
n^2-194560*k^6*n-92928*k^5*n^4-371712*k^5*n^3-557600*k^5*n^2-371776*k^5*n-116736
*k^4*n^4-466944*k^4*n^3-700640*k^4*n^2-467392*k^4*n+k^3*(-j^2-h^2-22048-1)-96512
*k^3*n^4-386048*k^3*n^3-579680*k^3*n^2-387264*k^3*n+2*k^2*(-j^2-h^2-22048-1)-
50688*k^2*n^4-202752*k^2*n^3-304928*k^2*n^2-204352*k^2*n+2*k^2*l-2*j^2*k^2-6*j^2
*k-4*h^2*k^2-13*h^2*k-8*g^2*j^2-8*g^2*h^2+128*f^2*n^2+32*f^2*k^5+224*f^2*k^4+608
*f^2*k^3+800*f^2*k^2+256*f^2*n+514*f^2*k-4608*d^4*y^4-192*d^2*y^2+4*c^2*u^2-2*b^
2*(-n^2)^2+8*b^2*n^3-16*b^2*n-4*b^2*k-4*z*t(-p^2+4*p-1)+4*z*exp(1)+4*x*y+4*v*y-8
*s*y+8*s*x+4*q*exp(1)-4*q*z-4*q*y+4*q*x-8*q*s+4*p*exp(1)+4*p*y^2-16*p*s^2-4*p*z-
4*p*q+8*n*exp(1)-8*n*z+4*n*y-4*n*v-8*n*q-8*n*p+4*m*p+4*l*y-4*l*v-4*l*p-4*l*n+4*l
*m-36*k*exp(3)+(-k)*(t(-p^2+4*p-1))^2-324*k*exp(3)^2+(-k)*(-64*d*n*u^2*y)^2+(-k)
*(-32*d*n*u^6*y)^2+(-k)*(-128*d^2*u^2*y^2)^2+(-k)*(-64*d^2*u^6*y^2)^2+(-k)*(-2*c
*u*x)^2+(-k)*(-8*n^2*u^2)^2+(-k)*(-4*n^2*u^6)^2+(-k)*(-exp(1))^2-2*k*(-x^2)^2+(-
k)*(-u^2)^2+(-k)*(-o^2)^2+(-k)*(-m^2)^2+(-k)*(-z)^2+(-k)*(-y)^2+(-k)*(-x)^2+(-k)
*(-q)^2+(-k)*(-m)^2+(-k)*(-l)^2-9*k*y^4+4*k*x^2+(-k)*v^2+2*k*u^2-2*k*q^2+2*k*o^2
-15369*k*n^4-61440*k*n^3-92683*k*n^2+2*k*m^2-9*k*l^4-8*k*l^2-62464*k*n+(6+2*i)*k
*l+4*j*z+4*j*q+8*h*z+4*h*q-12*h*j-8*g*j^2-16*g*h^2-8*b*p+8*b*m-8*b*l-72*exp(3)-2
*(t(-p^2+4*p-1))^2-648*exp(3)^2-2*(-64*d*n*u^2*y)^2-2*(-32*d*n*u^6*y)^2-2*(-128*
d^2*u^2*y^2)^2-2*(-64*d^2*u^6*y^2)^2-2*(-2*c*u*x)^2-2*(-8*n^2*u^2)^2-2*(-4*n^2*u
^6)^2-2*(-exp(1))^2-4*(-x^2)^2-2*(-u^2)^2-2*(-o^2)^2-2*(-m^2)^2-2*(-f^2)^2-2*(-z
)^2-2*(-y)^2-2*(-x)^2-2*(-q)^2-2*(-m)^2-2*(-l)^2-18*y^4+8*x^2-2*v^2+4*u^2-4*q^2+
4*o^2-2066*n^4-8192*n^3-12438*n^2+4*m^2-18*l^4-16*l^2-256*k^9-3072*k^8-16128*k^7
-48640*k^6-92960*k^5-116960*k^4-75072*k^3+(-7394-2*i)*k^2-4*j^2-10*h^2+132*f^2-8
*b^2-8448*n+(4+4*i)*l+(-15881-6*i)*k-2186-4*i

Tags de l'article :

For how many states, there's more than one Googolplex of turing machines?

27/09/2011 - Commentaires fermés

This is a great way to enter the world of great numbers, with a bit of theory and practical sort of innovation...

Main terms

What is a Turing Machine?

A Turing Machine is a very simple computer which was designed by Alain Turing in 1936. A Turing Machine is described by states, each states pointing to other states according to some conditions. You may read a bit more about Turing machines in order to fell all the taste of this article.

What are Googol and Googolplex ?

A Googol is a number represented by 1 followed by 100 zeroes. That is, 10^100. A Googolplex is 10 power Googol - that is, a number represented by 1 followed by a Googol of zeroes : 10^(10^100). Somewhat huge.

What is the Log function ?

The Log function approximatively gives the number of digits of a number. It's the reciprocal function of y = 10^x. So, x = Log(y). This function is important here because of one of its main properties. It turns multiplications into additions. So, the calculations will involve far less huge numbers.

So what?

A resolution

The question is: how many states do I need to be able to build one Googolplex Turing Machines? Winter's cold, brain's hot.

The Turing Machine considered here is the more simple one: two different values and two different directions. Two values and two directions make 4 possibilities. To this, let's add the number of possible jumps: k+1 if there's k states. The +1 is due to the terminal state. So, we've got 4*(k+1) possibilities for a given value. A state having two values (0 or 1), it's (4*(k+1))^2 each state. As there is k different states, we get: (4*(k+1))^(2*k).

The problem is that this expression is obviously over k^k and that the question becomes:

k | (4*(k+1))^(2*k) >= 10^(10^100)

I must admit that I didn't have any clue on how to cleanly solve this. Trying as many values of k as possible is hopeless. Here comes the Log. As a strickly growing function the order between the left part and right part is unchanged by the Log:

k | Log( (4*(k+1))^(2*k) ) >= Log ( 10^(10^100) )
So, k | 2*k * Log( 4*(k+1) ) >= 10^100
So, k | 2*k * (Log(4) + Log(k+1)) >= 10^100

Let's Log again:
k | Log(2) + Log(k) + Log(Log(4) + Log(k+1)) >= 100

Now, it's just about using Log(k) and Log(k+1) against 100. I'm sure that it's feasible, but let's do it by a program.

The program

The program, in the Python language, browse the values using an exponential scale. Once it gets over, then it turns back a try a 10th less scale. And so on until the Log of the Log of the number of possible Turing Machines reaches 100. The formatting disappears there, I replaced tabs by underscores.

# Python
# -*- coding: utf-8 -*-

# For how many states, there's more than one gogolplex of turing machines?

from math import log

def logLogNbTuring(k): return log(2.0*k,10)+log(log(4.0,10)+log(k+1.0,10),10)

# A value of 100 means that we're searching for a number of machines greater than 10^(10^100), more than a gogolplex.
nbTenPowerTen = 100

step = 1
while logLogNbTuring(step) step /= 10
print "log(step,10) set to %i" % log(step,10)

i = 1
belowValue = i
while (step>=1):
_if logLogNbTuring(i)>=nbTenPowerTen:
__i = belowValue
__step /= 10
_belowValue = i
_i+=step

# belowValue contains the last value before the limit, so add 1 to get over the limit
i = belowValue + 1
print "nbTenPowerTen=%i, solution=%i" % (nbTenPowerTen, i)
print "log(solution,10)=%f" % log(i,10)

The result

answer = 50 860 333 466 396 650 825 817 657 241 650 242 602 634 644 785 968 021 580 236 147 821 863 292 723 816 479 721 264 913 714 249 728
I think that because of rounds that this number is not strictly the exact solution. But that's not the point: Log(answer) = 97.70 means that answer almost equals 10^100, a Googol.

A Turing machine with almost one Googol states means one Googolplex possibility of Turing machines.

Tags de l'article :

Permutation sans variable intermédiaire

09/10/2011 - Commentaires fermés

Dans de nombreux environnements, on ne dispose pas toujours de variables intermédiaires. Il est donc nécessaire de recourir à des subterfuges.

Avec une variable intermédiaire

Soient deux variables a et b qu'il faut permuter. L'opération est classique si on dispose d'une variable intermédiaire X :

X = a
a = b
b = X

En déroulant l'exécution à la main, cela donne :

actionabX
initialisation47
X = a474
a = b774
b = X744

Ce qui requiert 3 étapes.

Sans variable intermédiaire

Il y a un problème avec

a = b
b = a

qui ne marche pas car la valeur de b est simplement copiée dans a.
Alors, peut faire ceci :

a = a + b
b = a - b
a = a - b

Ça marche, mais il y a deux formules différentes : a + b et a - b.
On peut faire plus simple :

a = - a - b
b = - a - b
a = - a - b

Ce qui donne l'exécution suivante :

actionab
initialisation47
a = - a - b-117
a = - a - b-114
a = - a - b74

Il y a le même nombre d'opérations que précédemment, mais l'action est identique pour tous.

Généralisation

Aux entiers

La permutation circulaire se généralise avec un nombre arbitraire de variables. Soit x1, x2, ..., xn les variables sur lesquelles on veut effectuer une permutation circulaire. Pour mettre la valeur de x1 and x2, x2 dans x3, ..., xn dans x1, on applique l'algorithme suivant :

Pour i de 1 à n Faire: xi = - ∑(Xj | j de 1 à n)
x1 = - ∑(Xj;j;1;n)

L'algorithme exploite le fait que le calcul se répète à l'identique pour tous.

Aux booléens

Le symbole ⊻ (XOR) a la même principe que le ∑ car l'opérateur ⊻ possède les propriétés d'associativité et de commutativité.

Pour i de 1 à n Faire: xi = ⊻(Xj | j de 1 à n)
x1 = - ⊻(Xj;j;1;n)

Le fait qu'en informatique les booléens sont utilisés pour stocker les données permet de généraliser la permutation à n'importe quel type de données.

Tags de l'article :

Primes, 26 letters inequality

08/10/2011 - Commentaires fermés

This inequality with 26 letters generates all the primes! But there's a trap. First, not all n-uples of the 26 variables return a prime. Second, there's no way to guess what subset of variable values returns primes.

(k + 2)*(1 − (w*z + h + j − q)^2 − ((g*k + 2*g + k + 1)*(h + j) + h − z)^2 − (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 − f^2)^2 − (2*n + p + q + z − e)^2 − (e^3*(e + 2)*(a + 1)^2 + 1 − o^2)^2 − ((a^2 − 1)*y^2 + 1 − x^2)^2 − (16*r^2*y^4*(a^2 − 1) + 1 − u^2)^2 − (n + l + v − y)^2 − ((a^2 − 1)*l^2 + 1 − m^2)^2 − (a*i + k + 1 − l − i)^2 − (((a + u^2*(u^2 − a))^2 − 1)*(n + 4*d*y)^2 + 1 − (x + c*u)^2)^2 − (p + l*(a − n − 1) + b*(2*a*n + 2*a − n^2 − 2*n − 2) − m)^2 − (q + y*(a − p − 1) + s*(2*a*p + 2*a − p^2 − 2*p − 2) − x)^2 − (z + p*l(a − p) + t(2*a*p − p^2 − 1) − p*m)^2) > 0

Indeed, k + 2 is prime if and only if this equation has a solution in the natural numbers (cf Wikipedia). Yes, it's a detail, but all the variables must be natural numbers ;-)

The question is: did anyone tried to develop this expression?

Yes, using giac :

expand((k + 2)*(1 − (w*z + h + j − q)^2 − ((g*k + 2*g + k + 1)*(h + j) + h − z)^2 − (16*(k + 1)^3*(k + 2)*(n + 1)^2 + 1 − f^2)^2 − (2*n + p + q + z − e)^2 − (e^3*(e + 2)*(a + 1)^2 + 1 − o^2)^2 − ((a^2 − 1)*y^2 + 1 − x^2)^2 − (16*r^2*y^4*(a^2 − 1) + 1 − u^2)^2 − (n + l + v − y)^2 − ((a^2 − 1)*l^2 + 1 − m^2)^2 − (a*i + k + 1 − l − i)^2 − (((a + u^2*(u^2 − a))^2 − 1)*(n + 4*d*y)^2 + 1 − (x + c*u)^2)^2 − (p + l*(a − n − 1) + b*(2*a*n + 2*a − n^2 − 2*n − 2) − m)^2 − (q + y*(a − p − 1) + s*(2*a*p + 2*a − p^2 − 2*p − 2) − x)^2 − (z + p*l(a − p) + t(2*a*p − p^2 − 1) − p*m)^2))

32*c*d*k*n*u*x*y*(-2*u^2)^2+16*c^2*d*k*n*u^2*y*(-2*u^2)^2+64*c*d^2*k*u*x*y^2*(-2
*u^2)^2+64*c*d*n*u*x*y*(-2*u^2)^2+32*c*d*k*n*u^9*x*y-128*c*d*k*n*u^7*x*y+128*c*d
*k*n*u^5*x*y-256*c*d*k*n*u^3*x*y+96*c*d*k*n*u*x*y-512*d^3*k*n*u^8*y^3*(-2*u^2)^2
+2048*d^3*k*n*u^6*y^3*(-2*u^2)^2-2048*d^3*k*n*u^4*y^3*(-2*u^2)^2+4096*d^3*k*n*u^
2*y^3*(-2*u^2)^2-192*d^2*k*n^2*u^8*y^2*(-2*u^2)^2+768*d^2*k*n^2*u^6*y^2*(-2*u^2)
^2-768*d^2*k*n^2*u^4*y^2*(-2*u^2)^2+1536*d^2*k*n^2*u^2*y^2*(-2*u^2)^2+32*c^2*d^2
*k*u^2*y^2*(-2*u^2)^2+32*c^2*d*n*u^2*y*(-2*u^2)^2+16*c^2*d*k*n*u^10*y-64*c^2*d*k
*n*u^8*y+64*c^2*d*k*n*u^6*y-128*c^2*d*k*n*u^4*y+48*c^2*d*k*n*u^2*y-32*d*k*n^3*u^
8*y*(-2*u^2)^2+128*d*k*n^3*u^6*y*(-2*u^2)^2-128*d*k*n^3*u^4*y*(-2*u^2)^2+256*d*k
*n^3*u^2*y*(-2*u^2)^2+16*d*k*n*x^2*y*(-2*u^2)^2+16*d*k*n*u^8*x^2*y-64*d*k*n*u^6*
x^2*y+64*d*k*n*u^4*x^2*y-128*d*k*n*u^2*x^2*y+128*c*d^2*u*x*y^2*(-2*u^2)^2+64*c*d
^2*k*u^9*x*y^2-256*c*d^2*k*u^7*x*y^2+256*c*d^2*k*u^5*x*y^2-512*c*d^2*k*u^3*x*y^2
+192*c*d^2*k*u*x*y^2+4*c*k*n^2*u*x*(-2*u^2)^2+64*c*d*n*u^9*x*y-256*c*d*n*u^7*x*y
+256*c*d*n*u^5*x*y-512*c*d*n*u^3*x*y+192*c*d*n*u*x*y-512*d^4*k*u^8*y^4*(-2*u^2)^
2+2048*d^4*k*u^6*y^4*(-2*u^2)^2-2048*d^4*k*u^4*y^4*(-2*u^2)^2+4096*d^4*k*u^2*y^4
*(-2*u^2)^2-1024*d^3*n*u^8*y^3*(-2*u^2)^2+4096*d^3*n*u^6*y^3*(-2*u^2)^2-4096*d^3
*n*u^4*y^3*(-2*u^2)^2+8192*d^3*n*u^2*y^3*(-2*u^2)^2-256*d^3*k*n*y^3*(-2*u^2)^4-
1536*d^3*k*n*y^3*(-2*u^2)^2-256*d^3*k*n*u^16*y^3+2048*d^3*k*n*u^14*y^3-6144*d^3*
k*n*u^12*y^3+12288*d^3*k*n*u^10*y^3-22016*d^3*k*n*u^8*y^3+22528*d^3*k*n*u^6*y^3-
22528*d^3*k*n*u^4*y^3+12288*d^3*k*n*u^2*y^3-384*d^2*n^2*u^8*y^2*(-2*u^2)^2+1536*
d^2*n^2*u^6*y^2*(-2*u^2)^2-1536*d^2*n^2*u^4*y^2*(-2*u^2)^2+3072*d^2*n^2*u^2*y^2*
(-2*u^2)^2+32*d^2*k*x^2*y^2*(-2*u^2)^2+32*d^2*k*u^8*x^2*y^2-128*d^2*k*u^6*x^2*y^
2+128*d^2*k*u^4*x^2*y^2-256*d^2*k*u^2*x^2*y^2-96*d^2*k*n^2*y^2*(-2*u^2)^4-576*d^
2*k*n^2*y^2*(-2*u^2)^2-96*d^2*k*n^2*u^16*y^2+768*d^2*k*n^2*u^14*y^2-1280*d^2*k*n
^2*u^12*y^2+4608*d^2*k*n^2*u^10*y^2-8256*d^2*k*n^2*u^8*y^2+8448*d^2*k*n^2*u^6*y^
2-4352*d^2*k*n^2*u^4*y^2+4608*d^2*k*n^2*u^2*y^2+64*c^2*d^2*u^2*y^2*(-2*u^2)^2+32
*c^2*d^2*k*u^10*y^2-128*c^2*d^2*k*u^8*y^2+128*c^2*d^2*k*u^6*y^2-256*c^2*d^2*k*u^
4*y^2+96*c^2*d^2*k*u^2*y^2+2*c^2*k*n^2*u^2*(-2*u^2)^2+32*c^2*d*n*u^10*y-128*c^2*
d*n*u^8*y+128*c^2*d*n*u^6*y-256*c^2*d*n*u^4*y+96*c^2*d*n*u^2*y-64*d*n^3*u^8*y*(-
2*u^2)^2+256*d*n^3*u^6*y*(-2*u^2)^2-256*d*n^3*u^4*y*(-2*u^2)^2+512*d*n^3*u^2*y*(
-2*u^2)^2+32*d*n*x^2*y*(-2*u^2)^2+32*d*n*u^8*x^2*y-128*d*n*u^6*x^2*y+128*d*n*u^4
*x^2*y-256*d*n*u^2*x^2*y-16*d*k*n^3*u^16*y+128*d*k*n^3*u^14*y-384*d*k*n^3*u^12*y
+768*d*k*n^3*u^10*y-1376*d*k*n^3*u^8*y+1408*d*k*n^3*u^6*y-1408*d*k*n^3*u^4*y+768
*d*k*n^3*u^2*y-16*d*k*n^3*y*(-2*u^2)^4-96*d*k*n^3*y*(-2*u^2)^2+48*d*k*n*x^2*y-16
*d*k*n*u^8*y+64*d*k*n*u^6*y-64*d*k*n*u^4*y+128*d*k*n*u^2*y-16*d*k*n*y*(-2*u^2)^2
+8*c*n^2*u*x*(-2*u^2)^2+128*c*d^2*u^9*x*y^2-512*c*d^2*u^7*x*y^2+512*c*d^2*u^5*x*
y^2-1024*c*d^2*u^3*x*y^2+384*c*d^2*u*x*y^2+4*c*k*n^2*u^9*x-16*c*k*n^2*u^7*x+16*c
*k*n^2*u^5*x-32*c*k*n^2*u^3*x+12*c*k*n^2*u*x-2*g^2*h*j*k^3-12*g^2*h*j*k^2-24*g^2
*h*j*k-1024*d^4*u^8*y^4*(-2*u^2)^2+4096*d^4*u^6*y^4*(-2*u^2)^2-4096*d^4*u^4*y^4*
(-2*u^2)^2+8192*d^4*u^2*y^4*(-2*u^2)^2-256*d^4*k*y^4*(-2*u^2)^4-1536*d^4*k*y^4*(
-2*u^2)^2-256*d^4*k*u^16*y^4+2048*d^4*k*u^14*y^4-2048*d^4*k*u^12*y^4+12288*d^4*k
*u^10*y^4-22016*d^4*k*u^8*y^4+22528*d^4*k*u^6*y^4-6144*d^4*k*u^4*y^4+12288*d^4*k
*u^2*y^4-512*d^3*n*y^3*(-2*u^2)^4-3072*d^3*n*y^3*(-2*u^2)^2-512*d^3*n*u^16*y^3+
4096*d^3*n*u^14*y^3-12288*d^3*n*u^12*y^3+24576*d^3*n*u^10*y^3-44032*d^3*n*u^8*y^
3+45056*d^3*n*u^6*y^3-45056*d^3*n*u^4*y^3+24576*d^3*n*u^2*y^3-2304*d^3*k*n*y^3+
64*d^2*x^2*y^2*(-2*u^2)^2+64*d^2*u^8*x^2*y^2-256*d^2*u^6*x^2*y^2+256*d^2*u^4*x^2
*y^2-512*d^2*u^2*x^2*y^2-192*d^2*n^2*y^2*(-2*u^2)^4-1152*d^2*n^2*y^2*(-2*u^2)^2-
192*d^2*n^2*u^16*y^2+1536*d^2*n^2*u^14*y^2-2560*d^2*n^2*u^12*y^2+9216*d^2*n^2*u^
10*y^2-16512*d^2*n^2*u^8*y^2+16896*d^2*n^2*u^6*y^2-8704*d^2*n^2*u^4*y^2+9216*d^2
*n^2*u^2*y^2-32*d^2*k*y^2*(-2*u^2)^2+96*d^2*k*x^2*y^2-32*d^2*k*u^8*y^2+128*d^2*k
*u^6*y^2-128*d^2*k*u^4*y^2+256*d^2*k*u^2*y^2-864*d^2*k*n^2*y^2-4*c^3*k*u^3*x+4*c
^2*n^2*u^2*(-2*u^2)^2+64*c^2*d^2*u^10*y^2-256*c^2*d^2*u^8*y^2+256*c^2*d^2*u^6*y^
2-512*c^2*d^2*u^4*y^2+192*c^2*d^2*u^2*y^2-2*c^2*k*u^2*x^2+2*c^2*k*n^2*u^10-8*c^2
*k*n^2*u^8+8*c^2*k*n^2*u^6-16*c^2*k*n^2*u^4+6*c^2*k*n^2*u^2+96*k*r^2*u^2*y^4-2*k
*p^3*s*y+6*k*p^2*s*y-2*k*p^2*s*x+2*k*p^2*q*s+18*k*o^2*exp(1)*exp(3)-2*k*n^4*u^8*
(-2*u^2)^2+8*k*n^4*u^6*(-2*u^2)^2-8*k*n^4*u^4*(-2*u^2)^2+16*k*n^4*u^2*(-2*u^2)^2
+2*k*n^2*x^2*(-2*u^2)^2+2*k*n^2*u^8*x^2-8*k*n^2*u^6*x^2+8*k*n^2*u^4*x^2-16*k*n^2
*u^2*x^2+2*k*q*w*z-2*k*p*l(-p+2)*t(-p^2+4*p-1)-2*k*p*z*l(-p+2)-2*k*p*x*y+4*k*p*s
*x+2*k*p*q*y-4*k*p*q*s+2*k*m*p^2*l(-p+2)+2*k*m*p*t(-p^2+4*p-1)+2*k*m*p*z+2*k*l*n
*p-2*k*l*m*n-2*j*k*w*z-2*h*k*w*z+2*g*j*k^2*z+8*g*j*k*z+2*g*h*k^2*z+8*g*h*k*z-4*g
*h*j*k^3-22*g*h*j*k^2-40*g*h*j*k-32*d*n^3*u^16*y+256*d*n^3*u^14*y-768*d*n^3*u^12
*y+1536*d*n^3*u^10*y-2752*d*n^3*u^8*y+2816*d*n^3*u^6*y-2816*d*n^3*u^4*y+1536*d*n
^3*u^2*y-32*d*n^3*y*(-2*u^2)^4-192*d*n^3*y*(-2*u^2)^2+96*d*n*x^2*y-32*d*n*u^8*y+
128*d*n*u^6*y-128*d*n*u^4*y+256*d*n*u^2*y-32*d*n*y*(-2*u^2)^2-144*d*k*n^3*y-48*d
*k*n*y+8*c*n^2*u^9*x-32*c*n^2*u^7*x+32*c*n^2*u^5*x-64*c*n^2*u^3*x+24*c*n^2*u*x-4
*c*k*u*x^3+4*c*k*u*x+2*b*k*n^2*p-4*b*k*n*p-2*b*k*m*n^2+4*b*k*m*n-2*b*k*l*n^3+6*b
*k*l*n^2-(-c^2)^2*k*u^4+192*r^2*u^2*y^4-4*p^3*s*y+12*p^2*s*y-4*p^2*s*x+4*p^2*q*s
+36*o^2*exp(1)*exp(3)-4*n^4*u^8*(-2*u^2)^2+16*n^4*u^6*(-2*u^2)^2-16*n^4*u^4*(-2*
u^2)^2+32*n^4*u^2*(-2*u^2)^2+4*n^2*x^2*(-2*u^2)^2+4*n^2*u^8*x^2-16*n^2*u^6*x^2+
16*n^2*u^4*x^2-32*n^2*u^2*x^2-g^2*j^2*k^3-6*g^2*j^2*k^2-12*g^2*j^2*k-g^2*h^2*k^3
-6*g^2*h^2*k^2-12*g^2*h^2*k-16*g^2*h*j+32*f^2*k^5*n^2+64*f^2*k^5*n+224*f^2*k^4*n
^2+448*f^2*k^4*n+608*f^2*k^3*n^2+1216*f^2*k^3*n+800*f^2*k^2*n^2+1600*f^2*k^2*n+
512*f^2*k*n^2+1024*f^2*k*n-512*d^4*y^4*(-2*u^2)^4-3072*d^4*y^4*(-2*u^2)^2-512*d^
4*u^16*y^4+4096*d^4*u^14*y^4-4096*d^4*u^12*y^4+24576*d^4*u^10*y^4-44032*d^4*u^8*
y^4+45056*d^4*u^6*y^4-12288*d^4*u^4*y^4+24576*d^4*u^2*y^4-2304*d^4*k*y^4-4608*d^
3*n*y^3-64*d^2*y^2*(-2*u^2)^2+192*d^2*x^2*y^2-64*d^2*u^8*y^2+256*d^2*u^6*y^2-256
*d^2*u^4*y^2+512*d^2*u^2*y^2-1728*d^2*n^2*y^2-96*d^2*k*y^2-8*c^3*u^3*x-4*c^2*u^2
*x^2+4*c^2*n^2*u^10-16*c^2*n^2*u^8+16*c^2*n^2*u^6-32*c^2*n^2*u^4+12*c^2*n^2*u^2+
2*c^2*k*u^2-b^2*k*(-n^2)^2+4*b^2*k*n^3-8*b^2*k*n+4*q*w*z-4*p*l(-p+2)*t(-p^2+4*p-
1)-4*p*z*l(-p+2)-4*p*x*y+8*p*s*x+4*p*q*y-8*p*q*s+4*m*p^2*l(-p+2)+4*m*p*t(-p^2+4*
p-1)+4*m*p*z+4*l*n*p-4*l*m*n-18*k*exp(1)*exp(3)-324*k*exp(1)*exp(3)^2-81*k*exp(1
)^2*exp(3)^2+k*z^2*(-w^2-1-1)+k*y^2*(-(-p)^2-6-1)+6*k*x^2*y^2+k*s^2*(-(-p^2)^2-4
)-2304*k*r^4*y^8-96*k*r^2*y^4+4*k*p^3*s^2+k*p^2*(-(-m)^2-1-1)-k*p^2*(l(-p+2))^2+
36*k*o^2*exp(3)-k*n^4*(-2*u^2)^4-6*k*n^4*(-2*u^2)^2-k*n^4*u^16+8*k*n^4*u^14-8*k*
n^4*u^12+48*k*n^4*u^10-86*k*n^4*u^8+88*k*n^4*u^6-24*k*n^4*u^4+48*k*n^4*u^2-2*k*n
^2*(-2*u^2)^2+6*k*n^2*x^2-2*k*n^2*u^8+8*k*n^2*u^6-8*k*n^2*u^4+16*k*n^2*u^2-k*l^2
*(-n)^2+6*k*l^2*m^2+2*k*l^2*n-2*k*z*t(-p^2+4*p-1)+2*k*z*exp(1)+2*k*x*y+2*k*v*y-4
*k*s*y+4*k*s*x+2*k*q*exp(1)-2*k*q*z-2*k*q*y+2*k*q*x-4*k*q*s+2*k*p*exp(1)+2*k*p*y
^2-8*k*p*s^2-2*k*p*z-2*k*p*q+4*k*n*exp(1)-4*k*n*z+2*k*n*y-2*k*n*v-4*k*n*q-4*k*n*
p+2*k*m*p+2*k*l*y-2*k*l*v-2*k*l*p-2*k*l*n+2*k*l*m+2*j*k^2*z-4*j*w*z+6*j*k*z+2*j*
k*q+2*h*k^2*z-4*h*w*z+8*h*k*z+2*h*k*q-2*h*j*k^3-10*h*j*k^2-18*h*j*k-2*g*j^2*k^3-
10*g*j^2*k^2-16*g*j^2*k-2*g*h^2*k^3-12*g*h^2*k^2-24*g*h^2*k+8*g*j*z+8*g*h*z-24*g
*h*j-288*d*n^3*y-96*d*n*y-8*c*u*x^3+8*c*u*x+4*b*n^2*p-8*b*n*p-4*b*m*n^2+8*b*m*n-
4*b*l*n^3+12*b*l*n^2-4*b*k*p+4*b*k*m-4*b*k*l-36*exp(1)*exp(3)-648*exp(1)*exp(3)^
2-162*exp(1)^2*exp(3)^2+(-(-f^2)^2)*k-2*(-c^2)^2*u^4+2*z^2*(-w^2-1-1)+2*y^2*(-(-
p)^2-6-1)+12*x^2*y^2+2*s^2*(-(-p^2)^2-4)-4608*r^4*y^8-192*r^2*y^4+8*p^3*s^2+2*p^
2*(-(-m)^2-1-1)-2*p^2*(l(-p+2))^2+72*o^2*exp(3)-2*n^4*(-2*u^2)^4-12*n^4*(-2*u^2)
^2-2*n^4*u^16+16*n^4*u^14-16*n^4*u^12+96*n^4*u^10-172*n^4*u^8+176*n^4*u^6-48*n^4
*u^4+96*n^4*u^2-4*n^2*(-2*u^2)^2+12*n^2*x^2-4*n^2*u^8+16*n^2*u^6-16*n^2*u^4+32*n
^2*u^2-2*l^2*(-n)^2+12*l^2*m^2+4*l^2*n-256*k^9*n^4-1024*k^9*n^3-1536*k^9*n^2-
1024*k^9*n-3072*k^8*n^4-12288*k^8*n^3-18432*k^8*n^2-12288*k^8*n-16128*k^7*n^4-
64512*k^7*n^3-96768*k^7*n^2-64512*k^7*n-48640*k^6*n^4-194560*k^6*n^3-291840*k^6*
n^2-194560*k^6*n-92928*k^5*n^4-371712*k^5*n^3-557600*k^5*n^2-371776*k^5*n-116736
*k^4*n^4-466944*k^4*n^3-700640*k^4*n^2-467392*k^4*n+k^3*(-j^2-h^2-22048-1)-96512
*k^3*n^4-386048*k^3*n^3-579680*k^3*n^2-387264*k^3*n+2*k^2*(-j^2-h^2-22048-1)-
50688*k^2*n^4-202752*k^2*n^3-304928*k^2*n^2-204352*k^2*n+2*k^2*l-2*j^2*k^2-6*j^2
*k-4*h^2*k^2-13*h^2*k-8*g^2*j^2-8*g^2*h^2+128*f^2*n^2+32*f^2*k^5+224*f^2*k^4+608
*f^2*k^3+800*f^2*k^2+256*f^2*n+514*f^2*k-4608*d^4*y^4-192*d^2*y^2+4*c^2*u^2-2*b^
2*(-n^2)^2+8*b^2*n^3-16*b^2*n-4*b^2*k-4*z*t(-p^2+4*p-1)+4*z*exp(1)+4*x*y+4*v*y-8
*s*y+8*s*x+4*q*exp(1)-4*q*z-4*q*y+4*q*x-8*q*s+4*p*exp(1)+4*p*y^2-16*p*s^2-4*p*z-
4*p*q+8*n*exp(1)-8*n*z+4*n*y-4*n*v-8*n*q-8*n*p+4*m*p+4*l*y-4*l*v-4*l*p-4*l*n+4*l
*m-36*k*exp(3)+(-k)*(t(-p^2+4*p-1))^2-324*k*exp(3)^2+(-k)*(-64*d*n*u^2*y)^2+(-k)
*(-32*d*n*u^6*y)^2+(-k)*(-128*d^2*u^2*y^2)^2+(-k)*(-64*d^2*u^6*y^2)^2+(-k)*(-2*c
*u*x)^2+(-k)*(-8*n^2*u^2)^2+(-k)*(-4*n^2*u^6)^2+(-k)*(-exp(1))^2-2*k*(-x^2)^2+(-
k)*(-u^2)^2+(-k)*(-o^2)^2+(-k)*(-m^2)^2+(-k)*(-z)^2+(-k)*(-y)^2+(-k)*(-x)^2+(-k)
*(-q)^2+(-k)*(-m)^2+(-k)*(-l)^2-9*k*y^4+4*k*x^2+(-k)*v^2+2*k*u^2-2*k*q^2+2*k*o^2
-15369*k*n^4-61440*k*n^3-92683*k*n^2+2*k*m^2-9*k*l^4-8*k*l^2-62464*k*n+(6+2*i)*k
*l+4*j*z+4*j*q+8*h*z+4*h*q-12*h*j-8*g*j^2-16*g*h^2-8*b*p+8*b*m-8*b*l-72*exp(3)-2
*(t(-p^2+4*p-1))^2-648*exp(3)^2-2*(-64*d*n*u^2*y)^2-2*(-32*d*n*u^6*y)^2-2*(-128*
d^2*u^2*y^2)^2-2*(-64*d^2*u^6*y^2)^2-2*(-2*c*u*x)^2-2*(-8*n^2*u^2)^2-2*(-4*n^2*u
^6)^2-2*(-exp(1))^2-4*(-x^2)^2-2*(-u^2)^2-2*(-o^2)^2-2*(-m^2)^2-2*(-f^2)^2-2*(-z
)^2-2*(-y)^2-2*(-x)^2-2*(-q)^2-2*(-m)^2-2*(-l)^2-18*y^4+8*x^2-2*v^2+4*u^2-4*q^2+
4*o^2-2066*n^4-8192*n^3-12438*n^2+4*m^2-18*l^4-16*l^2-256*k^9-3072*k^8-16128*k^7
-48640*k^6-92960*k^5-116960*k^4-75072*k^3+(-7394-2*i)*k^2-4*j^2-10*h^2+132*f^2-8
*b^2-8448*n+(4+4*i)*l+(-15881-6*i)*k-2186-4*i

Tags de l'article :

For how many states, there's more than one Googolplex of turing machines?

27/09/2011 - Commentaires fermés

This is a great way to enter the world of great numbers, with a bit of theory and practical sort of innovation...

Main terms

What is a Turing Machine?

A Turing Machine is a very simple computer which was designed by Alain Turing in 1936. A Turing Machine is described by states, each states pointing to other states according to some conditions. You may read a bit more about Turing machines in order to fell all the taste of this article.

What are Googol and Googolplex ?

A Googol is a number represented by 1 followed by 100 zeroes. That is, 10^100. A Googolplex is 10 power Googol - that is, a number represented by 1 followed by a Googol of zeroes : 10^(10^100). Somewhat huge.

What is the Log function ?

The Log function approximatively gives the number of digits of a number. It's the reciprocal function of y = 10^x. So, x = Log(y). This function is important here because of one of its main properties. It turns multiplications into additions. So, the calculations will involve far less huge numbers.

So what?

A resolution

The question is: how many states do I need to be able to build one Googolplex Turing Machines? Winter's cold, brain's hot.

The Turing Machine considered here is the more simple one: two different values and two different directions. Two values and two directions make 4 possibilities. To this, let's add the number of possible jumps: k+1 if there's k states. The +1 is due to the terminal state. So, we've got 4*(k+1) possibilities for a given value. A state having two values (0 or 1), it's (4*(k+1))^2 each state. As there is k different states, we get: (4*(k+1))^(2*k).

The problem is that this expression is obviously over k^k and that the question becomes:

k | (4*(k+1))^(2*k) >= 10^(10^100)

I must admit that I didn't have any clue on how to cleanly solve this. Trying as many values of k as possible is hopeless. Here comes the Log. As a strickly growing function the order between the left part and right part is unchanged by the Log:

k | Log( (4*(k+1))^(2*k) ) >= Log ( 10^(10^100) )
So, k | 2*k * Log( 4*(k+1) ) >= 10^100
So, k | 2*k * (Log(4) + Log(k+1)) >= 10^100

Let's Log again:
k | Log(2) + Log(k) + Log(Log(4) + Log(k+1)) >= 100

Now, it's just about using Log(k) and Log(k+1) against 100. I'm sure that it's feasible, but let's do it by a program.

The program

The program, in the Python language, browse the values using an exponential scale. Once it gets over, then it turns back a try a 10th less scale. And so on until the Log of the Log of the number of possible Turing Machines reaches 100. The formatting disappears there, I replaced tabs by underscores.

# Python
# -*- coding: utf-8 -*-

# For how many states, there's more than one gogolplex of turing machines?

from math import log

def logLogNbTuring(k): return log(2.0*k,10)+log(log(4.0,10)+log(k+1.0,10),10)

# A value of 100 means that we're searching for a number of machines greater than 10^(10^100), more than a gogolplex.
nbTenPowerTen = 100

step = 1
while logLogNbTuring(step) step /= 10
print "log(step,10) set to %i" % log(step,10)

i = 1
belowValue = i
while (step>=1):
_if logLogNbTuring(i)>=nbTenPowerTen:
__i = belowValue
__step /= 10
_belowValue = i
_i+=step

# belowValue contains the last value before the limit, so add 1 to get over the limit
i = belowValue + 1
print "nbTenPowerTen=%i, solution=%i" % (nbTenPowerTen, i)
print "log(solution,10)=%f" % log(i,10)

The result

answer = 50 860 333 466 396 650 825 817 657 241 650 242 602 634 644 785 968 021 580 236 147 821 863 292 723 816 479 721 264 913 714 249 728
I think that because of rounds that this number is not strictly the exact solution. But that's not the point: Log(answer) = 97.70 means that answer almost equals 10^100, a Googol.

A Turing machine with almost one Googol states means one Googolplex possibility of Turing machines.

Tags de l'article :