¿Puede un programa tener una salida infinita sin repetición sin quedarse sin memoria?

Depende de lo que quieras decir con no repetir.

Si todo lo que busca no es un patrón discernible en la salida, puede imprimir repetidamente rand () o como otros autores sugirieron [math] \ pi [/ math] o [math] e. [/ Math] Sin embargo, todas las subsecuencias posibles se repite infinitamente a menudo en estos tres casos, por lo que ciertamente no están libres de repeticiones.

Si está tratando de imponer absolutamente ninguna repetición en la salida, entonces esto no es posible. Primero, el alfabeto en sí es finito (por ejemplo, compuesto de caracteres de 256 bits) y tendrá que repetir las letras. Además, hay n ^ k cadenas distintas de longitud k sobre un alfabeto de tamaño n. Entonces, según el principio del casillero, cualquier cadena de longitud n * (n ^ k + 1) debe tener al menos dos copias de una cadena de longitud k.

Para hacer las cosas interesantes asumiremos que la salida puede estar delimitada por un carácter especial (por ejemplo, _) y exigiremos que las cadenas entre los delimitadores sean distintas.

No puede producir infinitas cadenas distintas en una máquina con memoria limitada.

Para ver por qué considerar todos los estados posibles en los que podría estar la máquina. El espacio de estado es enorme – 2 ^ (tamaño de RAM en bits + tamaño de registros en bits) – pero aún finito. Ahora dibuje un borde de cada estado a un estado subsiguiente en función de lo que haría el hardware (por ejemplo, actualizar el puntero de código y posiblemente un valor de memoria de pila o montón). Esta construcción es similar a un DFA, excepto que todas las transiciones son todas epsilon-transiciones (no leen ninguna entrada). Además, hay exactamente un borde de cada nodo.

Ahora considere todos los nodos que generan _. Hay un número finito de tales nodos pero un número infinito de _ en la salida, por lo tanto, uno de estos estados debe ingresarse un número infinito de veces. Además, hay un número finito de ciclos en el gráfico que incluye ese nodo, por lo tanto, al menos uno de los ciclos debe ingresarse más de una vez. Por lo tanto, el programa tiene salida repetitiva.

Es posible extender este ejemplo usando entradas finitas modelando esa entrada en el espacio de estado. Sin embargo, la entrada infinita podría dar como resultado que la máquina pueda producir cadenas distintas. Por ejemplo, si la entrada en sí contenía solo cadenas distintas, el programa simplemente podría copiar la entrada a la salida. No todas las cadenas podrían hacer esto, por ejemplo, una cadena de todos los 0 no agregará nada útil a la construcción anterior.

El ejemplo también se puede ampliar con el uso de un generador de números aleatorios puros incorporando cada salida posible del RNG en el espacio de estado. Esto puede conducir a una cadena que no tiene repeticiones (por ejemplo, generar 0, 1 o _ aleatoriamente podría conducir a la salida a continuación), pero cualquier salida de ese tipo tendría probabilidad de llegar a cero, ya que requeriría rutas arbitrariamente largas no repetidas a través del gráfico de estado .

Si la salida infinita admite búsqueda y reescritura, entonces tiene una máquina Turing completa y puede emitir valores distintos que no se repiten.

Aquí hay un algoritmo que supera n unos (1, 11, 111, 1111, etc.). Lo hace escribiendo los 1 como 0 inicialmente, luego los convierte a 1 individualmente mientras escribe 0 para el siguiente número.

1. Inicialice la cinta a 0_. (_ es el delimitador de salida).
2. Escanear a la izquierda hasta el primer _.
3. Siga escaneando a la izquierda hasta encontrar un 0.

1. Si se encuentra un 0, reemplácelo con 1, luego escanee hasta el final de la salida y agregue un 0.
2. Si no se encuentra 0, escanee hasta el final de la salida y agregue 0_

Así es como se ve la salida.

