Debo admitir que me resulta difícil imaginar por qué la adición se consideraría difícil de implementar, pero tal vez soy parcial.
Se puede diseñar fácilmente una máquina de Turing que agregue números naturales representados en notación unaria. Para calcular [matemática] m + n [/ matemática], la entrada debe ser [matemática] m [/ matemática] escrita en unario (esta es una cadena de [matemática] m + 1 [/ matemática] [matemática] 1 [/ math] s) seguido de un espacio en blanco seguido de [math] n [/ math] escrito en unario (esta es una cadena de [math] n + 1 [/ math] [math] 1 [/ math] s). El sumador reemplaza el espacio en blanco por [matemática] 1 [/ matemática] y elimina la [matemática] 1 [/ matemática] más a la derecha.
Por supuesto, también se pueden agregar números naturales representados en la base 10; simplemente use el algoritmo de suma estándar que se enseña en la escuela. La implementación de la máquina Turing lleva a cabo la adición de dígitos individuales directamente usando la función de transición y usa el estado para almacenar el transporte.
- ¿Por qué necesitamos saber cálculo en informática?
- Cómo convertir una combinación dada a un solo número
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
- ¿Cuál es la complejidad temporal de T (n) = T (n / a) + T (n / b) + cn cuando 1 / a + 1 / b> 1? Por ejemplo T (18n / 20) + T (5n / 20) + n.
- ¿Qué problemas abiertos en matemáticas tendrían aplicaciones prácticas inmediatas si se resolvieran?
¿Por qué se acepta generalmente la tesis de Church-Turing? Una muy buena razón para aceptarlo es que se puede demostrar que todos los lenguajes de programación conocidos son tan poderosos como el simple modelo de máquina de Turing. Otra es que aún nadie ha sido capaz de encontrar un algoritmo que satisfaga nuestra intuición habitual de lo que constituye un algoritmo pero que no puede implementarse.
