¿Cuál es un ejemplo de un problema empresarial computacionalmente imposible?

17

Tengo un compañero de trabajo que se niega a aceptar la realidad de que las máquinas de Turing (y las máquinas de Von Neuman por extensión) no pueden resolver su propio problema de detención diciendo:

Puedes hacer cualquier cosa con suficiente tiempo y dinero.

Tampoco le gustan los problemas teóricos argumentando que:

En nuestro campo, nunca nos encontraremos con esas preguntas. Somos desarrolladores de aplicaciones, no científicos teóricos.

¿Hay un buen ejemplo de un problema comercial que sea computacionalmente imposible que pueda usar para ayudarlo a convencerlo de esto?

Jesan Fafon
fuente
11
No puedes demostrar con el ejemplo que algo es imposible. Su compañero de trabajo solo dirá "No está funcionando porque no hemos descubierto el enfoque correcto". Lo mejor que puedes hacer es mostrarle una prueba. Si no lo compra, es realmente estúpido o un imbécil o ambos. Aquí hay una lista de problemas indecidibles: en.wikipedia.org/wiki/List_of_undecidable_problems
Thomas Eding
18
A un teórico e ingeniero les dijeron que podían besar a una chica recorriendo repetidamente la distancia entre ellas y ella a la mitad. El teórico inmediatamente dejó de decir "es imposible, nunca llegaré allí". El ingeniero fue a por ello y dijo: "Me acercaré lo suficiente para fines prácticos". Usted, señor, necesita intentar ese beso.
gbjbaanb
2
@gbjbaanb: Ese es un buen descriptor de muchas de las soluciones no óptimas para problemas difíciles de NP, y saber que esos problemas son (prácticamente) imposibles de resolver de manera clásica es la razón por la que opta por el método alternativo. Si no acepta que algunos problemas son prácticamente o literalmente imposibles de resolver, entonces no buscará soluciones imperfectas que puedan dar una respuesta "suficientemente buena" después de un período de tiempo indeterminable.
Phoshi
3
@Phoshi no, el punto es que las soluciones de ingeniería del mundo real solo requieren una solución que sea lo suficientemente buena como para resolver el problema lo suficiente como para ser aceptado. Resolverlo perfectamente no vale la pena el tiempo y el gasto. p.ej. El problema del vendedor ambulante es imposible debido a más de unos pocos nodos, pero muchas empresas aún requieren (y entregan) una solución menos que óptima. Si solo produjéramos la perfección, nadie tendría estos.
gbjbaanb
10
@gbjbaanb: Cierto, pero la única razón por la que resolvieron esos problemas es al aceptar primero que no se puede "hacer nada con suficiente tiempo y dinero" y dejar de buscar la solución óptima. El conocimiento de lo que no puede hacer es a menudo tan importante para encontrar una solución como el conocimiento de lo que puede hacer.
Phoshi

Respuestas:

11

No es técnicamente imposible, pero ...

Programación de recursos , con el objetivo de encontrar la programación ideal que maximice el uso de franjas horarias. Estuve en un proyecto una vez, en mis primeros días de computación, que tenía este requisito. Trabajé en ello un tiempo antes de darme cuenta de que era NP-hard.

Aquí se pueden encontrar otros ejemplos de problemas que no son técnicamente imposibles, pero son técnicamente difíciles .

La mayoría de los problemas informáticos difíciles en la informática empresarial no son imposibles, sino poco prácticos. Tu amigo tiene razón; puedes resolver la mayoría de ellos si les arrojas suficiente dinero. Pero el argumento es engañoso; El objetivo de dirigir un negocio es ganar dinero, no perderlo.

En la práctica diaria, hablamos de la integridad de Turing de una manera vaga, no para demostrar algún principio matemático, sino para ilustrar (por ejemplo) la insuficiencia de HTML y CSS como un vehículo completo para producir programas con funciones completas.

