¿Pueden las computadoras hacer cosas que las máquinas de Turing no pueden?

Las computadoras digitales electrónicas de hoy en día a menudo se denominan máquinas de Turing universales. Es decir, el concepto de UTM se usa para comprender las computadoras digitales electrónicas de programa almacenado de hoy. Pero, ¿es adecuado este concepto? De hecho, ¿pueden las computadoras de hoy hacer cosas que las UTM no pueden hacer? Si pueden hacer más de lo que puede hacer un UTM, podría ser importante para AI, ya que AI (y Searle y su argumento de la habitación china) usan el concepto UTM para definir las capacidades de la plataforma de investigación y desarrollo de AI: la computadora digital electrónica.

La máquina de Turing es una abstracción, y las computadoras electrónicas se implementan físicamente, por lo que pueden realizar acciones físicas y afectar cosas físicas, como teclados y monitores, pueden visualizar sus resultados, mientras que la máquina de Turing no puede, pueden realizar tareas equivalentes mucho más rápido, etc. Sin embargo, en teoría , cualquier programa que una computadora pueda ejecutar puede ser ejecutado en principio por una (realización física de) una máquina de Turing.
@Roddus Como una abstracción matemática, una máquina de Turing tiene una cinta infinita, por lo que su pregunta probablemente debería ser al revés :)
Las computadoras de hoy, no. Sin embargo, hay problemas que tienen respuestas que las computadoras de hoy no pueden resolver. En teoría, es posible que alguien cree una computadora "mágica" (que se ve muy diferente a una máquina de Turing) que pueda responder estas preguntas.
Crea calor. Ocupar espacio. Descomponer. Quedarse sin memoria.
@jobermark Me estoy quedando sin memoria con lo que estaría de acuerdo. Pero una TM sería realmente fácil de hacer (se agregaría más cinta cuando fuera necesario) y el motor generaría calor, la máquina ocuparía espacio... Estaba pensando más en la memoria de acceso aleatorio y en realidad recibir entrada. ¿Y algo mas?
@Conifold Siempre me pareció extraño que las máquinas de Turing (según el artículo de Turing de 1936) no tengan entrada en tiempo real. El que imprime 0 1 0 1... no tiene ninguna entrada. La máquina Universal tiene su SD (programa) cargado y es entrada en este sentido, pero una vez que la máquina empieza a ejecutar el programa, no hay entrada. (Si lo hubiera, los símbolos tendrían que aparecer en cuadrados vacíos como por arte de magia). Solo me pregunto si hay algo importante en esta falta de posibilidad de entrada en tiempo real en una máquina de Turing de 1936.
@ngn Mi interés en saber si las computadoras son máquinas de Turing proviene del argumento de la habitación china de Searle. Entiende la máquina electrónica con los conceptos de la máquina universal de Turing. Pero, ¿la computadora digital electrónica es una UTM? No es (según tengo entendido) en el sentido de que los UTM no tienen memoria de acceso aleatorio (solo izquierda, derecha, un cuadrado a la vez) y no tienen entrada en tiempo real. Pero, ¿hay algún programa que se ejecute en la máquina electrónica pero que ninguna máquina de Turing pueda ejecutar (ignorando la RAM y la falta de entrada de UTM)?
@ngn continuación ¿Qué pasa con (en Basic) A$=B$, en otras palabras, copiar el contenido de la variable B$ y almacenar la copia en la variable A$? El programa no tiene idea de lo que contiene B$. ¿Puede una TM realizar una operación de copia sin identificar los símbolos a copiar? O en C: a=*b, tome lo que está almacenado en b y asígnelo a a. O en ensamblador, mov EAX, EBX, copie el contenido del registro EBX para registrar EAX. en todos estos programas la cosa a manipular no es identificada por el programa. ¿Puede una máquina de Turing manipular un símbolo sin identificarlo (escanearlo)?
@Roddus a TM puede simular acceso aleatorio, solo que no tan eficientemente. No entiendo a qué te refieres con "sin identificar los símbolos" en tu último comentario. Obviamente, un TM debe conocer al menos los desplazamientos de origen/destino en su cinta para realizar la copia.
Si la entrada es en tiempo real o está preescrita en la cinta de entrada, no es relevante para la naturaleza de la computación. Los problemas con la formalización de entradas y salidas para TM se discutieron en Math SE: Entrada y salida de una máquina de Turing .
@Conifold Eso es interesante sobre la naturaleza de la computación. Voy a mirar la referencia. ¿Por qué la fuente de los símbolos no es relevante para la naturaleza de la computación? (Intuitivamente, la fuente parece irrelevante, pero ¿se puede explicar la intuición?) Estoy pensando en símbolos recibidos por el TM desde un sistema externo, no en símbolos impresos en la cinta por el propio TM (que podrían considerarse entradas para el algoritmo de ejecución) , pero la fuente de esta "entrada" es la propia TM).
La computación es, por definición, lo que transforma la entrada en la salida, se abstrae de dónde vienen y adónde van. Puede suponer que "el mundo" ya escribió todos los símbolos en la cinta que se alimenta a TM. De hecho, puede imaginar que dicha cinta se alimenta "en tiempo real", pero eso no hace ninguna diferencia en lo que hace con ella.
@Conifold Entonces, cuando una picadora de carne muele carne, ¿eso significa que la picadora de carne realiza un cálculo en la carne? A lo que estoy tratando de llegar es si una computadora puede procesar tokens que llegan de los sensores sin realizar cálculos sobre ellos. ¿Todo lo que hace una computadora con la entrada se define como "computación"? ¿O se define "computación" de alguna otra manera sin referencia a lo que hacen las computadoras? Si es así, la pregunta "¿Las computadoras necesariamente computan?" Es empírica. Y tal vez puedan procesar lo que procesan sin computar sobre lo que procesan (y esto tiene implicaciones para la CRA).
@ngn Por "sin identificar los símbolos" quiero decir que una TM puede hacer cosas con los símbolos, procesarlos, manipularlos, sin identificarlos. Estoy pensando en un programa de computadora que pueda hacer esto, por ejemplo, var2 = var1. Esto copia lo que esté en la variable (lo que esté almacenado en la ubicación nombrada) var1 y lo escribe en var2. ¿Puede una MT hacer este tipo de copia "ciega"? ¿O tiene que identificar los símbolos en var1 y luego ejecutar condicionales donde la operación de escaneo es exitosa? Por ejemplo, si "1" está en var1, entonces el TM tiene que ejecutar los condicionales Scan: si "0" entonces...; si "1" entonces...?
@Roddus Cuando dice "ciego", ¿está tratando de describir algo como el cifrado completamente homomórfico ?
La computación es el procesamiento de símbolos, no importa, así que tampoco estoy seguro de a qué se refiere su analogía. No estoy seguro de qué son los "tokens que llegan de los sensores", pero qué diferencia hace en principio si los consideramos como la entrada o agregamos una capa adicional de cómputo y los vemos como procesados. La computación se define como la transformación de entradas en salidas de acuerdo con las reglas de transcripción. Esos se implementan aproximadamente en computadoras físicas, todo lo demás que hacen es irrelevante en esta abstracción. Entonces, sus preguntas empíricas no son sobre computación.
Las máquinas de @Roddus Turing no son objetos físicos. Período. Si construyes un modelo físico de uno, no sería uno, así como una máquina que genera permutaciones no es un grupo. Como tales, no tienen una velocidad de cálculo, por lo que la memoria lineal y de acceso aleatorio son equivalentes.
@ngn algo así como la firma ciega de un cifrado homomórfico.
@Conifold los tokens que llegan de los sensores son los objetos que emiten los sensores digitales y que viajan a la computadora ('símbolos'). Gracias por una definición de computación. Lo pensare. Estoy tratando de ver la máquina física como un sistema causal, y el concepto de símbolo trae consigo mucho bagaje lingüístico (que Searle hace un gran uso). Pero si una computadora puede manipular un 'símbolo' de entrada sin transformarlo en un símbolo de salida de acuerdo con una regla de transcripción, ¿la computadora está haciendo algo más que calcular el símbolo?
@jobermark Entiendo que el concepto de TM es, en efecto, la definición de computación de la máquina. Estoy tratando de ver la computadora electrónica como un sistema causal y preguntar, bueno, ¿puede realizar tipos de procesamiento en símbolos que las MT no pueden? Quiero decir, ¿hay una diferencia fundamental? ¿O la UTM explica completamente las habilidades, las posibilidades del dispositivo electrónico?
@Roddus, tanto las TM como las computadoras pueden realizar un cifrado completamente homomórfico
@Roddus Tenemos una prueba formal de que la manipulación de bits y los UTM son totalmente equivalentes excepto por la velocidad. En cuanto a la velocidad, la principal diferencia sería la disponibilidad de aleatoriedad. Las máquinas modernas no lo usan, pero las máquinas cuánticas lo aprovecharían con creces. También tenemos NTM=DTM, por lo que, en principio, una máquina no determinista no puede ser más poderosa que una determinista, pero la combinación de procesamiento paralelo y aleatoriedad real teóricamente puede ser mucho más rápida. Así que 'puedo hacer' todavía no está adecuadamente definido.
Este es el significado estricto de "computación" en esta teoría. Si estamos usando una computadora analógica, entonces puede emplear un proceso causal de caja negra para la transformación. Siempre que estemos empíricamente seguros de que el resultado se ajusta a nuestras especificaciones, no tenemos que preocuparnos por lo que hay dentro de la caja. Pero tampoco es susceptible de análisis teórico como cálculo.
@ngn simplemente tomando la idea de firmar a ciegas un texto cifrado, supongamos que una máquina en una oficina de correos lee las direcciones en el exterior de los sobres que llegan por correo, luego dispara los sobres en diferentes contenedores según algún elemento de la dirección, digamos país . Esa máquina presumiblemente calcula las direcciones, pero ¿calcula los símbolos sellados dentro de los sobres? Presumiblemente no. ¿En qué se diferencia esto de la siguiente asignación de variables: a$ = b$? ¿El programa calcula sobre el contenido de b$?
@jobermark "la manipulación de bits y los UTM son totalmente equivalentes". ESTÁ BIEN. ¿Podría dar un enlace a la prueba formal?
@Conifold, ¿entonces "empíricamente seguro" significa una inferencia inductiva? ¿Y las especificaciones son del tipo skinneriano de estímulo-respuesta (entrada-salida)? Computación = "transformación de entradas en salidas según reglas de transcripción". Eso es útil. Entonces, para la computadora analógica de caja negra, las reglas son desconocidas, y la inferencia inductiva implica reglas invariantes y, por lo tanto, emparejamiento de entrada-salida invariante.
Aquí hay un ejemplo básico. drona.csa.iisc.ernet.in/~deepakd/atc-2008/murec.pdf . (Pero, en total, buscar cursos básicos para las clases de matemáticas de pregrado es algo que deberías hacer por ti mismo). Dado que todas las instrucciones de manipulación de bits son funciones recursivas, esto se aplica a toda la gama de máquinas digitales. Las máquinas analógicas caen bajo una rúbrica diferente, y en la medida en que procesan lógicamente números reales en lugar de enteros y permiten una aleatoriedad real, no están cubiertas por este resultado.
@Roddus FHE es más que el clasificador de correo que describe. Puede calcular el contenido de los sobres sin abrirlos.
Más o menos, por supuesto, podríamos tener una teoría física de lo que sucede dentro de la caja negra, pero puede ser computacionalmente (en el sentido abstracto) intratable emplearla. Las redes neuronales se utilizan a menudo como cajas negras, aunque en principio podrían analizarse computacionalmente.
Esta discusión de referencia e identificación se desmorona cuando te das cuenta de que la mayoría de los idiomas van a asignar $a=$b dejando que los dos símbolos apunten a la misma dirección. Los símbolos ayb y la dirección han sido 'identificados' pero no hay ningún concepto de su contenido. La pregunta es tan infundada que no tiene sentido preguntar si 'los contenidos' están 'identificados' o no y cómo.
Usamos los UTM como modelo para eliminar toda esta conversación ambigua, ya que las mismas cosas se pueden lograr de tantas maneras diferentes que no podemos saber exactamente a qué nos referimos cuando hablamos de algo tan simple como 'asignación': ¿Mueve el ¿contenido? ¿Cambia los punteros? ¿Simplemente le indica al compilador que dos cosas son iguales, sin ningún efecto real en el momento de la ejecución? ¿El idioma no elegirá eso simplemente por contexto? Cumplir con el modelo más restringido y menos poderoso evita que digamos tonterías sin sentido.
@jobermark Gracias. Entonces, la idea de asignación se abstrae de los detalles causales. O la cesión puede realizarse en distintas causalidades. Supongo que algunos dirían que ese es el principal valor de la abstracción (y el lenguaje indicará los detalles por su contexto). ¿Y las máquinas de Turing (UTM) son las más útiles? ¿último? ¿Más precisa? abstracción del programa almacenado computadora digital electrónica? Pero aún parece posible que los UTM no reflejen (o cualquiera que sea la palabra correcta) todo lo que las computadoras pueden hacer. Parece existir una independencia entre la UTM y el dispositivo electrónico.
@Roddus solo en la medida en que el dispositivo tenga componentes caóticos o analógicos. En la medida en que una computadora digital es digital , es isomorfa a una UTM. La electrónica que no es digital generalmente no se considera una computadora en el lenguaje moderno. Hay un cierto grado de negarse a entender lo que no quiere admitir que está pasando aquí.
@jobermark Esta es una pregunta básica que me interesa. El concepto de UTM se usa para comprender los dispositivos electrónicos particulares reales, las computadoras. ¿Se podrían utilizar otros conceptos bastante diferentes para entender estos mismos dispositivos? ¿Es la UTM la única idea que tenemos para entender la máquina? ¿Qué pasa con el concepto de asociación de particulares? ¿Podría entenderse útilmente la máquina como un dispositivo que crea instancias de relaciones asociativas?
Podría, y si esas relaciones son entre entidades discretas, el resultado sería probablemente isomorfo a un UTM. Entonces, ¿por qué no considerar un UTM como un dispositivo que crea instancias de relaciones asociativas? Correcto. La gente ya tiene , a través de álgebras relacionales y universales. El documento que cité ofrece cinco formas muy independientes de ver estos fenómenos, todas isomorfas a las UTM, pero con diferentes puntos fuertes. ¿Has seguido el enlace? ¿Te importa escuchar o deberíamos dejar de hablar? Pareces empeñado en no escuchar.
Así que no, no hay una forma de ver las computadoras: funciones recursivas, cálculo lambda, sistemas deductivos generales, álgebra universal, la teoría de formas relacionales, la categoría de categorías cerradas cartesianas, la semántica abstracta de tipos abiertos, la topología de marcas discretas teselaciones de un plano, etc. etc. etc. son todas formas de ver estos fenómenos. Y todos son isomorfos a UTM. Pero cada uno de ellos nos permite ver estas cosas desde un punto de vista diferente y hace que diferentes problemas sean más difíciles o más fáciles de representar.
La ventaja de la UTM es simplemente que es fácil de especificar y tiene reglas muy restrictivas. Entonces, para cuestiones de posibilidad e imposibilidad absolutas, es el ejemplo de la marca (Turing se centró en demostrar que un problema imposible es imposible). Para cuestiones de rendimiento comparativo, la gente suele recurrir a funciones recursivas (Kleene estaba preocupado por las matemáticas constructivas y aplicadas). Para cuestiones relacionadas con descripciones abstractas de comportamiento y relativa complejidad de expresión, a menudo recurren a conceptos de álgebra relacional como combinadores....