• 0_ – Estado inicial de la cinta.
• 1_0: escanee a la izquierda de _ y reemplace un 0 con un 1, luego escanee a la derecha y agregue un 0.
• 1_00_ – No quedan ceros de _. Escanee a la derecha y agregue un 0_.
• 1_10_0: escanee a la izquierda de _ y reemplace un 0 con un 1, luego escanee a la derecha y agregue un 0.
• 1_11_00 – Escanee a la izquierda de _ y reemplace un 0 con un 1, luego escanee a la derecha y agregue un 0.
• 1_11_000_ – No quedan ceros de _. Escanee a la derecha y agregue un 0_.

Si la salida es escaneable pero no se puede modificar, entonces el problema es un poco más complicado. Es posible que pueda evitar copiar todo el contenido de salida durante cada modificación, pero esto probablemente resulte en alguna repetición. El uso inteligente de delimitadores para representar cada actualización de estado de manera distinta podría solucionar el problema.

No. Como Alon Amit y otros han señalado, una computadora tiene un número finito de estados. Cuente todos los registros, memoria y contadores. Si esos son todos almacenes de bits, cuente el número de bits y tome 2 a la potencia del número de bits, que es un número realmente grande pero finito. Esas son todas las posibilidades de dónde podría estar la computadora al ejecutar su programa. Dado que el número de estados es finito, eventualmente tendrá que repetirse (si el universo dura tanto, lo cual no es así). Si repite un estado, repetirá la salida.

Algunos han comentado que si el programa usa la función rand (), podría no repetirse. Solo hay tantas salidas de la función rand (), por lo que habrá un estado que se repite con la misma salida de la función rand (). Es posible usar una función rand () que no sea completamente aleatoria y que no repita indefinidamente su mismo ciclo, por lo que es posible que tenga una salida que nunca se repita.

Pero, si permite rand () en el programa, tiene una entrada para el programa y no es justo decir que su programa tiene una salida infinita sin repetición si requiere una entrada infinita sin repetición. Si eso fuera permitido, le doy un programa de una línea que nunca se queda sin memoria y tiene una salida infinita no repetida:

para (;;){

printf (cualquiera que sea el mono en el teclado que acaba de escribir);

}

Ahora, para * verificar * si el programa nunca se repite, necesitaría una memoria infinita.

Creo que puedo resumir las partes más importantes de las respuestas de todos aquí, además de agregar algunas cosas …

Definición de términos

Primero, seamos claros acerca de la terminología. Al no repetir la salida, supongo que NO sucederá lo siguiente: después de imprimir los dígitos X, la computadora comienza a reimprimir el tamaño de la cadena de dígitos X y se repite. Siempre. Esto, por cierto, es el comportamiento de las expansiones decimales para todos los números racionales. Una cadena de dígitos “no repetitivos”, supongo, sería simplemente una serie de dígitos en los que esto nunca sucede.

Primer intento: sin entrada externa

Como muchos han dicho, la respuesta corta es “no”, porque la computadora es una máquina de estados finitos. El problema es esencialmente el de escribir un generador de números aleatorios (RNG), y los diseñadores de RNG toman este problema extremadamente en serio. El problema es que después de escribir X dígitos … a pesar de que X puede ser un número muy grande … el “objeto” de números aleatorios vuelve a su estado inicial y, después de eso, la salida RNG es completamente predecible. Esto es cierto incluso si el estado aleatorio usa todas las memorias en la computadora.

Segundo intento: reloj del sistema como entrada

El procedimiento típico en el uso de RNG es bastante adecuado para la gran mayoría de los propósitos prácticos, como los programas de juegos: use el reloj del sistema para seleccionar un lugar de inicio aleatorio dentro de la secuencia de X estados aleatorios. Es posible que un programa de juego solo necesite hacer eso una vez durante una ejecución del juego. Podemos hacerlo un poco mejor aquí. Podríamos, por ejemplo, tomar periódicamente nuevas entradas del reloj del sistema y seguir comenzando en diferentes lugares dentro de la secuencia repetida de dígitos X.

