Ahora un poco de "off-topic" sobre las cuestiones de implementación real de la función sucesor.
Y bueno, con la computadora imaginaria siempre es todo más fácil. 
Sí, tras postear mi mensaje me dí cuenta que podía haber nombrado la máquina de Turing,
pero no agregué ninguna aclaración, y además no es una máquina real.
Es un mecanismo imaginario, más complicado que lo que se está queriendo representar con eso.
No es tan imaginaria, hay gente que se ha dedicado a construir alguna real (a efectos demostrativos). Mira por ejemplo: https://spectrum.ieee.org/032610-diy-turing-machine
Hola geometracat.
Sí, efectivamente tengo visto que hay gente que ha construido máquinas de Turing de verdad... pero siempre con memoria limitada.
El mismo creador de la máquina dice esto:
The tape in my machine is a 1000’ roll of white 35mm film leader.
A lo mejor habría que agregarle algún mecanismo para que se le pueda agregar más cinta bajo demanda.
En ese caso sí sería una Máquina de Turing real.
Es más fácil (en el sentido de escalable) empalmar un trozo de cinta
que ampliar la RAM o los discos rígidos o los procesadores, o lo que sea que se invente en el futuro para tener más y más almacenamiento, que se vuelve más y más complejo y retorcido.
De hecho, a lo mejor esto que decís de las máquinas de Von Neumann,
pues en cierto modo han desvirtuado mucho las cosas,
en el sentido de que se hace parte del diseño la necesidad de tener cada casillero de memoria
indexado de antemano.
La Máquina de Turing
no indexa las posiciones de memoria.
En la computación antigua, los archivos se almacenaban en cintas,
y yo mismo he programado así, así que no sé de qué me sorprendo.
Pero bueno, esto me hace pensar que, entonces, la manera más adecuada
de simular lo que hace la Máquina de Turing sería usar un archivo de texto
en vez de un tipo de datos entero, como argumento de la función "siguiente".
Esto se haría así, porque un archivo es el resabio de lo que antiguamente se hacía con las cintas: es una estructura de datos de tamaño flexible, de acceso secuencial
(aunque a veces puede accederse en forma no secuencial, no está esto asegurado),
y que puede leerse y reescribirse byte a byte.
Y los estados, en lenguajes como
C,
Fortran,
Pascal,
BASH,
bien pueden ser etiquetas a donde el programa salta con un "
goto",
tras leer un caracter del archivo, y procesarlo con un
switch-case o similar.
Pero bueno, como sea, aunque yo reformule mi programa en
C mediante estas nuevas convenciones, la verdad es que los problemas de acceso o referencia a memoria son los mismos.
Pero hay otras formas de hacer esto. Por ejemplo, podrías ir guardando el número en un disco duro en lugar de en memoria RAM, con lo que tienes muchísima más capacidad de almacenamiento. O podrías usar varios ordenadores en red, de manera que "añadir" más memoria significaría "añadir más ordenadores" que fueran capaces de acceder a más memoria (que es el camino que se emplea para tratar con datos masivos).
En resumen, que las complicaciones son más de carácter técnico que filosófico. No hay ningún problema real en guardar números grandes y calcular el siguiente, más allá de que la arquitectura de los ordenadores es como es, por motivos de versatilidad y de eficiencia. Pero aún con los ordenadores actuales hay muchas soluciones que realmente solo requieren añadir "más memoria".
Cuando estás diciendo que "sólo requieren más memoria", estás asumiendo que ese problema es soslayable, porque no atañe a la cuestión filosófica.
Es que el número de complicaciones crece con el tamaño de los datos.
Puedo almacenar dígitos en un archivo gigante en un disco duro,
pero los datos en un disco duro también se indexan con números enteros.
El tamaño de un archivo se guarda por ahí como un número entero.
Entonces, yo no digo que no sea posible, de hecho en mi post lo dejé en duda,
pero a mí me parece que cuanto más grande sea el número de dígitos,
mayores serán los problemas para almacenarlo,
porque luego hay que hacer referencia a ese "dato".
Si un dato requiere almacenarse en muchos archivos, porque no cabe en uno,
tendré que indicarlo de alguna manera,
haciendo referencia a esos archivos,
y esos archivos tendrán o un nombre o una ubicación,
que si requiero un número aún mucho más grande,
pues los mismos nombres de archivo comenzarán a ser escasos,
y tendré que hacer una referencia indirecta,
almacenando nombres grandes de archivo en otros archivos,
y así sucesivamente.
Yo creo que la solución podría ser pensar en un diseño escalable,
pero que se haga de una manera recursiva,
de modo que se clasifique a los números naturales según cierto grado de complejidad.
La idea sería, tras considerar un número natural de tamaño \(S_n\)
(donde \(S_n\) es una sucesión creciente que cuenta el número de dígitos de un natural),
almacenar una referencia de digamos "orden 0" (espero que se entienda lo que prentedo hacer),
que apunta a uno o más archivos de "orden 1",
cuyos datos apuntan a uno o más archivos de "orden 2",
y así hasta llegar al orden \(n\), que es donde se almacenarían
efectivamente los dígitos del número.
Tan complicado me resulta imaginar números grandes, como complicado es hacer referencia a los lugares en que se almacena la información de ellos al representarlos en un medio de almacenamiento.
Y considero que esa analogía en la complicación es parte ineherente de los números naturales.
Por eso me cuesta tomarme a la ligera que sea lo mismo pensar en un 25 que en un 10324781234781247812349781032497109.
Es más costoso calcular el siguiente de un número grande.
El exceso de costo puede volverlo imposible en la vida real.
¿Y en la mente?
__________________
En cuanto a electrónica digital, algo conozco, pero no tengo cómo hacer eso en casa,
y si tuviera, no es fácil que otros usuarios del foro lo reproduzcan.
Todo bien con las observaciones que me hiciste.
Pero Carlos alentó al público a que programe las funciones en cuestión en su computadora,
y no quería dejar pasar el hecho de que no es todo tan simple como podría uno imaginar.
_________________
En cuanto a dificultad... mmmm. Sí, computar la función siguiente parece lo más fácil de todo. Pero me vuelan unas moscas molestas, que espero que me aclaren, y que indicaré en el siguiente mensaje, para no mezclar tantos asuntos.