Respuestas (1)

La respuesta corta es no; Las computadoras modernas no pueden hacer cosas que las máquinas de Turing no pueden hacer. Lo que pueden hacer es ejecutar máquinas de Turing muy sofisticadas y complejas que simulan cosas que las máquinas de Turing no podrían hacer.

Éste es un punto importante; Las redes neuronales artificiales, los algoritmos genéticos, los algoritmos de lógica difusa y todos los demás tipos de mecanismos de "aprendizaje automático" e "inteligencia artificial" que las computadoras pueden ejecutar siguen siendo de naturaleza determinista y algorítmica. Todavía ejecutan una serie estricta de comandos y, lo que es más importante, no se desvían de esos comandos, pase lo que pase. Son buenos para resolver problemas NP (no polinómicos) solo en la medida en que emulan el proceso que llevaría a cabo un ser humano, pero esa emulación no es perfecta y es posible que nunca lo sea. Incluso los elementos 'aleatorios' en un Algoritmo Genético no son verdaderamente aleatorios; siembra una lista ordenada (pero aparentemente aleatoria) de números con un valor inicial y cada llamada de un número aleatorio se toma de esta lista desde un punto determinado por el valor inicial.

En ese sentido, las computadoras pueden acumular nuevos datos y pueden usar esos datos para impulsar su comportamiento, pero solo de acuerdo con las reglas de una máquina de Turing. En ese sentido, la computadora no puede extenderse más allá de su programación, aunque aparentemente puede emular esa capacidad por la forma en que usa los datos que acumula.

