¿Qué tan grande es el conjunto de todas las máquinas de Turing?

Question

¿Qué tan grande es el conjunto de todas las máquinas de Turing? Estoy seguro de que es infinitamente grande, pero, ¿qué tipo de infinitamente grande es su tamaño?

Answer 1

Por un informal argumento, máquinas de Turing corresponden aproximadamente a los programas escritos en algún lenguaje de programación. Cada programa es una cadena finita en ASCII o unicode o binario (o de otro alfabeto finito de algún tipo).

Podemos imaginar la escritura ingenua de un programa de salidas de todas las posibles cadenas en lexographical orden, se ejecuta el compilador en cada uno, y tirando de él hacia fuera si hay un error. Este programa será en última instancia la lista de todos los programas (aunque, "hola mundo" podría tomar un tiempo muy largo para producir). Por lo tanto, tenemos un programa en el que se enumeran todos los programas. El conjunto de todas las máquinas de turing es contable.

Answer 2

Ha visto usted que usted puede codificar máquinas de Turing por números naturales? Esto es hecho en la forma de mostrar que no hay una máquina de Turing universal. de lo contrario, cada máquina es una cadena finita de símbolos de algún alfabeto

Answer 3

Depende de cómo se defina "distintas" en términos de máquinas de turing. En general, dos (una cinta) máquinas de turing no son "distintos" si hay un componente sabio bijection que va de una 7-tupla para el otro 7-tupla.(Ver http://en.wikipedia.org/wiki/Turing_machine#Formal_definition para el 7-tupla a la que me refiero.). Esto conduce a una contables número de máquinas de turing. Si, en cambio, si "distinto" se define de una manera que el 7-tuplas tienen que ser idénticos para no ser "distinto", entonces hay una cantidad no numerable de máquinas de turing. En este caso, no habría un "conjunto" de todas las máquinas de turing, en su lugar, habría una "clase" de todas las máquinas de turing.

Answer 4

Tac-Tics la respuesta es casi correcta, pero el "ingenuo" del programa de argumento es innecesario y posiblemente incorrecta (como por mi comentario).

La observación de que las máquinas de Turing puede ser descrito por finito de cadenas de caracteres de un alfabeto finito es suficiente: mediante la asignación de las letras del alfabeto y los números enteros en algunos de base (por ejemplo, binario o, como Turing no, decimal sin el uso de los dígitos 8 y 9), se pueden asignar todos los programas enteros. Así, el conjunto de todos (válido o no válido)¹ máquinas es asignable a un subconjunto de los números enteros; por lo tanto el conjunto de todas las máquinas y el (menor) conjunto de todos los equipos válidos son contables.

_{1: Por "válidas", me refiero a cualquiera de Turing "círculo-gratis" concepto o equivalente-pero invertida "detener" concepto (que se presenta cuando el trabajo de Turing fue reinterpretada como la "detener el problema").}