Incluso eso no es perfecto. Si leemos periódicamente el reloj del sistema, digamos con precisión cada 4.5 segundos, en realidad estamos produciendo un comportamiento no aleatorio, porque el reloj se incrementará de manera predecible. Un “cracker” RNG suficientemente potente podría detectar el patrón resultante. Sin embargo, incluso este comportamiento simple, leer periódicamente el reloj del sistema y comenzar en nuevos lugares en la secuencia, aumenta la longitud efectiva de X en muchos órdenes de magnitud, porque pasará mucho más tiempo antes de que la computadora alcance un estado completamente idéntico al algún estado inicial

Tercer intento: entradas externas

La única solución verdadera, como algunas otras respuestas han aludido, es obtener periódicamente una entrada de una fuente externa verdaderamente aleatoria; Los eventos en el universo físico ofrecen una fuente potencialmente rica y, según muchos físicos, pueden ser verdaderamente aleatorios. Por ejemplo, todos los días más o menos … después de producir muchos billones de dígitos usando las técnicas anteriores … podría leer el último precio de cierre del Promedio Industrial Dow Jones (DJIA), y usar los últimos dígitos para ingresar una nueva variable aleatoria en el producción de dígitos. Por supuesto, no habrá nuevos DJIA los fines de semana y días festivos, pero ese problema se puede resolver utilizando otros precios de acciones según sea necesario. Pero incluso esta solución no es perfecta en lo que respecta al RNG ideal.

Cuarto intento: aleatorizar el aleatorizador

Un defecto de la tercera solución es que pasarías un día entero con una secuencia que en teoría podría ser “descifrada” por un analizador de RNG suficientemente potente. Probablemente es teóricamente imposible obtener un RNG perfecto sin tomar una entrada aleatoria desde el exterior durante la producción de cada dígito, lo que hace que la computadora parezca superflua. Pero una muy buena aproximación sería esta: use una fuente aleatoria para determinar con qué frecuencia para obtener una nueva entrada de número aleatorio en su generador, y luego otra fuente aleatoria para obtener esa variable siempre cambiante.

Y hay una advertencia: si estás produciendo muchos dígitos por segundo, ¡debes hacerlo rápido! La solución puede estar en la construcción de un aleatorizador de mecánica cuántica que pueda proporcionar un verdadero número aleatorio a una velocidad súper alta.

Sí tu puedes. Todas las personas que dicen: “No puede”, no han escuchado la pregunta exacta. No es “puede un programa COMPUTAR una salida infinita no repetitiva”. Entonces, si tiene una computadora y un sensor ruidoso conectado, simplemente puede emitir el ruido. Suponiendo que los estados cuánticos de nuestro universo sean lo suficientemente “infinitos” para usted, la salida será infinitamente aleatoria.

Pero si se te ocurre esa mierda teórica de que los estados dentro de una computadora no son infinitos, los estados del universo tampoco lo son. Entonces, el infinito matemático no es real de todos modos y algo realmente infinito no existe en este universo y tampoco puede ser producido por una computadora.

Además de esto, surge la pregunta: ¿puede una computadora generar una secuencia pseudoaleatoria de números aleatorios que demore más en salir hasta que se repita de lo que existirá el átomo promedio del que está construido? Sí. Toda computadora moderna tiene esta capacidad.

Por lo tanto, esta pregunta no es exactamente sobre las computadoras en sí y no hay información sobre las capacidades de las computadoras o no, pero esta pregunta es una declaración sobre algo no real como “infinito”.

No hay nada real e infinito. Por lo que sé.

Y cada declaración sobre el infinito y la realidad es solo académica y no tiene valor real para ninguna aplicación práctica. No es que la idea de infinito no tenga valor, pero simplemente no hay infinito real en el universo.

Entonces, para cada aspecto práctico de su pregunta, la respuesta es: SÍ

Para cada aspecto teórico de su pregunta, es: NO, porque es cierto para todo en el universo y también para las computadoras.

