Las máquinas Turing trabajan en secuencias de símbolos escritos en su cinta. Dependiendo del alfabeto que utilice una máquina Turing, estas secuencias de símbolos pueden representar varias entradas y ...Las máquinas Turing trabajan en secuencias de símbolos escritos en su cinta. Dependiendo del alfabeto que utilice una máquina Turing, estas secuencias de símbolos pueden representar varias entradas y salidas. De particular interés, por supuesto, son las máquinas Turing que computan funciones aritméticas, es decir, funciones de números naturales. Una forma sencilla de representar números enteros positivos es codificándolos como secuencias de un solo símbolo1.
