¿Cuál es la diferencia entre problemas decidibles e indecidibles en teoría de la computación?

Un problema es una pregunta de sí / no sobre una entrada dada. Por ejemplo, dado un número entero positivo, ¿es par? O, dada una cadena de ceros y unos, ¿es un palíndromo?

Si puede encontrar una forma sistemática (un algoritmo) para responder la pregunta correctamente, entonces el problema se llama decidible. De lo contrario, es indecidible .

Los problemas indecidibles tienden a ser bastante difíciles, por lo que no suele pensar en un ejemplo de la cabeza. Algunos ejemplos básicos son preguntas sobre programas y lo que pueden calcular. Por ejemplo, dado un programa Java que toma entradas enteras y tiene una salida booleana, ¿siempre da salida a verdadero ? Muchos ejemplos “geniales” están relacionados con este sencillo ejemplo. Por ejemplo, dadas dos matrices booleanas finitas que representan configuraciones en Conway’s Game of Life, ¿puedes alcanzar una configuración a partir de la otra? O, dado un programa y una entrada a ese programa, ¿se ejecutará el programa sin caer en un bucle infinito?

En cada problema indecidible, no hay “gancho” para obtener una respuesta. Lo mejor que puede hacer es probar un número infinito de posibilidades. A veces, eso es suficiente para obtener una respuesta parcial. Por ejemplo, para responder a la pregunta sobre si un programa ejecuta un bucle infinito libre en un entero dado, uno simplemente puede ejecutar el programa. Si se ejecuta para siempre, no sabemos lo que está sucediendo, pero si se detiene y genera una respuesta, entonces lo sabemos. Problemas como este, donde podemos resolver la mitad del problema, se conocen como parcialmente decidibles. Es decir, si podemos responder sí cuando la respuesta es sí, entonces es parcialmente decidible.

Hay problemas que ni siquiera son parcialmente decidibles, como:

¿Un programa Java dado con entrada entera y salida booleana dice verdadero exactamente a un entero?

En este caso, prueba omitida, ninguna simulación garantizará un sí o un no.

Hay una serie de teoremas útiles sobre los tipos de preguntas sobre programas que son indecidibles y no parcialmente decidibles. Cualquier pregunta “no trivial” sobre el cálculo de un programa es indecidible. Una pregunta no trivial es una que a veces es verdadera y a veces falsa. Por ejemplo, dado que algunos programas se ejecutan sin bucle infinito en una entrada determinada y otros no, la cuestión general de si un programa se ejecuta sin bucle infinito en una entrada determinada es indecidible. Por otro lado, una pregunta trivial podría ser: ¿se ejecuta un programa determinado durante al menos un paso en una entrada determinada? La respuesta siempre es “sí”, por lo que es trivialmente decidible.

El teorema correspondiente para el cual las preguntas sobre programas ni siquiera son decidibles parcialmente es más complejo y tiene condiciones más estrictas.

Se dice que un problema es decidible si siempre puede responderlo con “sí” o “no”.

Por ejemplo,

“¿Comiste?” “¿Tienes un bolígrafo?” “¿Tu trabajo está hecho?”

Siempre puede responder “sí” o “no” para tales preguntas.

Tales problemas son lo que llamamos decidibles o, en otras palabras, los llamamos “solucionables”. De lo contrario, se dice que la clase de problemas es “indecidible” o “insoluble”.

Para ser más precisos con el tema, se dice que un problema es decidible si alguna máquina de Turing decide o resuelve con SÍ o NO para cada caso del problema.

De lo contrario, el problema es indecidible.

La teoría de la informática tiene cierta terminología formal utilizada para clasificar los problemas en función de su nivel de dificultad.

El término “indecidible” se utiliza para referirse a aquellos problemas que han demostrado ser irresolubles. Como se puede adivinar, si un problema aún no se resuelve, no significa que sea indecidible, a menos que se pruebe su indecidibilidad.