Del mismo modo, el problema de detención es importante para los teóricos, pero no tiene mucha relevancia para la mayoría de las empresas.

Robert Harvey
fuente
14
El problema de detención surge en el análisis estático de código. A partir de esto, puede obtener problemas mundanos como "aquí hay algo de código, haga que se vea bonito" a "aquí hay algo de código, es malware": el primero es importante para las empresas que hacen IDE (resaltado de sintaxis, refactorización), el segundo para empresas antivirus y profesionales de seguridad.
12
"Del mismo modo, el problema de detención es importante para los teóricos, pero no tiene mucha relevancia para la mayoría de las empresas": Bueno, si el problema de detención fuera computable, podríamos verificar automáticamente si un software se va a terminar / colgar. cierta entrada o no. Probablemente ya no tendremos BSOD. Como esto no es posible, tenemos que usar otras técnicas para garantizar la calidad del software (como las pruebas) y nadie está invirtiendo tiempo y dinero para desarrollar un programa general de "verificación de terminación". Así que creo que este resultado teórico tiene una gran relevancia práctica.
Giorgio
4

Otros han comentado sobre esto, pero intentaré escribir una respuesta dando mi punto de vista.

Me gusta la respuesta de Robert Harvey, y los comentarios a su respuesta, y me gustaría ampliarlos.

Creo que debe presentar estos problemas indecidibles (como la terminación) de una manera mundana: por ejemplo, una herramienta IDE que "verifica si esta función siempre devuelve un valor".

Cuando enseñaba, mi ejemplo favorito era la refactorización ( equivalencia de funciones, otro problema indecidible ). Yo pregunté:

¿Cómo verifica si una función / programa hace lo mismo después de su buena refactorización? Claro, tenemos pruebas unitarias para eso, pero no cubren todos los casos. Y son aburridos de escribir ... ¡Pero somos programadores! ¡Deberíamos escribir un programa que verifique si estas dos funciones están produciendo siempre el mismo resultado! ¿Por qué no intentas escribirlo?

o, como una variación tal vez más cercana a su caso:

Tenemos este código heredado escrito en un antiguo y oscuro dialecto COBOL, para el cual no existen especificaciones y / o compiladores. Solo tenemos el programa. Todo nuestro negocio depende de ello, por lo que debemos estar 100% seguros de que el nuevo código Java hace exactamente lo mismo en cada situación. La gerencia quiere un programa que haga eso, verificando todos los casos posibles, y estima que se puede hacer en 6 a 8 semanas. ¿Por qué no intentas escribirlo?

El punto no es escribir tal programa. O una buena aproximación de los requisitos. El punto es darse cuenta de que NO se puede hacer de una manera directa, NO desperdicie innumerables nuestros tratando de descubrir cómo hacerlo (solo para darse cuenta de que no es posible), sino reconocerlo. "¡Ah! ¡Esto es indecidible! No es posible hacerlo directamente. Necesito encontrar una forma diferente y más inteligente de hacerlo, con una aproximación suficientemente buena".

Tienes que encontrar una manera de presentar el problema de una manera reconocible y aparentemente simple. No creería cuántos estudiantes de CS intentarán escribir un programa de este tipo de inmediato ... antes de tomar una clase de computabilidad :)

Lorenzo Dematté
fuente
Su segunda cita intenta invocar el problema de detención incorrectamente; sin embargo, si sabemos que el programa COBOL funciona y podemos ejecutarlo en un entorno de prueba (vm-clone todo PROD si es necesario), el problema de detención se excluye y podemos intentarlo. Probablemente a mano en lugar de por programa, pero de todos modos podemos hacerlo. Podríamos dividir en árbol todas las formas de entrada posibles si es necesario. Debido a que el programa objetivo se detiene, también lo hará la bisección del árbol.
Joshua
2

Suponiendo que podamos dejar de lado las cuestiones morales por el momento:

