Creo que la pregunta es confusa: las máquinas de Turing (que son un modelo de cálculo) con las máquinas de Turing universales (que aceptan otra máquina de Turing como entrada y la emulan). Si bien el concepto de “opuesto” no está bien definido aquí, podemos Ciertamente, vienen con máquinas que no son UTM.
Absolutamente hay máquinas de Turing que solo hacen una cosa; por ejemplo, una máquina de Turing que reconoce cubos: ¿Cómo podemos diseñar una máquina de Turing que acepte una cadena cuya longitud es un cubo perfecto?
Otro ejemplo de máquinas teóricas que calculan un algoritmo “de la manera más directa” son los circuitos booleanos. Estos se estudian en la complejidad computacional como un modelo de cómputo “no uniforme”; Se necesitan diferentes circuitos para diferentes tamaños de entrada, y cada circuito resuelve un solo problema.
- ¿Podríamos usar la definición de integración de suma de Riemann para obtener las integrales de cualquier función polinómica o trascendental?
- ¿Cuáles son algunos artículos clásicos sobre teoría de grafos?
- Siendo un estudiante de matemáticas BSc sin cursos de computación, ¿cómo puedo aprender codificación para ser competitivo?
- ¿Cuál sería la forma más eficiente de verificar si un número dado es un factorial de algún número o no?
- Dada una matriz que consta de N enteros, ¿puedes encontrar el valor máximo de xor de dos números en una matriz (ai xor aj)?
Formalmente, una máquina Turing acepta algún lenguaje L, un conjunto de cadenas. El “opuesto” de esa máquina de Turing acepta todas las cadenas que no están en L. Es bastante fácil demostrar que ese opuesto no puede ser una máquina de Turing, en general. (En términos formales, el complemento de un conjunto recursivamente enumerable no es necesariamente enumerable recursivamente).
También se podría decir que una máquina que no reconoce ningún idioma es lo opuesto a una máquina de Turing, excepto que es bastante fácil crear una TM que no reconozca ningún idioma.
Una máquina de Turing tiene almacenamiento infinito; una máquina que solo tiene una cantidad finita de almacenamiento (¿lo opuesto?) es una máquina de estado finito (FSM). En realidad, las computadoras son FSM muy grandes, no máquinas de Turing.