Conocer la indecidibilidad de un problema prácticamente lo resuelve y no es necesario poner más esfuerzos en esa dirección.

Para un problema dado, aún no resuelto, puede ir en cualquier dirección según su intuición,

(1) probar que es indecidible, o

(2) encuentre la solución / respuesta

En el momento en que uno de los anteriores está hecho, se elimina la necesidad de otro. También existen problemas sin resolver que se cree que son indecidibles sin pruebas.

La cantidad de cómputo utiliza modelos informáticos abstractos para definir con precisión las cosas sobre la indecidibilidad. Sin embargo, en la descripción anterior, quería presentar una presentación intuitiva e informal de la misma para una audiencia más amplia.

La forma en que se define en el cálculo, es algo así como la variación entre 0 y 1 (probabilidad binaria).

Por ejemplo, si algo requiere intentos infinitos, o no genera 0 o 1 (no o sí), entonces todavía hay alguna probabilidad de que se dé una respuesta diferente, por lo que la situación es indecidible.

En estadística, los modelos de Chi cuadrado y las curvas de campana, etc., se usan para indicar dónde se encuentra un dato hasta determinar la probabilidad. Sin embargo, tales datos, en cuanto a alcanzar el poder de causalidad, son relativos a menos que se expresen como probabilidad, y la probabilidad en sí misma está sujeta a la falacia filosófica de la inducción, que dice que nunca podemos saber nada absoluto a través de la probabilidad, particularmente cuando las opciones permanecen abiertas. Una ilustración simple es que si la probabilidad de encontrar un restaurante extraño en un desierto fuera una cuestión de la cantidad de veces que el restaurante extraño aparece en un área cuadrada particular del espacio dentro del desierto, entonces la probabilidad de encontrar el restaurante podría ser 1 / dieciséis. Pero para la percepción humana, si algo ocupa un 1/16 del espacio completo, será necesariamente fácil de encontrar, por lo que la única razón para no encontrar el restaurante será si no queremos ir allí o no podemos pagarlo, etc. Entonces, en la práctica, el comportamiento humano se trata más de la racionalidad, la necesidad y lo intrascendente que de la probabilidad. Entonces, la probabilidad de que el restaurante tome 1/16 del desierto realmente no nos dice nada acerca de la probabilidad de usar el restaurante, a menos que nos preguntemos acerca de muchas personas con comportamiento típico que siempre están deambulando por el desierto (eso es , tienen preferencia por el desierto de antemano), y luego tenemos que hacer una encuesta y determinar cuánto les gusta el restaurante, y luego ajustar la cantidad de personas que no tienen ganas de caminar 48 pies o lo que sea. Entonces se trata de la especialización en la que determinas las matemáticas de caminar 48 pies. Mira, el modelo de probabilidad es excelente para crear especialidades muy limitadas que resuelven problemas matemáticos muy específicos, como viajar a Marte, o la probabilidad de que conozcas a alguien en un grupo de personas que conoces, etc.

Muchos de esos problemas individuales son decidibles en términos de probabilidad, pero no muchos de ellos generan una respuesta de ‘sí o no’ (0 o 1). Sin embargo, algunos de los datos son sí o no, porque ya no son datos dinámicos, por lo que al menos sabemos que se dice que ciertos datos en particular son exactos cuando se registraron de manera confiable en algún momento de la historia reciente. Sin embargo, algunos de estos datos se registran como probabilidad, lo que lo hace más confuso. Este tipo de datos probabilísticos (si de hecho son datos probabilísticos: no debemos suponer que es 100% de probabilidad) puede darnos estimaciones basadas en la probabilidad, pero una vez más está sujeto a la falacia de la inducción, lo que significa que no y no puede proporcionar la verdad filosófica, a menos que hagamos suposiciones sobre lo que es verdad y lo que no, porque a menudo hay casos atípicos que no han sido estudiados.