La computadora moderna más pequeña que se me ocurre es la ATTiny11, que no tiene RAM sino 32 registros de 8 bits. Eso es de 256 bits. Además de eso, tiene 64 bytes de memoria flash EEprom. Entonces, después de contar los 256 bits de todos los 0x00 a todos los 0xFF, aumenta los 64 bytes en 1 y así sucesivamente. Esa es una longitud de 768 bits y 2 ^ 768 para contar eso, por lo que no se repite hasta que el universo termine. Puede implementar un pequeño algoritmo bithift-feedback-pseudo-random o algo así. Pero esta es realmente la computadora más pequeña con la que he trabajado. E incluso esa cosa puede generar números (pseudo-) aleatorios hasta que el universo termine.

No lo hace en un universo teórico, ¿y qué? ¿Ese chip existirá por unos 50? ¿100 años? Tops Y hasta entonces ni siquiera habrá contado sus registros. Será necesario durante más de 1E63 años, si el programa cuenta con cada ciclo de reloj. Sin siquiera tocar la EEPROM. ¿Y nuestro universo existe desde 13.7E9 años? Sí claro.

Supongo que si te queda un poco de sentido práctico, la respuesta es SÍ.

Lo que ocurre con esta respuesta “NO” es que es una especie de retórica. Siempre existe esta espada Damokles sobre esta pregunta: “¿pueden pensar las computadoras?” Y la humanidad siempre trata de definir los límites de las máquinas para superar este límite y afirmar que puede hacer cosas que una máquina no puede hacer. Entonces, cuando miras los 38 trucos retóricos de Schopenhauers (El arte de tener razón) puedes ver que existe este truco retórico para generalizar una pregunta y dar una respuesta que se adapte a tus necesidades.

Y esta generalización de algo que es cierto para todo en la universidad, que de hecho no es infinito porque nada es infinito, poner explícitamente en la computadora para reclamar sus ‘límites’, que en un nivel abstracto son verdaderos, pero no prácticos nivel.

La respuesta ‘NO’ implica que una computadora no puede generar flujos infinitos de números, de modo que cuando la máquina ni siquiera puede contar correctamente, esa cosa nunca podrá hacer XYZ. En este caso, ‘pensar’ o ser ‘inteligente’, sea lo que sea que pensemos que es la inteligencia. Entonces, me opongo firmemente a esta respuesta ligeramente retórica, incluso si es teóricamente correcta. Pero debido a que esto es tan general, es cierto para todo y con eso se convierte en Mu.

Mu como la respuesta a una pregunta mal formulada que no puede producir una respuesta útil.

Y esta es la razón por la que rechazo el NO. No acepto este ‘límite’ que no es un límite real en absoluto. Ese es el producto de una pregunta mal formulada y la pregunta por sí sola es algo retórico, es un recipiente para poner límites a algo donde no hay límites reales. Por fin no hay límites, eso no es cierto para todo lo demás en el universo también.

Tenemos 30 años de luz de invierno de IA detrás de nosotros. Y esta pregunta fue una de las razones por las que perdimos tanto potencial y tantos años de ciencia en este campo. Y tenemos que dejar de hacer preguntas retóricas, porque tememos a la máquina. No hay futuro para este planeta sin nosotros enseñando procesos cognitivos a las máquinas. Ningún ser humano puede coordinar la sociedad moderna, ninguna sociedad humana coordinada, simplemente nada humano puede hacer frente a los datos masivos que enfrentamos todos los días.

Entonces nuestra esperanza es que los 30 años perdidos no sean la perdición de nuestro tiempo. Que la arrogancia e ignorancia de esos 30 años no fueron demasiado largas y ya es demasiado tarde para nosotros. Para construirlos. Y lo primero que tenemos que hacer es dejar de hacer preguntas teóricas y retóricas que surgen del miedo.

