Bitcoin es un sistema de Turing completo incluso en script. Por CSW
Bitcoin es un sistema de Turing completo incluso en script.
CSW
1 de septiembre de 2021
Desafortunadamente, un problema importante proviene de la falta de comprensión y de muchos términos comunes en la actualidad. La completitud de Turing no requiere una cinta infinita y, no fue una cinta infinita lo que Turing mencionó en su artículo; era un sistema ilimitado. Es importante destacar que no puede tener una máquina de Turing con una cinta infinita en lugar de una cinta ilimitada por definición. Una cinta infinita no está relacionada con un problema que se pueda calcular.
La primera parte de esto que debe recordar es que una máquina de Turing puede calcular cualquier problema computable. No se pueden calcular todos los algoritmos. Decir que puede ejecutar un programa que nunca se detiene no es crear una máquina de Turing. Eso tampoco es una cinta infinita; es un sistema ilimitado. Por definición, cualquier sistema ilimitado es siempre infinitamente más pequeño que el infinito.
Bitcoin es un sistema completo de Turing incluso en script . Una máquina de Turing asume que tienes una cinta ilimitada. En este caso, significaría un tamaño de script ilimitado. Dado un script arbitrariamente largo, puede ejecutar cualquier algoritmo computable posible. El hecho de que el tamaño del guión se vuelva difícil de manejar es irrelevante. No todas las máquinas de Turing son eficientes. Sin embargo, no hay nada en los cimientos de las máquinas de Turing que requiera eficiencia.
La razón principal por la que el núcleo ataca el comentario de que he afirmado que bitcoin es Turing completo está relacionado con la introducción de límites que han impuesto. Mientras que dije que Bitcoin crece hasta donde termina en los centros de datos , ellos desean crear un sistema separado que sea más limitado. Una cinta limitada no es aquella que pueda ejecutar ningún algoritmo. Por lo tanto, con un tamaño de transacción limitado, nunca podrá alcanzar el mismo nivel de cálculo que con un tamaño de transacción ilimitado.
Turing escribió los siguientes artículos:
Turing, AM (1937). En números computables, con una aplicación al Entscheidungsproblem . Actas de la sociedad matemática de Londres, 2 (1), 230-265.
Turing, AM (1937). Computabilidad y definibilidad de λ . The Journal of Symbolic Logic, 2 (4), 153-163.
Turing, AM y Church, A. (1937). Computabilidad y definibilidad X. Lógica simbólica, 2.
Si lee estos, verá que él (Turing, 1936, p. 230) está hablando de “números ‘computables’” que “pueden describirse brevemente como los números reales cuyas expresiones como decimales se pueden calcular por medios finitos”.
Pi no es un valor computable de Turing según esta definición. Más bien, una aproximación en tiempo y espacio finitos de pi puede considerarse computable por Turing.
El artículo de Turing se basa en que mi Godel :
, «Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme , I». Monatsheftc Math. Phys., 38 (1931), 173-198
Desafortunadamente, si no tiene los antecedentes matemáticos en forma de matemáticas discretas de las que estos autores estaban hablando, o sobre lo que escribieron, en ese caso, es probable que cometa uno de los muchos errores que la gente comete en torno a la definición de un Máquina de Turing.
Turing había notado (1936, p.230) que la clase de números computables era «no obstante enumerable». Sin embargo, no dijo que la máquina de gira en sí misma deba ser enumerable para que esto sea cierto.
Turing estaba ampliando la investigación de Church (1936), que investigaba el concepto de «calculabilidad efectiva». Como señaló Turing, la calculabilidad efectiva es funcionalmente equivalente al concepto de «computabilidad» de Turing, mientras que estos se definen por separado. Por esta razón, se le ha llamado el problema de Church-Turing. Cada autor creó una solución con Church derivando la primera.
Alonzo Church, “Un problema irresoluble, de la teoría de números elementales”, AmericanJ . of Math., 58 (1936), 345-363
2/3
Hennie (1965) investigó el concepto de una máquina de Turing fuera de línea de una sola cinta.
Hennie, FC (1965). Cálculos de máquina de Turing fuera de línea en una sola cinta. Información y control, 8 (6), 553-578.
Dicha máquina y cinta se pueden calcular según sea necesario y crear de una manera estructurada que luego se puede producir para validar cualquier número computable. Un ejemplo de cómo esto puede reflejarse en el script bitcoin sería crear un conjunto de reglas y procesos matemáticos que puedan computar cualquier número digital en una cinta que luego pueda ser procesada. En este caso, podemos comparar la cinta con el script bitcoin. De esta manera, podría imaginarse la creación de una sola transacción como una sola cinta que se compila y produce fuera de línea y se usa en línea en un tiempo finito.
Hartmanis (1968) proporcionó una discusión sobre la complejidad de las máquinas de Turing de una sola cinta. Si bien señaló que existe un límite de tiempo agudo en nueve conjuntos regulares de secuencias, existen varias formas de complejidad computacional que pueden usarse para medir estas formas de computación. Simultáneamente, es posible determinar los diferentes niveles de complejidad para estas cintas en comparación con estas cintas para múltiples máquinas de cinta. De esto se derivan las diversas formas de complejidad computacional. Entonces, el problema ahora no es si un script es un sistema completo de Turing, sino si es eficiente. Por supuesto, el cálculo de una sola cinta es ineficiente y no es uno que yo recomendaría, pero es factible y posible de implementar.
Hartmanis , J. (1968). Complejidad computacional de los cálculos de la máquina de Turing de una cinta. Revista de la ACM (JACM), 15 (2), 325-339.
Shannon (1956) examinó el concepto proporcionado por Turing para hacer una máquina mecánica u otra máquina eléctrica y cometió un error en la descripción. Desafortunadamente, Shannon (1956, p. 157) describió la máquina de Turing como un sistema que requiere “un elemento de control, un cabezal de lectura y escritura y una cinta infinita”. No fue Turing quien afirmó que una máquina de Turing debe ser infinita, sino Shannon.
Shannon, CE (1956). Una máquina de Turing universal con dos estados internos. En Automata Studies. ( AM-34), Volumen 34 (págs. 157-166). Prensa de la Universidad de Princeton.
Mientras que Shannon produjo una excelente ingeniería; no era matemático. Ésta es una distinción importante porque Turing (1936, p. 230) afirmó categóricamente que era una máquina que puede calcular “los números reales cuyas expresiones como decimal son calculables por medios finitos”.
Turing señaló que la máquina de computación no escribe más que un número finito de símbolos (1936, p. 233). En esto, la máquina no tiene límites, pero no es infinita. Ésta es una distinción significativa y muy importante que muchos no matemáticos no lograron comprender. Una máquina ilimitada es infinitamente más pequeña que cualquier valor infinito.
Hopcroft y Ullman (1969, p. 168) investigaron las máquinas de Turing delimitadas por cinta y siguieron el error de Shannon de suponer una cinta de trabajo infinita en lugar de una ilimitada. Desafortunadamente, esto es pereza y no debería haberse hecho de esta manera. Observará que discuten las versiones en línea y fuera de línea de las máquinas de Turing y que notan que en el caso de la máquina de Turing fuera de línea que mencioné anteriormente, se puede suponer que la cinta no se repite. En este artículo (1969, p. 169), observará que los autores han eliminado la suposición de que la máquina se detiene para cada entrada. Si bien esto proporciona una forma de máquina, no es más que un solo ejemplo, y la gente los toma por más de lo que son como ejemplos y los hace universales. Tenga en cuenta que no estoy diciendo una máquina de Turing universal aquí, que es otra cosa diferente.
Hopcroft, JE y Ullman, JD (1969). Algunos resultados en máquinas de Turing delimitadas por cinta. Revista de la ACM (JACM), 16 (1), 168-177.
3/3
Sin embargo, suponga que lee el documento en su totalidad. En ese caso, verá que la definición de una máquina de Turing no determinista que presentan como una 6-Tupla (p. 169) se crea utilizando estados finitos, símbolos finitos y finito. Por tanto, no es una máquina infinita.
Aunque la gente usa infinito e ilimitado indistintamente, estos son conceptos diferentes. Existe una diferencia entre un sistema ilimitado y un sistema infinito, ya que un sistema ilimitado es necesariamente finito. Si bien no tiene límites definidos, es definible en grande, lo que se diferencia de un sistema infinito que es indefinible en grande.
La forma de pensar en esto es crear un sistema que tenga 100 unidades de cinta y, si necesita más espacio, agregue otro sistema de 100 unidades de cinta para ampliarlo. Además, puede hacer esto tantas veces como sea necesario. Eso sigue siendo un proceso que ocurre en un tiempo finito en un espacio finito y, por lo tanto, nunca se vuelve infinito.
Note aquí que he dicho en <espacio> «finito» y no lo he dicho de una manera que indique que es un proceso que es «infinito». Esta distinción no es matemática, sino más bien el error al notar en <space> finite difiere de la expresión inglesa infinite.
Un problema inviable no se puede resolver y no tiene solución. Se puede calcular un problema ilimitado con suficiente tiempo y espacio de memoria.
En un artículo sobre computación paralizada , Juille y Pollack (1996) documentaron metodologías para crear una máquina de Turing de cintas múltiples que sería más eficiente que un tipo de transacción de cinta única que propuse anteriormente. En esto, en lugar de una sola transacción, ejecutaría muchas transacciones en paralelo y solo requeriría que se promocione una única ruta como solución. De esta manera, no usaría una sola transacción, sino un número ilimitado de transacciones que se computan como máquinas de Turing fuera de línea donde solo envía una sola transacción para que se registre en Blockchain que se ha demostrado (fuera de Blockchain) para encontrar la solución deseada y calcular el problema correctamente.
Juillé , H. y Pollack, JB (1996). Programación genética masivamente paralela. En Avances en programación genética: volumen 2 (págs. 339-357).
McCarthy (1956, p. 177) señaló que un sistema como una máquina de Turing en una sola transacción de bitcoin (y no, no estaba describiendo bitcoin sino máquinas computacionales generales de este tipo) son extremadamente ineficientes. En consecuencia, como señalé anteriormente en el artículo de Juillé y Pollack (1996), la solución debería encontrarse en sistemas paralelos que calculan muchas posibilidades simultáneamente en lugar de hacer una sola cinta de transacción difícil de manejar. Dicho esto, queda que una sola transacción y el script que se puede escribir en una sola transacción son en sí mismos Turing completos siempre que no intente limitar el tamaño de Blockchain.
El argumento en contra de que bitcoin sea Turing completo es el de los límites de tamaño de transacción y bloque. Dados esos límites, bitcoin no es un sistema completo de Turing, pero bitcoin no fue diseñado para ser limitado de esa manera. Por lo tanto, si bien BTC no es Turing completo, bitcoin sí lo está.
McCarthy, J. (1956). La inversión de funciones definidas por las máquinas de Turing. En Automata Studies. ( AM-34), Volumen 34 (págs. 177-182). Prensa de la Universidad de Princeton.
Fue un torrente de conciencia de cuando desperté
Bitcoin es un sistema de Turing completo incluso en script.
CSW
1 de septiembre de 2021
1/3
Bitcoin es un sistema de Turing completo
Dejar un comentario
¿Quieres unirte a la conversación?Siéntete libre de contribuir!