He leído que inicialmente Church propuso el cálculo como parte de su artículo Postulados de lógica (que es una lectura densa). Pero Kleene demostró que su "sistema" era inconsistente, después de lo cual Church extrajo cosas relevantes para su trabajo sobre "computabilidad efectiva" y abandonó su...
Algoritmo de Karatsuba para la multiplicación rápida se publicó por primera vez en A. Karatsuba y Yu. Ofman (1962), "Multiplicación de muchos números digitales por computadoras automáticas", Actas de la Academia de Ciencias de la URSS 145: 293–294. Según Karatsuba (1995, "La complejidad de los...
Tengo dos preguntas históricas: ¿Quién describió por primera vez el cálculo no determinista? Sé que Cook describió problemas NP-completos, y que Edmonds propuso que los algoritmos P son algoritmos "eficientes" o "buenos". Busqué en este artículo de Wikipedia y hojeé "Sobre la complejidad...
Según el relato histórico (no verificado), Kolmogorov pensó que cada lenguaje en PP\mathsf{P} tiene una complejidad de circuito lineal. (Vea la pregunta anterior conjetura de Kolmogorov que PPP tiene circuitos de tamaño lineal .) Tenga en cuenta que esto implica P≠NPP≠NP\mathsf{P}\neq \mathsf{NP}...
Hace poco tuve una discusión sobre las máquinas de Turing cuando me preguntaron: "¿La máquina de Turing se deriva de autómatas o es al revés"? No sabía la respuesta, por supuesto, pero tengo curiosidad por averiguarlo. La máquina de Turing es básicamente una versión un poco más sofisticada de un...
Hoy enseñé los límites inferiores de , y uno de los estudiantes preguntó por la razón del nombre . La explicación oficial es que la "A" significa "Alternancia".A C0 0AC0AC^0A CACAC Recuerdo vagamente que me dijeron hace muchos años que Nick Pippenger Steve Cook nombró a después de Nick Pippenger...
Al tratar de convencer a los economistas de la relevancia de la teoría de la complejidad en forma impresa, ¿hay alguna referencia estándar para citar? Estoy familiarizado con la publicación del blog de Noam Nisan , la encuesta de Tim Roughgarden y el capítulo 11 del ensayo de Scott Aaronson . Estas...
¿Existen casos interesantes de algoritmos que se hayan publicado con límites probados y donde se hayan publicado límites estrictamente mejores más adelante? No mejores algoritmos con mejores límites, ¡obviamente eso ha sucedido! Pero un mejor análisis conduce a un mejor límite en un algoritmo...
Estoy interesado en la historia temprana de los resultados publicados sobre compensaciones de espacio-tiempo de propósito general. En particular, quiero saber quién describió por primera vez el siguiente tipo de algoritmo para evaluar un cálculo que tiene un gráfico de flujo de datos arbitrario con...
¿Quién introdujo la idea de recursión ? ¿Alguien puede explicar de dónde vino y cómo impactó la
Robin Milner definió bigraphs como un tipo de estructura gráfica con una estructura similar a un gráfico, pero donde los nodos se pueden anidar. Generalizan cálculos de procesos como CCS y el cálculo , pero Milner parece haber tenido la intención de que se usen de manera mucho más general: las...
Mientras enseñaba cómo implementar FSMs utilizando circuitos lógicos sincrónicos, noté una coincidencia intrigante: tanto en el mundo teórico de CS como en el mundo de la ingeniería eléctrica, el "estado" se denota típicamente (y el espacio de estado ). Primero pregunté sobre EESX , pero luego,...
Para celebrar el cumpleaños número 100 de Alan Turing, quiero ver un documental sobre su vida. Sin embargo, hay varios documentales para elegir. ¿Qué documental sobre Alan Turing es tu favorito? Incluya solo un documental por
Me gustaría saber sobre la historia de estos dos términos: " eficiente ", " factible ". ¿Quién los usó sobre computación / algoritmos la primera vez? (en el sentido moderno de estos términos, es decir, siglo XX). ¿Cómo se convirtieron en la corriente principal? ¿Cómo comenzaron a usarse estos dos...
Busco: Michael O. Rabin, "Grado de dificultad para calcular una función y un ordenamiento parcial de conjuntos recursivos", Universidad Hebrea, Jerusalén, 1960 Resumen: “Intentamos medir la cantidad de trabajo inherente a la tarea de calcular una determinada función computable (recursiva)....
Los idiomas Dyck se definen mediante la siguiente gramática S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) sobre el conjunto de símbolos { ( 1 , ... , ( k , ) 1 , ... , ) k } . Intuitivamente, los idiomas Dyck son los idiomas de paréntesis equilibrados de k tipos diferentes. Por ejemplo,...
He estado tratando de entender qué, por qué y cómo del cálculo pero no puedo entender "¿por qué funciona?"λλ\lambda "Intuitivamente" obtengo el modelo de computabilidad de Turing Machines (TM). Pero esta abstracción me deja confundido.λλ\lambda Supongamos que las TM no existen; entonces, ¿cómo...
Todos los museos y exposiciones relacionados con la informática que conozco parecen abarcar solo la historia de la maquinaria informática, pero nada sobre temas de informática. Usted está involucrado en la creación de un nuevo Museo de Computación, creado para educar, entretener e inspirar al...
Es bien sabido que la máquina analítica de Charles Babbage tenía una arquitectura que se parecía mucho a la arquitectura moderna de Von Neumann. Además, es notable que las tablas para representar un programa para la máquina analítica de Babbage ( http://www.fourmilab.ch/babbage/figures/menat3.png...
(Disculpas si esto está fuera de lugar o es demasiado amplio. Estoy abierto a sugerencias sobre cómo reformularlo). Estoy interesado en rastrear la historia "antigua" de los algoritmos de flujo máximo y los algoritmos de optimización discretos en general. Ford-Fulkerson es mi hombre de paja como...