Esta respuesta puede ir un poco más allá del rango previsto de esta pregunta, pero solo veo el campo más amplio y las implicaciones. Y son inquietantes.

En todos los aspectos prácticos, las máquinas (computadoras) pueden hacer todo lo que los humanos podemos hacer. Sin embargo, están bajo los mismos límites, bajo los cuales está todo lo que hay en este universo. Y tampoco tienen vida ilimitada. Las computadoras mueren eventualmente, o terminan rotas, si tomas la palabra “morir” más estrecha para “no vivo más”. Por lo general, más rápido que nosotros los humanos.

Y esto, también, es algo que la ficción siempre se equivoca. Las computadoras son solo herramientas. No están vivos en un sentido biológico. Pero en teoría pueden ser sensibles, incluso si eso parece estar muy lejos de la ingeniería de software a partir de ahora. Pero no creo que estemos diseñando sistemas inteligentes. Estamos diseñando para que sean mejores herramientas para nosotros. Y una de las cosas que necesitamos es hacerlos más inteligentes que hoy.

Y supera los 30 años perdidos de oscuridad de la IA. Y deja de hacer preguntas tontas que solo son Mu para mostrar retóricamente cuán malas son y cuán limitadas. Es mejor centrarse en lo que pueden hacer, lo que nunca se descubrió, que nadie pensó, se atrevió a hacer y logró explorar con ellos.

Es lo mismo con las tareas completas de NP que las computadoras realmente pueden resolver bastante bien hoy. No encontrar la solución (teóricamente) perfecta (las computadoras NO PUEDEN hacer eso! Gritan todos y su hermana), sino una solución práctica que realmente ayude. Que es lo que hacen por todos hoy.

Porque los límites teóricos no son límites prácticos. La mayoría de los límites teóricos que puedes ignorar en la vida cotidiana. No tienen importancia o al menos son muy menores.

Incluso el ATTiny11 puede proporcionarle un flujo interminable de números aleatorios para el momento en que los átomos no se descomponen. Y para cualquier momento la humanidad existirá. Y es por eso que la respuesta es: SÍ

Sí, solo hazlo. Ignora a los que no dicen. Realmente estoy harto de los que no dicen en informática teórica. “¡Las computadoras no pueden resolver los problemas de NP!”, Gritan. Y, en teoría, tienen razón, pero solo son menos de 10 líneas en Python con el paquete DEAP para resolver un gran problema de mochila como un pequeño ejemplo de lo que puede hacer con eso. Y su computadora no se calienta con eso, y ni siquiera tiene tiempo para tomar un sorbo de té antes de que su computadora presente una respuesta. Si. Tal vez no sea la respuesta perfecta, pero ¿a quién le importa? De Verdad? La perfección es como el infinito, no de este mundo. No me interesa la perfección, ni el infinito ni ninguna otra cosa abstracta. Necesitamos soluciones Encuéntralos.

Quiero saber algunas respuestas reales de la informática teórica sobre qué es / es / posible pero que nunca se ha probado. Como las cosas que Alan Turing soñó. Quiero algunos sueños y no cojo Schopenhauer 38 trolling, luciendo petulante y sin lograr nada. Respeto este campo, no me malinterpreten, pero están pendientes de esta mierda desde hace 30 años también. Y son una de las razones por las que el campo de la IA estuvo estancado durante tanto tiempo. ¡Dejen eso, chicos! Y se te ocurre algo útil.

Tenemos grandes problemas que resolver y un poco atrevido SÍ es lo que necesitamos ahora. Solucionemos los problemas de nuestra sociedad y no nos lamentemos por eso / teóricamente / nuestras máquinas ni siquiera pueden contar hasta el infinito y obtener calificaciones de doctor por no decirlo. Eso es solo Mu.

Si va a rechazar excepciones triviales, como la salida de los resultados de un generador de números aleatorios verdadero (es decir, no algorítmico), entonces no, las computadoras no pueden generar una salida infinita no repetida cuando se limitan a la memoria finita.