El Negocio A ha contratado una forma de comunicación entre las oficinas satélite A1 y A2 sin que nadie más que las personas autorizadas en A1 y A2 puedan entender la comunicación.

Business B ha contratado a usted una forma de espiar inteligentemente todas las comunicaciones entre A1 y A2.

Obviamente no puedes hacer las dos cosas.

Debido a la forma en que funcionan las matemáticas (las matemáticas exactas han estado sujetas a una investigación en curso durante 100 años), uno de los siguientes requisitos no puede cumplirse:

(1): Proporcione un algoritmo de cifrado que no pueda ser roto por un atacante con una cantidad arbitraria de dinero disponible.

(2): proporcione un algoritmo de ruptura de cifrado para un algoritmo de cifrado arbitrario que se ejecute en un tiempo razonable.

Joshua
fuente
1
(3): No conseguir otro trabajo después de que el mercado descubra que incluso intentaste ambos
TruthOf42
1

Recientemente tomé una clase sobre Modelo de Procesos de Negocio y Notación ( BPMN ). Allí se puede ver fácilmente que los flujos de trabajo con demasiadas divisiones, uniones y bucles se vuelven rápidamente poco prácticos (aunque no necesariamente imposibles , AFAIK) para comprender y controlar (cuando utiliza demasiadas divisiones OR en lugar de divisiones XOR).

Para la industria del software, creo que lo mismo vale para problemas similares de "cobertura de múltiples condiciones" en el análisis de cobertura de código .

Para un negocio, el camino a seguir es reducir el espacio del problema y no arrojar más recursos al problema complejo. En mi ejemplo, agregue restricciones al flujo de trabajo (o en el análisis de cobertura de código, simplifique el código), en lugar de trabajar duro para encontrar, por ejemplo, N posibles trazas y resultados donde N es un número inimaginablemente grande.

Aparte de eso, creo que hay muchos problemas en el análisis de red / gráfico que son imposibles de resolver (tratando de determinar una topología de red recorriendo iterativamente todos los caminos, etc.).

knb
fuente
0

El ejemplo clásico está tratando de analizar HTML con expresiones regulares . Esto puede funcionar con conjuntos limitados de HTML, pero una solución general es imposible, debido al hecho de que tienen diferentes gramáticas Chomsky (como el enlace deja en claro (ish)).

En términos más generales, a algunas personas no les gusta pensar filosóficamente (como su compañero de trabajo) y no estoy seguro de que pueda discutir para salir de una mentalidad. Su primer punto es ciertamente erróneo, pero el segundo podría ser una forma de decir que no tengo que preocuparme por esto para codificar formularios web para la recepción de productos. Simpatizo con esto, pero a veces conocer la teoría significa que no te comprometes a encontrar el Santo Grial en el tiempo de trabajo.

Alistair Mackenzie
fuente
-6

Quizás la respuesta es que su compañero de trabajo es correcto. ¿Quizás has entendido mal a Turing, o cómo se aplica aquí?

Todas las máquinas son finitas, por lo tanto no hay máquinas de Turing 'reales' ni programas que nunca se detengan. Un programa trivial que ejecuta un bucle infinito simple podría durar 5 minutos o 50 años, pero en una máquina finita se detendrá. También se detendrá un problema no trivial que no se detenga, como 'calcular pi exactamente', porque eventualmente el cálculo excederá la capacidad de almacenar más dígitos.

El resultado de Turing no garantiza nada particularmente útil en máquinas finitas, por lo que su búsqueda es en última instancia infructuosa. Es mejor centrarse en cuánto tiempo y cuánto dinero y dejar infinito a los matemáticos.

Puede pensar que un programa como { while true: print "running"; print "halted"; }es un contraejemplo, pero no lo es. Este programa tiene efectos secundarios, que pueden o no hacer que se detenga. Ignorando los efectos secundarios, es posible idear una prueba formal de que este programa no se detendrá. En esta pregunta solo nos interesan los programas que evaden la prueba formal de no detenerse, donde la cuestión de la detención es indecidible. Este no es un programa así.