Si queremos la verdad filosófica, queremos que nuestros datos sean completos, lo cual es solo una palabra débil para coherente y absoluto. Bueno, lo absoluto sale por la ventana de inmediato, porque hay detalles como que las cosas no son energía absoluta, al menos, no energía infinita. Entonces, a menudo lo que la gente entiende por absoluto es simplemente que “algo existe”. Pero, desafortunadamente, en filosofía, hay dudas al respecto. Uno puede imaginar que uno está siendo engañado por un científico malvado, o que es una mota de polvo, y Dios está contando una historia complicada para mantenerlo entretenido, y así sucesivamente. Por lo general, no tenemos una historia de fondo compleja para explicar exactamente lo que estaba sucediendo. E incluso si lo fuéramos, aún podríamos no saber si era cierto o no. Entonces, no sabemos qué ilusión es verdadera, por lo que ciertamente no sabemos qué realidad es verdadera, por lo que no sabemos, si algo existe, en qué sentido existe. Y así, no sabemos realmente qué es verdad filosófica o absolutamente, excepto a través de A) un argumento sobre lo que es verdad, o B) una simple declaración sobre lo que existe. Pero, por razones que he explicado, una declaración simple es muy difícil de construir que realmente daría una idea exhaustiva de lo que existe. Y también, puede ser difícil probar lo que existe con un argumento, porque los sentidos pueden ser engañados, o podemos depender de algún detalle específico más de lo que deberíamos, o por el contrario, puede haber algún detalle que sea más importante que otros detalles, y por eso también es difícil construir la verdad con argumentos.

En filosofía, entonces, lo que es verdaderamente integral es una cuestión de lo que es categóricamente exclusivo, a lo que solo se puede llegar mediante la adopción de supuestos sobre lo que es verdad. Si lo que se presenta realmente expresa categóricamente todo lo que es real (incluso si por alguna calificación que se contextualiza por suposiciones y realmente no se aplica a todos los casos), entonces no está sujeto a la falacia de la inducción porque realmente está presentando todo datos, aunque solo sea en un sentido calificado. La cuestión de la verdad pasa luego a la usabilidad, que es la cuestión de si el uso de categorías presenta algo que proporciona un conocimiento útil sobre todo en el mundo. En muchos casos, todas las categorías dirán que lo que se presentó ‘es todo’ (por ejemplo, la palabra ‘todo’) o ‘bajo ciertas calificaciones, todo se comporta de esta manera’ (como un modelo de física complicado que requeriría cálculo y quizás la probabilidad de saber realmente lo que está sucediendo y, por lo tanto, si usa la probabilidad, puede estar sujeto a la falacia de la inducción una vez más). Estos métodos que acabo de mencionar en realidad no pasan la usabilidad desde un punto de vista filosófico, porque no nos dicen qué es, en última instancia, coherentemente cierto acerca de todo. Si algo se comporta de cierta manera, aún necesitamos saber qué significa eso en el contexto de todo lo demás, y si no lo sabemos, entonces falta algo, y si falta algo, entonces no es coherente. Y así, la tercera medida de la verdad exitosa es la coherencia, lo que significa tratar todos los datos de la misma manera sin dejar de expresar todas las propiedades de los datos. En este punto, es como una gran teoría unificada o teoría de todo lo que es necesario, pero también podemos querer obtener verdades filosóficas de los datos, por lo que lo que se necesita es complejidad. La complejidad nos permite medir el nivel de detalle de los datos, y esto puede requerir aceptar limitaciones o grados de coherencia para asegurarnos de que la fórmula de datos diga algo sobre todos los datos.

Entonces, si los datos son Completos → Exclusivos → (Con supuestos adecuados) → Útiles → Coherentes (tratando los datos de la misma manera mientras aún expresa todas las propiedades de los datos) → Complejos (proporciona al menos un grado de conocimiento de los datos) …

Entonces eso es lo que se entiende por resultados concluyentes en filosofía. Si se proporciona todo esto, podemos pasar a las dimensiones y la estética.