Hay cierto debate ahora sobre si una computadora cuántica romperá o no ese modelo, pero si lo hace, entonces no es una 'computadora clásica' y solo habremos usado el nombre 'computadora' para extender un metáfora que ya entendemos. Dicho esto, si una computadora cuántica puede o no operar de una manera no determinista será una pregunta muy interesante para tratar de responder a su debido tiempo.

Tim B II Usted dice "... las computadoras pueden acumular nuevos datos y pueden usar esos datos para controlar su comportamiento, pero solo de acuerdo con las reglas de una máquina de Turing". comportamiento. Los nuevos datos pueden determinar el comportamiento, pero ¿no contradice eso la teoría de la máquina de Turing de Turing? Un UTM ejecuta una descripción de una TM. Esta descripción (programa) define el comportamiento de entrada-salida de la UTM, cualquiera que sea ese comportamiento, presente, pasado y futuro. Pero, ¿no pueden los nuevos datos cambiar esa definición de comportamiento de entrada-salida?
Hola Roddus. Su explicación es exactamente por qué no podemos decir determinar su comportamiento. Incluso las redes neuronales son máquinas de estados finitos, y cómo los diferentes valores activan el movimiento entre esos estados se define de antemano. La gran complejidad del código detrás de una red neuronal puede hacer que parezca que los nuevos datos pueden cambiar la salida programada, pero el programa central no cambia, y si ejecuta los mismos datos con la misma semilla aleatoria, obtendrá los mismos resultados EXACTOS, cada vez porque el proceso sigue siendo determinista.
Hola, Tim B. No estoy seguro de haber entendido completamente tu comentario, pero ¿qué tal esta respuesta? La máquina tiene un programa simple. Todo lo que hace es tomar los dos primeros símbolos de entrada que llegan y almacenarlos en las ubicaciones 1 y 2. Todos los demás símbolos de entrada se comparan con el de la ubicación. 1. En caso de coincidencia, la máquina emite como salida una copia del símbolo en loc. 2. ¿El comportamiento de la máquina no depende de los datos de entrada, no del programa (o no solo del programa)? Es casi seguro que ejecutar una nueva instancia del programa dará como resultado un comportamiento diferente de la máquina (el flujo de entrada es variable).
Entiendo lo que dices, pero el problema que tengo es que la programación tiene en cuenta las variables que tienen diferentes valores en diferentes estados, incluida la entrada. las salidas cambiarán de acuerdo con las entradas, sí, e incluso los pasos que toma el programa son diferentes, pero el alcance del programa no ha cambiado. Que cambie las entradas solo significa que diferentes partes del mismo programa se ejecutan en diferentes momentos, no que la aplicación haya cambiado la forma en que manejaría cualquiera de las entradas.
Pero el programa no cambia. Y todo el pequeño programa se ejecuta. No sabe (ni le importa) lo que está almacenado en loc. 1 o 2. Pero el comportamiento de la máquina cambia (es diferente de una sesión a otra). Por lo tanto, el programa no puede explicar el comportamiento de la máquina. Algo más tiene que explicarlo. El algo más es el contenido del flujo de entrada (y, por extensión, si proviene de un sensor, entonces el algo más es el entorno detectado). Así que la máquina ha aprendido de su experiencia. Entonces, ¿significa esto que la idea de la máquina de Turing no puede explicar el aprendizaje a partir de la experiencia?
No, en realidad la máquina no ha aprendido de la experiencia, ha reaccionado de forma predeterminada a los cambios en los datos de entrada. Que el programa sea al menos en parte responsable del cambio en el estado de entrada es irrelevante. El programa SIEMPRE haría lo mismo con las mismas entradas, independientemente de cómo se crearon esas entradas. Esta es la razón por la cual la piratería es posible; las computadoras en realidad no saben nada acerca de los datos; es una entrada a un conjunto de instrucciones y aunque podemos observar lo que parece un comportamiento dependiente de los datos, es simplemente un procesamiento condicional impulsado por el valor.
Turing, en su artículo de 1950, planteó el tema del aprendizaje, diciendo que el aprendizaje es un caso de cambio de las reglas de operación de la máquina, y cómo fue esto posible dado que las reglas de operación (programa) están fijadas desde el principio, sin importar cuál sea la máquina. la historia puede ser. (Luego, las reglas postuladas "efímeramente válidas" para explicar el aprendizaje, sean las que sean). Mi pequeño programa no cambia y trata todas las entradas de la misma manera. ¿Es esto lo que quieres decir? ¿Que el aprendizaje es un cambio en las reglas, y si no hay cambio entonces (por definición de "aprendizaje") el aprendizaje no ocurre?
Sí, eso es exactamente lo que estoy diciendo. Cuando leo el artículo de Turing, estoy acumulando conocimiento. Cuando integro ese conocimiento en mi comprensión de los algoritmos y cómo funcionan las computadoras para cambiar la forma en que hago o pienso algo, eso es aprender. Otra forma de decirlo es que un HDD lleno de datos no ha "aprendido" nada más que un HDD en blanco porque ninguno de los HDD puede cambiar su comportamiento como resultado de los datos que contiene. Tampoco puede hacerlo un programa de computadora que se ejecuta contra cualquiera de los HDD, simplemente hace lo que está programado para hacer contra una entrada definida.
En su punto de que el programa SIEMPRE haría lo mismo con las mismas entradas. Así es. Presumiblemente, los procesos neuronales (programas) que procesan las entradas neuronales siempre hacen lo mismo con las mismas entradas también. Pero el punto es que dependiendo de las entradas, la MÁQUINA hace cosas diferentes. El programa nunca aprende. Es la máquina la que aprende. En otras palabras, el cerebro de la máquina es más que hardware más software. Hay algo más ahí. Y el aprendizaje se encarna en esta cosa extra. (Hice este comentario justo antes del último)
Si bien estoy de acuerdo con su sinopsis, es una lata de gusanos que he abierto muchas veces en este sitio. Matemáticamente, es posible que nuestra capacidad de aprender y tomar nuestras propias decisiones sea una ilusión. Empíricamente, estoy de acuerdo contigo; algo más está pasando. De todos modos, la máquina que llamamos computadora no puede extenderse más allá de su programación, aunque podemos emular ese fenómeno de manera bastante convincente. Entonces, la pregunta es si simplemente estamos emulando ese mismo fenómeno de manera tan convincente que incluso nos hemos engañado a nosotros mismos, pero eso está MUCHO más allá del alcance de su pregunta. :)
Y posiblemente mi comprensión. Pasé los últimos 18 años, incluidos 10 en investigación de posgrado, tratando (¿tontamente?) de explicar qué es lo extra. Ha sido difícil salir del modo computacional de pensar en el problema. De ahí la pregunta: ¿Pueden las computadoras hacer cosas que los TM no pueden (los TM son probablemente la definición aceptada de computación de máquina). No estoy seguro de que las máquinas de Turing puedan ejecutar el programa simple descrito anteriormente. Tienen que escanear ("identificar") un símbolo para poder manipularlo, pero el pequeño programa, en parte, no parece hacer esto.
¿Pueden las computadoras hacer cosas que las máquinas de Turing no pueden?
RespuestasAquíPolítica de privacidad1y, 2v