Computer Science and Math

Sí, se demostró con cardinalidades entre conjuntos. Hoy voy a hablar de algo que me dejó consternada por un rato. Un día estaba leyendo la demostración, pensé que quizá si hubiera estado con mis compañeros también  hubieran sentido algo al enterarse del resultado... Luego recordé que quizá pensarían en cómo la demostración empoderaría a la clase trabajadora y yo aquí con tonterías pseudotrascendentales. (Facultad de Ciencias, Socialist Icon 💖)  En fin, empecemos.   Problemas de decisión Dentro de la Teoría de la Computación un problema de decisión es aquel donde la salida del algoritmo sólo es Sí o No, 0 o 1, True o False, o algún equivalente Por ejemplo, decidir si una gráfica es conexa o no, es un problema de decisión Supongamos que fuera posible pasar cada una de todas las infinitas gráficas posibles como input al algoritmo. Luego de eso podríamos ver a las infinitas gráficas separadas en dos conjuntos. Definiremos a L como el conjunto que contiene a todos los elemen...

Sean algunos algoritmos Árbol generador de peso mínimo Regresiones Cadena común más larga Page Rank Runge-Kutta Recorrido de un grafo por profundidad (DFS) Y los algoritmos fueron... Sabemos que los algoritmos existen y que la implementación de algunos es sencilla de encontrar en internet. Intuitivamente sabemos que podemos pensar en un algoritmo y con suficiente abstracción podemos implementarlo en algún lenguaje de programación. Un día quizá después de programar suficiente (o no) nacen las preguntas ¿qué algoritmo no puedo programar? ¿existe siquiera alguno que no pueda programar? Tengo este algoritmo ¿es posible programarlo? Dentro de la computación teórica existe el concepto de computabilidad, éste se encarga de estudiar lo anterior. Máquina de Turing (MT) Es una propuesta de Alan Turing hecha en 1936 en su artículo "On computable numbers, with an application to the Entscheidungsproblem", es un modelo teórico de computación en el cual están basadas todas las computadora...