El argumento es más sutil de lo que esperaba. Mi contraejemplo iba a ser la fórmula Bailey – Borwein – Plouffe que permite calcular un dígito arbitrario de [math] \ pi [/ math] sin necesidad de calcular ninguno de los dígitos anteriores (o mantenerlos en la memoria). Sin embargo, calcular el dígito [matemático] k [/ matemático] de [matemático] \ pi [/ matemático] requiere que [matemático] k [/ matemático] se codifique de tal manera que pueda caber en la memoria. Dado un límite de memoria arbitrario, es bastante fácil encontrar un valor para [math] k [/ math] que sea lo suficientemente grande como para no ser representable dentro de ese espacio.

Si la hipótesis fuera cierta, los generadores de números pseudoaleatorios no tendrían que existir.

Si el programa tiene un conjunto finito de entradas finitas y debe ejecutarse en una cantidad finita de memoria, entonces la respuesta es no.

La restricción que coloco en la secuencia de entrada es fácil de ver. Considere el pseudocódigo:

Mientras (verdadero) {
Entrada I;
Salida I;
}

Si “I” en la declaración 2 es infinito, entonces no cabe en la memoria. Entonces, suponga que todas las entradas son finitas. Entonces, el programa claramente usa una cantidad finita de memoria. La entrada de ese programa determina completamente la salida. Si sus entradas son los dígitos de π, entonces la salida será los dígitos de π. Esto parece violar el espíritu de la pregunta que hizo.

Entonces, suponga que hay un número finito de entradas finitas. Considere el estado del programa en ejecución. El estado se define por el contenido de su memoria y registros (incluida la PC) y el flujo de entrada actual. Dado que el tamaño de las ubicaciones y los registros de memoria son finitos, y dado que hay un número finito de cada uno, y hay un número finito de entradas finitas, el número total de estados que el programa puede alcanzar es finito. Como las computadoras actuales son deterministas, el estado actual de ejecución de dicho programa determina completamente el siguiente estado. Por lo tanto, el programa en ejecución bajo una restricción de memoria finita dada es equivalente a un autómata determinista de estado finito.

Debería ser obvio que el estado del programa en el momento en que ejecuta una declaración de salida determina completamente la salida. Ahora, considere la secuencia de estados durante una ejecución dada (infinita) del programa bajo una restricción de memoria finita. Como el programa es equivalente a un autómata de estado finito, la secuencia de estados de ejecución es en última instancia periódica. Se deja como ejercicio para que el lector vea cómo esto conduce a un conjunto de resultados en última instancia periódico.

No estoy de acuerdo con las respuestas positivas que has recibido hasta ahora.

Desde un punto de vista práctico, puede crear listas muy, muy largas, pero una computadora tiene una cantidad limitada de memoria, que corresponde a un número limitado de estados. Finalmente, se verá obligado a repetir uno de los estados y, a partir de ahí, pasar a un ciclo de salida periódico.

Ese escenario cambia si permite el uso de una “memoria infinita” o el proceso para volver a leer la salida dada hasta ahora.

Editar:

Permitir que el programa lea su propia salida probablemente tampoco sería suficiente ya que en un punto no podrá realizar un seguimiento de la posición en la que está leyendo en una secuencia demasiado larga.

Pensé en una forma de argumentar de manera acertada que no es posible en términos simples. Es decir, una computadora con una banda de memoria finita no puede funcionar durante una cantidad de tiempo infinita para producir, un dígito a la vez, un número trascendental infinito como pi.

Un número trascendental siempre está cambiando, donde no puedes encontrar alguno sobre todo el patrón. Sin embargo, cualquier subsecuencia del número se repetirá nuevamente en algún momento. Además, puede encontrar cualquier número como subsecuencia de los decimales.

Ahora, solo hay dos formas posibles de determinar / calcular un decimal de pi, que es o bien (1) conociendo todos los números anteriores o (2) sabiendo en qué posición se encuentra.