Aquí está el sistema único que he encontrado que puede manejar datos coherentes de una manera justa y equilibrada: deducción categórica

…

Enlaces de ciencia de datos

Se dice que un problema de decisión es decidible si es posible construir una máquina de Turing que se detenga en un tiempo finito dando la respuesta correcta (sí o no) para todas las entradas. En otras palabras, si es posible enmarcar un algoritmo que dé la solución correcta a un problema de decisión, el problema es decidible.

Para un problema indecidible, se sabe que enmarcar este tipo de algoritmo es imposible.

Por lo que puedo deducir, parece estar definido por la perspectiva de la naturaleza derivada de cómo funciona una máquina de Turing.

La dinámica inherente de la derivación derivada para intentar explicar si el “punto alcanzado se alcanza o no” parece ser de una estatura similar al manejo de un estado booleano en sí mismo.

Ahora, el problema inherente que siento es el hecho de la ambigüedad. Eso, solo se puede alcanzar mediante un conjunto de distinción a la que nos estamos haciendo, fuera del enfoque algorítmico real.

En lo que, creo, hace que el modelo sea ligeramente defectuoso.

No inutilizable, pero defectuoso.

Entonces, las diferencias que surgen, en términos de decidible e indecidible, son justas, si puede diferenciar el estado real del resultado en términos del estado desencadenado del estado de la máquina de Turing.

En cierto sentido, usted está hablando de los estados de Entropía en términos de tasas de convergencia a las cuales, “¿Cuándo llegaremos a un punto de ser capaces de saber, y vamos a ser capaces de hacerlo”?

Y, en última instancia, tal vez, con alguien capacitado en eso, pueden diferir entre los dos muy rápidamente; pueden diferenciarse en términos de cómo son los diferentes derivados y con qué trabajan.

Es similar a decir eso, encontrar algún sentido de implicar lógica booleana vinculada a ella o estatura derivada.

Me recuerda mucho a la teoría de conjuntos, en cierto sentido, ya sabes.

Es muy, binario antes del punto de donde no está.

Solo es incierto hasta que sea seguro. Al menos, suponiendo que es una interacción válida en términos de descripción del conjunto.

Si no lo es, como en, no es un conjunto válido de descripciones, a lo que no existe un límite superior de certeza al que pueda derivar inherentemente … No hay un techo con el que tropezarse, por así decirlo …

Bueno, entonces la incertidumbre se convierte en una certeza.

Entonces, la diferencia es que parece ser la estatura inherente del límite superior y la accesibilidad en términos del estado de activación.

Similar a, cuándo ocurre, puede ocurrir.

Sin embargo, no es tanto por qué, como ya se dijo, parece que no hay una cobertura algorítmica y un enfoque para definir esta perspectiva de antemano.

Un conjunto es decidible si hay una máquina de Turing (o algoritmo) que responde Sí para cada elemento del conjunto y No para cada elemento que no está en el conjunto. Para un conjunto indecidible, no existe tal máquina / algoritmo de Turing.

Un problema decidible es un problema para el cual hay un algoritmo que se ejecuta en un tiempo finito y siempre da la respuesta correcta de sí / no.

Hay muchos problemas indecidibles, el más famoso es el problema de detención, que pregunta si hay un algoritmo que pueda decidir si un algoritmo determinado se detendrá en una entrada en particular. Un boceto de la prueba de su indecidibilidad está disponible en Wikipedia Detener el problema – Wikipedia

El problema decidible es uno para el que podemos diseñar un algoritmo (no importa si es tiempo polinómico o no).

Mientras que para un problema indecidible no podemos dar un algoritmo. Uno de los famosos problemas indecidibles es el problema de detención de la máquina de Turing .

Nota: Tanto el problema P como el NP caen en la categoría de problema decidible. He visto a muchas personas que piensan que NP cae en un conjunto de problemas indecidibles. lo cual está completamente mal. vea este enlace NP (complejidad) – Wikipedia para más detalles.