Estoy empezando a leer un libro sobre Complejidad Computacional y Máquinas de Turing. Aquí está la cita:
Un algoritmo (es decir, una máquina) puede representarse como una cadena de bits una vez que decidimos sobre una codificación canónica.
Esta afirmación se proporciona como un hecho simple, pero no puedo entenderlo.
Por ejemplo, si tengo un algoritmo que toma como entrada y calcula o:( x + 1 ) 2
int function (int x){
x = x + 1;
return x**2;
}
¿Cómo se puede representar esto como una cadena usando el alfabeto ?
algorithms
turing-machines
computability
computation-models
Kenenbek Arzymatov
fuente
fuente
Respuestas:
La respuesta más ingenua y simple a su pregunta es que el código proporcionado (y el código de máquina compilado) se representan de hecho como cadenas sintácticas de {0,1} *. Además, dado que está hablando de máquinas turing, los programas que ejecutan son una lista lineal de operaciones / instrucciones, no hay razón para que no puedan representarse como bits / bytes.
fuente
Ya tiene una representación de esa función como texto. Convierta cada carácter en un valor de un byte utilizando la codificación ASCII. Entonces el resultado es una secuencia de bytes, es decir, una secuencia de bits, es decir, una cadena sobre el alfabeto . Ese es un ejemplo de codificación.{ 0 , 1 }∗
fuente
No me puedo resistir ...
(Los puntos anteriores representan unos, los ceros en blanco).
fuente
Su computadora almacena todo como secuencias de
0y1, incluida la pregunta que escribió para preguntar cómo lo hace. Por ejemplo, cada letra y símbolo está representado por 8 bits (estoy hablando de cómo solían ser las cosas, hoy en día es de 16 bits y más complicado). Puedes verlos aquí . Bueno, no muestran los bits, sino los códigos hexadecimales y octales. ¿Sabes cómo convertir un número a su representación digital?fuente
La hipótesis fundamental detrás de este concepto es la tesis de Church-Turing . Puede ser difícil ver que cualquier algoritmo pueda representarse como una cadena de bits, porque el término "algoritmo" puede considerarse en términos muy informales. En la tesis de Church-Turing, usan un concepto muy rigurosamente definido de lo que es un algoritmo (e incluso entonces ha habido algunas preguntas sobre las palabras). Sin embargo, su terminología ha tenido tanta influencia que a veces se argumenta que estas definiciones de palabras como "algoritmo" son tan efectivas que simplemente las aceptamos como la definición.
Church-Turing afirma que cada algoritmo puede implementarse como un cálculo en una máquina de Turing. Dado que la descripción de una máquina de Turing es un conjunto finito de valores, es trivial ver cómo mapear esta descripción en una secuencia de números y luego en una secuencia de 0 y 1.
Como las otras respuestas han mencionado, es trivial representar su algoritmo de ejemplo usando codificación ASCII u otras codificaciones.
Creo que la razón por la cual su libro da esta afirmación como un hecho proviene del hecho de que muchos simplemente usan la tesis de Church-Turing como base para su definición de un algoritmo. Si utiliza dicha definición, es un hecho tan obvio como "5 es un número" porque básicamente lo definió como tal.
fuente
Esta declaración se basa en la existencia de TM universales . Estas son básicamente TM programables que pueden simular cualquier otra TM con a lo sumo poli sobrecarga. Por lo tanto, su programa es simplemente parte de la entrada codificada como ceros y unos.
fuente
Bueno, hablemos de algoritmos que no se pueden representar como una cadena de bits finita para ningún tipo de codificación.
Déjame escribir un algoritmo para ti ... Ah, pero si lo hago, puedo representar ese algoritmo con la codificación de mi texto escrito.
¿Qué tal representar mi algoritmo usando algunos 'medios analógicos', digamos por la posición de algunas monedas en mi escritorio? Aunque la posición de esas monedas puede ser modelada por algunos números reales (lo que en algunas codificaciones podría ser imposible de representar de manera finita), ¡esta descripción completa puede considerarse nuevamente una representación de mi algoritmo y puede codificarse nuevamente en una cadena de bits!
¡Espero que estos ejemplos aclaren que si algún algoritmo no puede ser representado por una cadena de bits finita, no tenemos forma de describir este algoritmo en absoluto!
Entonces, ¿por qué consideraríamos la existencia de algo de lo que no podemos hablar? Quizás interesante para la filosofía, pero no para la ciencia. Por lo tanto, definimos la noción de algoritmo de modo que pueda representarse mediante una cadena de bits, ya que al menos sabemos que podemos hablar sobre todos los algoritmos.
Aunque la respuesta anterior a la pregunta formulada, creo que la confusión sobre el ejemplo dado se debe principalmente al hecho de que una representación solo necesita representar de manera única algún algoritmo. ¡La forma de representación no necesita involucrar los cálculos reales invocados por el algoritmo! ¡Esto es muy útil, ya que significa que también podemos representar algoritmos no calificables !
fuente
Otra forma de ver esto es a través de la teoría de la información. Todas las codificaciones de información / preguntas significativas / útiles se pueden convertir en 'secuencias' binarias.
Gran parte del campo va a la pregunta, "¿cuál es la forma de hacer la menor cantidad promedio de preguntas para comunicar una información significativa?" En la práctica, esto es lo mismo que "¿cuál es el enfoque óptimo para hacer la menor cantidad de preguntas de sí / no para comprender lo que se comunicó o dijo?"
fuente