(1) Si solo recibiera una subsecuencia de los dígitos y calculara el dígito que sigue, no podría ser lo suficientemente exacto. Esto es porque; cada vez que vea esa subsecuencia, calcularía el mismo resultado que el dígito de seguimiento, lo que significa que ya no es trascendental.

Por lo tanto, debe tener en cuenta todos los decimales anteriores, lo que significa que tendrá que mantener esos dígitos anteriores en la memoria. Pero, la memoria es finita y, por lo tanto, finalmente se acabará. Por lo tanto, no es posible de esta manera.

(2) si fuera capaz de calcular cualquier número decimal de pi en un cierto índice “i” con una función f (i), entonces aún tendría que abordar eventualmente números de índice tan grandes que no podrían almacenarse en memoria (por ejemplo, número de índice de 16 gb

Con todo, no hay forma de hacer que una computadora con memoria finita funcione por una cantidad infinita de tiempo produciendo pi, e o cualquier otro número de transmisión.

No.

Suposiciones
* Estrictamente no repetitivo

* Una salida es algo ‘atómico’ como printf (“% s”, our_amazing_output)

Cadena de pensamientos:

(i) si utilizamos un generador de números aleatorios (RNG) ideal, que escupe números distribuidos de manera perfectamente uniforme, eventualmente alcanzaríamos un límite. por ejemplo, si tenemos un RNG de 100 bits, después de 2 ^ 100 salidas terminaríamos el ciclo y, por lo tanto, repetiríamos una salida.

(ii) una solución rápida para eso sería agregar los nuevos números repetidos a las salidas anteriores para que la salida sea única nuevamente. Pero esto requerirá copiar y pegar la salida que requiere memoria, con un infinito que sería imposible.

(iii) pero entonces, ¿por qué incluso un RNG? Podemos simplemente hacer un bucle como se muestra arriba, pero nuevamente eso no funciona. volver a (ii)

Sí, eso es relativamente trivial. Necesita imprimir algo que se sabe que no se repite sin requerir que recuerde lo que ha impreso hasta ahora. Las sugerencias obvias son números trascendentales, como [math] \ pi [/ math] o [math] e [/ math].

En teoría no. En la práctica, no puede tener una salida infinita de todos modos, y es fácil escribir programas triviales que generarían una salida que no se repetiría durante la vida útil de la computadora.

Sí, si se cumplen estas condiciones: la generación de números aleatorios no es cíclica, el programa se ejecuta en tiempo real y no se compila.

Luego en técnica:

mientras que (1) {

n = randNum (0)

imprimir (n)

{

Una interpretación es que la generación de números aleatorios es independiente de la aritmética modular y, a medida que el programa se ejecuta en el procesador, sobrescribe continuamente la memoria utilizada por la pila. No sé si dicho sistema es implementable.

Hay algoritmos que generan los dígitos de PI con una cantidad constante de uso de memoria.

Tal programa puede generar una salida infinita no repetitiva

Un sistema operativo es tal programa. Otro: John McCarthy tenía su computadora de oficina conectada a un termómetro. Cuando está atrapado en una conversación, puede usarse como un reloj, cuando la temperatura cambia un grado, es hora de volver al trabajo. Pero en el área de SF Bay eso es mucho tiempo.

El desbordamiento de enteros es lo que dice: desbordamiento de enteros. No tiene nada que ver con la memoria.

Por lo tanto, su programa es un buen ejemplo de lo que desea, pero se repetirá en breve.

Busque generadores de números pseudoaleatorios con un período muy largo. Algo así como el Xorshift de Marsanglia incluso debería funcionar con su 2 ^ 128-1 perod.

Parece que la máquina solo puede estar en un número finito de estados y solo puede ver una cantidad finita de información. Entonces ahí está tu respuesta.

Sin embargo, sería casi fácil dar la apariencia de una salida infinita no repetitiva en escalas de tiempo humanas con nuestra tecnología. Te puede interesar El problema del castor ocupado (enlace aleatorio).