Esto está inspirado en esta pregunta. Sea la colección de todos los combinadores que solo tienen dos variables ligadas. ¿ C es combinatoriamente completa?CC\mathcal{C}CC\mathcal{C} Creo que la respuesta es negativa, sin embargo, no pude encontrar una referencia para esto. También me interesarían...
Considere el siguiente juego de 2 jugadores: La naturaleza elige un programa al azar Cada jugador juega un número en [0, infinito] inclusive en respuesta al movimiento de la naturaleza Tome el mínimo de los números de los jugadores y ejecute el programa durante (hasta) tantos pasos (a menos que...
El siguiente término λ, aquí en forma normal: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implementa un algoritmo de clasificación para listas codificadas por la iglesia. Es decir, el...
Hace unos años, me encontré con la siguiente regla de la izquierda para la igualdad en el cálculo posterior: s ≐ t ⇝ θθ ( Γ ) ⊢ θ ( C)Γ , s ≐ t ⊢ Cs≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢C \frac{s \doteq t \leadsto \theta \qquad \theta(\Gamma) \vdash \theta(C)} {\Gamma, s \doteq t \vdash C} Aquí, s ≐ t ⇝ θs≐t⇝θs...
En el papel clásico de cálculo de construcciones hay una regla que establece (página 7 del pdf, página 101 del documento original) Esta regla significaría que cualquier contexto es reducible a un miembro de ese contexto. Parece que esto no debería ser correcto, ya que implicaría 1 ≅ Nat 3 ≅...
La teoría de tipo constructivo con su interpretación básica bajo la correspondencia de curry howard consiste solo en funciones totales y computables. En la literatura, se ha dicho algo sobre el uso de la "teoría del tipo computacional" para representar la no terminación en los programas...
Estoy buscando referencias sobre la complejidad del problema de equilibrio de la fórmula booleana . En particular, ¿Se sabía que las fórmulas booleanas se pueden equilibrar en ?AC0AC0\mathsf{AC^0} ¿Hay alguna prueba simple de que el equilibrio de la fórmula booleana esté en...
En una charla de Razborov, se publica una pequeña y curiosa declaración. Si FACTORING es difícil, entonces el pequeño teorema de Fermat no es demostrable en S12S21S_{2}^{1} . ¿Qué es S12S21S_{2}^{1} y por qué las pruebas actuales no están en S12S21S_{2}^{1} ?
En Complexity Zoo, dice [ 1 ] que, en complejidad descriptiva, PAGPAGP puede definirse mediante tres tipos diferentes de fórmulas, FO ( L FPAG)FO(LFPAG)FO(LFP) que también es FO ( nO ( 1 ))FO(norteO(1))FO(n^{O(1)}) , y también como SO ( HO R N)SO(HORnorte)SO(HORN) . Sin embargo, hay algunas...
Es un hecho bastante conocido que derivar una contradicción de una desigualdad (por ejemplo, ) en la teoría de tipo Martin-Loef requiere un universo.( 0 = 1 ) → ⊥(0=1)→⊥(0=1) \to \bot La prueba también es bastante sencilla: en ausencia de universos, podemos borrar las dependencias de cualquier...
Cerrado. Esta pregunta está fuera de tema . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que sea sobre el tema para el intercambio teórico de pila de informática. Cerrado hace 3 años . ¿Existe...
Estoy tratando de entender los conceptos de tipos universales y existenciales, pero en todas partes veo intuiciones lógicas u operativas (o implementaciones) (por ejemplo, el libro TAPL de B. Pierce), que, bueno ... es bueno , pero me gustaría ver las definiciones (donde las vemos como conjuntos),...
El teorema de PCP establece que cada problema de decisión en NP tiene pruebas probabilísticamente comprobables (o de manera equivalente, que existe un sistema de prueba completo y cuasi-sonoro para teoremas en NP que usa complejidad de consulta constante y logarítmicamente muchos bits...
En el contexto de algunos trabajos recientes , hemos estado definiendo un lenguaje basado en una lógica de tres valores à la Kleene, donde significa verdadero, para falso y para error o no sabe. Para demostrar que nuestro lenguaje era expresivo, queríamos demostrar que podíamos construir un...
Mi pregunta es acerca de la teoría del modelo finito / complejidad descriptiva, por lo que significará "primer orden sobre palabras binarias finitas, usando predicados Rs y un predicado unario P verdadero en la posición del 1 en la palabra".FO(R)FO(R)FO(R) Me gustaría saber, ¿hay alguna...
Los functores construidos a partir de productos finitos y sumas tienen cierre ordinal , que se detalla muy bien en este manuscrito de Francois Metayer. es decir, podemos alcanzar el tipo inductivo iterando el functor , que alcanza su punto fijo después de las iteraciones
Estoy tratando de entender el documento sobre p-Optimal Proof Systems and Logic para PTIME . Hay una noción llamada sistemas de prueba en el documento y no entiendo: Σ={0,1}Σ={0 0,1}\Sigma = \{0,1\} ... Identificamos problemas con subconjuntos deQQQ enΣ∗Σ∗\Sigma^* . Creo que la intuición es...
Para comprender mejor un artículo, estoy tratando de obtener una breve comprensión de la lógica de punto menos fijo. Hay algunos puntos donde estoy atrapado. Si G = ( V, E)sol=(V,mi)G = (V,E) es un gráfico y Φ ( P) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a ,...
Supongamos que no conocemos el resultado de Joe B. Wells de 1994 de que tanto la tipificación como la verificación de tipo son indecidibles en el Sistema F (AKA ). En los cálculos Lambda con tipos de Barendregt (1992) encontré una prueba debido a Malecki 1989 de que la verificación de tipos implica...
es bien sabido que el cálculo μ modalμμ\mu es una de las lógicas temporales más expresivas para expresar las propiedades de los árboles / gráficos, y que CTL * es estrictamente menos expresivo que el cálculo .μμ\mu Aquí me gustaría pedir un ejemplo de fórmula de cálculo , tan simple como sea...