Funcion de Ackermann
Funcion de Ackermann
La funcion consiste en lo siguiente :
int ackerman(int m,int n){
if(m==0){
return n+1;
}else{
if(n==0 && m>0){
return ackerman(m-1 , 1);
}else{
return ackerman(m-1, ackerman ( m , n-1 ));
}
}
}
Suponiendo que entren 2 valores , 2 y 1 :
Esta funcion crece demasiado rapido haciendo la funcion A(4,2) el da como resultado un numero de 19 729 digitos con este crecimiento tan alto la funcion demuestra ser computable pero crece mas rapido que cualquier otra funcion recursiva primitiva, por lo tanto esta no es considerada una.
Para dar una idea de los resultados que daria con otros valores.
La funcion de Ackermann, suele ser utilizada para comparar compiladores y su habilidad de recursion.
La funcion de Ackermann es un ejemplo de que aun habiendo funciones computables, sus resultado es incierto Se dice que la expresion (4,3) en la funcion Ackermann no cabe en el universo fisico, es increible la capacidad de esta funcion al crear cifras inimaginables por la persona e incluso en procesadores modernos, que el tiempo que llevaria procesar dicha funcion si el programa hubiese comenzado en el principio del universo, aun hoy el programa todavia no encontraria respuesta. Pero por que no tengamos aun respuesta no quiere decir que no sea computable.
fuentes :
http://www.esacademic.com/dic.nsf/eswiki/508398
http://www.ugr.es/~eaznar/funcion_ackermann.htm
https://www.youtube.com/watch?v=i7sm9dzFtEI
La
funcion de Ackermann es una funcion que toma como entrada 2 numeros
naturales y devuelve 1 numero natural, es el ejemplo mas simple de una
funcion total (una funcion en la cual se definen todos los posibles
valores) computable, pero que no es una funcion recursiva primitiva.
Esta funcion desmiente el dicho que toda funcion computable puede ser es
recursiva primitiva.
Las funciones recursivas primitivas son funciones que coinciden con los programas que utilizan for.
Las funciones recursivas primitivas son funciones que coinciden con los programas que utilizan for.
La funcion consiste en lo siguiente :
if(m==0){
return n+1;
}else{
if(n==0 && m>0){
return ackerman(m-1 , 1);
}else{
return ackerman(m-1, ackerman ( m , n-1 ));
}
}
}
Suponiendo que entren 2 valores , 2 y 1 :
A (2,1) = (A ( 1, A( 2, 0)));
A(2,1) = (A (1, A ( A ( 1 , 1)));
A(2,1) = ( A (1, A (A ( A ( 0, 1))));
A(2,1) = (A (1, A ( A ( 0, 2)));
A(2,1) = (A (1, A ( 0, 3)));
A(2,1) = (A (1, 4));
A(2,1) = (0, 5);
A(2,1)= 5Esta funcion crece demasiado rapido haciendo la funcion A(4,2) el da como resultado un numero de 19 729 digitos con este crecimiento tan alto la funcion demuestra ser computable pero crece mas rapido que cualquier otra funcion recursiva primitiva, por lo tanto esta no es considerada una.
Para dar una idea de los resultados que daria con otros valores.
La funcion de Ackermann, suele ser utilizada para comparar compiladores y su habilidad de recursion.
La funcion de Ackermann es un ejemplo de que aun habiendo funciones computables, sus resultado es incierto Se dice que la expresion (4,3) en la funcion Ackermann no cabe en el universo fisico, es increible la capacidad de esta funcion al crear cifras inimaginables por la persona e incluso en procesadores modernos, que el tiempo que llevaria procesar dicha funcion si el programa hubiese comenzado en el principio del universo, aun hoy el programa todavia no encontraria respuesta. Pero por que no tengamos aun respuesta no quiere decir que no sea computable.
fuentes :
http://www.esacademic.com/dic.nsf/eswiki/508398
http://www.ugr.es/~eaznar/funcion_ackermann.htm
https://www.youtube.com/watch?v=i7sm9dzFtEI
Comentarios
Publicar un comentario