Puede ayudar distinguir Turing 'fuerte' de Turing 'débil'. Las máquinas de Turing fuertes son realmente infinitas y, si no se detienen, funcionarán por tiempo infinito. No podemos construir esos.

Las máquinas de Turing débiles tienen límites finitos de tiempo y espacio, y son el único tipo que podemos construir. Estamos interesados ​​en programas que no se puede demostrar que se detengan dentro de esos límites. Turing nos dice que existen tales programas, pero no podemos identificarlos. Si los límites son lo suficientemente bajos, podemos identificarlos escribiendo el programa y ejecutándolo hasta sus límites.

La esencia de Turing es que no hay atajos. La única manera de estar seguro de si un problema es computacionalmente factible es escribir el programa, ejecutarlo y averiguarlo. Con suficiente tiempo y dinero puede escribir todos los programas, ejecutarlos para siempre y con el tiempo, y encontrar los que producen resultados (los cabestros). Los otros seguirán corriendo. ¿Tiene un compañero de trabajo suficiente tiempo y dinero para hacer eso?

En serio, sin embargo, la disputa se trata de límites. Turing y NP complete nos dicen que ciertas clases de problemas no pueden ser resueltas por computadoras dentro de un presupuesto dado o en un horario dado, sin importar cuán grande sea ese presupuesto o cuán generoso sea ese horario. Abundan ejemplos de ese tipo de problemas: romper claves criptográficas; optimizar las rutas para realizar entregas a cientos de direcciones; cajas de embalaje en camiones; ¡Encontrar errores en programas grandes!

Por lo tanto, solicite a su compañero de trabajo un presupuesto y un cronograma, y ​​haga una promesa de que puede producir un problema que no puede resolverse dentro de ese presupuesto o cronograma. Esa promesa será muy fácil de cumplir.

david.pfx
fuente
2
La esencia del problema de detención es que hay clases de problemas que no se pueden calcular, incluso con tiempo y dinero infinitos. Eso es lo que mi compañero de trabajo se niega a aceptar.
Jesan Fafon
Entonces no estamos de acuerdo. He editado mi respuesta, pero esencialmente el mensaje es el mismo. Su pregunta tal como se plantea no tiene una respuesta (o no una que le guste), pero subyacente es un problema real y un punto real que debe hacerse. Si quiere ganar este argumento, tendrá que cambiar un poco el terreno, y he tratado de proporcionarle ayuda para hacerlo. [Recuérdame que no intente responder preguntas como esta otra vez; los votos negativos no son bienvenidos.]
david.pfx
2
@simon: a riesgo de repetirme, no hay programas que tarden una cantidad infinita de tiempo en completarse porque no hay computadoras Turing completas, solo aproximaciones finitas a ellas. No puede probar que un programa arbitrario se completará en un período de tiempo determinado por un método que sea más rápido que ejecutar el programa. En la práctica, cualquier oración con la palabra 'infinito' corre el riesgo de no tener sentido.
david.pfx
3
while True: print "doing stuff"; print "Finished"; Ese es un ejemplo de un programa que tarda una cantidad infinita de tiempo en finalizar. Hay una cantidad infinita de otros programas que también tardan una cantidad infinita de tiempo en completarse. Regularmente creamos programas que toman una cantidad infinita de tiempo para completar a propósito. Se llaman 'procesos de larga ejecución'. La mayoría de los sitios web dinámicos son ejemplos de uno.
Singletoned
2
El punto es seguramente que hay conjuntos de programas de computadora que son efectivamente infinitos, nunca se detendrán bajo su propio vapor (eventualmente presionaremos break, desconectaremos la alimentación, etc.), si los programamos en una máquina Turing, lo haría correr sin parar. La esencia del problema de detención es que no hay forma práctica o teórica de determinar los programas que no se detienen en absoluto algorítmicamente.
Alistair Mackenzie