20/04/2019, 05:57:58 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
  Mostrar Mensajes
Páginas: [1] 2 3 ... 18
1  Matemática / Lógica / Re: "La no demostrabilidad (~Bew(#~Bew(w)) ) no es una prueba" es demostrable en PA : 08/01/2019, 11:50:46 pm
Estimado geómetracat,

entiendo perfectamente todo lo que dices, e incluso puedo coincidir en lo de las "razones estúpidas", porque las demostraciones pueden obtenerse sin más que aplicar mecánicamente las definiciones.

Usé la notación original de Gödel, con citas de páginas y notas al pie, y esto puede parecer pedante. Pero en un tema tan controversial es preferible que la notación no sea un tema de debate. Por otra parte, encuentro que esa notación está aclarada, si hay alguna duda, hasta en sus más mínimos detalles, por las conferencias en Princeton de 1934, y por toda la literatura que se ha generado sobre ella.

El salto de [texx]Bw[/texx] a [texx]Bew[/texx] es más complicado, y tal vez sea necesario desarrollar una demostración paso a paso.

Intentaré ser más explícito la próxima semana.

Saludos

2  Matemática / Lógica / "La no demostrabilidad (~Bew(#~Bew(w)) ) no es una prueba" es demostrable en PA : 08/01/2019, 02:58:30 am
Estimados, les invito a una sesión en Academia.edu

Resumen
La noción de fórmula bien formada es fundamental para los sistemas formales. El sistema de Gödel tiene una definición para ella. Sin embargo, si el argumento de la fórmula que la expresa es el número de ella misma, vale lo mismo cuando el argumento del argumento es una fórmula bien formada que para una cadena al azar. Es decir, usando la cita en lugar de la numeración, EsFormula ("EsFormula (x)") siempre es verdadera, para cualquier valor de x. Esto trae impensadas consecuencias.


https://www.academia.edu/s/ab6beae46c/malformaciones-encriptadaa-tras-los-numeros-de-godelpdf?source=link
3  Matemática / Lógica / Re: NP-Completitud en cuestión: proc lineal resuelve satisfacibilidad booleana. : 23/08/2018, 05:51:29 pm
4  Matemática / Lógica / NP-Completitud en cuestión: proc lineal resuelve satisfacibilidad booleana. : 22/08/2018, 02:10:33 am
https://www.academia.edu/s/da61caba7e/linear-sat-decider-np-completeness-in-question?source=link

Usa una técnica ya usada en los algoritmos DPLL (Davis-Putnam-Logemann-Lovelandes), el backtracking.
La diferencia es que lo usa desde el comienzo, no cuando surge un conflicto. Y cuando surge un conflicto no hay disparadas exponenciales (exponencial throws), al parecer.
Puede ser que sea útil en la práctica, aún si no resuelve del todo el problema teórico. Pues si hay alguna incorrección detectable, tal que se pueda acotar su alcance de antemano, o alguna disparada exponencial, también acotable, sería útil para la industris.

Saludos.

5  Matemática / Lógica / Re: Teorema de Gödel : 04/04/2017, 08:52:53 pm
Primero construye una fórmula abierta, que interpretada en castellano sería:

G(x): "La sustitución de la variable 'x' en el número de fórmula x no es demostrable."

Luego efectúa la sustitución de la variable libre (la x que no tiene comillas simples) por el número de Gödel de G(x).

G: "La sustitución de la variable 'x' en el número de fórmula #G(x) no es demostrable."

El resultado es un enunciado del meta lenguaje que tiene como argumento otro enunciado del meta lenguaje. No hay ningún enunciado del lenguje objeto, el básico, compuesto sólo de ecuaciones diofánticas eventualmente cuantificadas, o una combinación booleana de ellas.

Es un enunciado vacío. Su argumento es una operación (instanciación de variable) con el número de una fórmula abierta como argumento. Por supuesto es indemostrable, porque depende de la demostración de G(x).

Como G(x) es una fórmula abierta, sólo sería demostrable si se pudiera aplicar la regla de generalización.






6  Matemática / Lógica / Re: Teorema de Gödel : 04/04/2017, 08:45:41 pm
Como cualquiera puede comprobar en la demostración que hace Gustavo, el enunciado G no tiene ningún número de Gödel de una sentencia básica. Son todas sentencias del metalenguaje interno.

El final de la demostración.

En todo lo que sigue, x es la variable [texx]v_|[/texx].

Definimos P(z) como la fórmula [texx]-\exists{y}Dem(y,z)[/texx]. (Recordemos que [texx]Dem(y,z)[/texx] expresa la relación "y es el código de una demostración de la fórmula de código z".)

Definimos Q(x) como [texx]\forall{z}(z=d(x)\Rightarrow{P(z)})[/texx].

Sea n = cód(Q(x)). Entonces [texx]d(n) = c\'od(Q[\overline{n}])[/texx]. Llamamos m = d(n).

Los siguientes enunciados son equivalentes entre sí (esta equivalencia es sintáctica e implica que cualquiera de ellos es demostrable si y sólo si cualquiera de los otros lo es):

1. [texx]Q[\overline{n}][/texx]
2. [texx]Q(x/\overline{n})[/texx]
3. [texx]\forall{z}(z=\overline{m}\Rightarrow{P(z)})[/texx]
4. [texx]P[\overline{m}][/texx]
5. [texx]P(x/\overline{m})[/texx]

Llamemos G al enunciado [texx]P(x/\overline{m})[/texx], es decir, [texx]-\exists{y}Dem(y,\overline{m})[/texx].

Vamos a demostrar que ni G ni -G son demostrables.

Recordemos que hemos supuesto que se ha dado un sistema omega-consistente de axiomas aritméticos. (Que sea omega-consistente implica que es consistente.)

Si G es demostrable, entonces (por las equivalencias que mencionamos antes) [texx]Q[\overline{n}][/texx] es demostrable. Recordemos que el código de [texx]Q[\overline{n}][/texx] es m.

Sea k el código de una demostración de [texx]Q[\overline{n}][/texx], entonces [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado verdadero. La palabra "verdadero" se usa aquí en el sentido finitista, ya que [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado que expresa una propiedad de k y m que es verificable en una cantidad finita de pasos.

Como [texx]Dem(\overline{k},\overline{m})[/texx] es un enunciado finitista verdadero, entonces (por hipótesis) es demostrable. En consecuencia (por el tecnicismo que vimos antes) [texx]\exists{y}Dem(y,\overline{m})[/texx] es demostrable. Pero entonces -G es demostrable (ya que [texx]\exists{y}Dem(y,\overline{m})[/texx] es equivalente sintácticamente a -G). Esto contradice que el sistema es consistente, luego G no es demostrable.

Si -G es demostable entonces, por la consistencia del sistema, G no es demostrable. Luego, para todo k, [texx]-Dem(\overline{k},\overline{m})[/texx] es un enunciado finitista verdadero y, por lo tanto, demostrable. Por la omega-consistencia entonces [texx]\exists{y}Dem(y,\overline{m})[/texx] no es demostrable. Entonces -G no es demostrable. Esto contradice la hipótesis inicial. Por lo tanto, -G no es demostrable.

Vimos así que G no es demostrable, y que -G tampoco es demostrable. El sistema es, entonces, incompleto, Q.E.D.

7  Matemática / Lógica / Re: Teorema de Gödel : 04/04/2017, 08:10:28 pm
Gödel agrega 45 definiciones de propiedades y relaciones recursivas (más una que no es recursiva, la 46, Bew), que actúan en la práctica como si al sistema se le hubieran añadido axiomas para la división, la primalidad, la función factorial, la potencia, las dos inversas de la potencia, y varias más.

Están a partir de la página 8 en el documento que adjunto.

Estas fórmulas permiten que en el sistema se pueda expresar enunciados del metalenguaje natural, en castellano, como:

<< "ssss0 + sssssss0 = sssssssssss0  " es una fórmula demostrable>>.

La analogía es exacta, salvo que en lugar de citas textuales, Gödel hace citas codificadas en números.


"Ser demostrable" es expresable:

Hemos visto que "Ser un axioma" es expresable. Gracias al Principio Generador podemos deducir que "Ser una demostración" es también expresable. Con más precisión, la relación "x es el código de una demostración" es expresable.

Por otra parte, "Ser la última expresión en una sucesión de expresiones aritméticas" es también expresable. Esto se debe a que "y es el código de la última expresión en la sucesión de código x" equivale a que "la concatenación de los tres siguientes números, en ese orden: el código de [texx]\otimes{}[/texx],  el número y, el código de [texx]\otimes{}[/texx], es sufijo de x".

Como consecuencia de todo esto tenemos que la relación "x es el código de una demostración de la fórmula de código y" (es decir, "la fórmula de código y es la última en la demostración de código x") es expresable. Dado que usarenos muchas veces esta relación, la indicaremos como Dem(x, y).

Destaco un hecho: Dem(x, y) es la abreviatura de una larga fórmula escrita en el lenguaje formal, en la que x e y son las únicas variables libres, cuyo significado es: "x es el código de una demostración de la fórmula de código y".

Al hablar de "significado" podría llegar a entenderse que hemos introducido un concepto no fiinitario, pero esto es sólo aparente porque la condición "x es el código de una demostración de la fórmula de código y" puede traducirse a condiciones puramente sintácticas entre los números x e y, verificables todas ellas mecánicamente en una cantidad finita de pasos.

Es decir, existe un algoritmo que, dados los números n y m, puede verificar en una cantidad finita de pasos si [texx]Dem(\overline{n}, \overline{m})[/texx] se cumple o no. (Donde [texx]\overline{n}[/texx] y [texx]\overline{m}[/texx] son los numerales correspondientes a los números n y m.)

"y es el código de una fórmula demostrable" se puede expresar entonces como [texx]\exists{x}Dem(x,y)[/texx] (es decir, "existe una demostración de la fórmula de código y"). Por lo tanto "Ser el código de una fórmula demostrable" es expresable.

Nota: Que [texx]x[/texx] es el código de una demostración, que [texx]y[/texx] es el código de una  de una fórmula, y que [texx]y[/texx] es el código de la última expresión en la sucesión de código [texx]x[/texx] son todas propiedades recursivas, por lo que el hecho de que sean expresable se puede deducir del teorema general que dice que toda propiedad recursiva es expresable. Sin embargo, por sí sola, la propiedad "y es el código de una fórmula demostrable" no es recursiva (aunque sí expresable).

Nos habíamos propuesto el objetivo de probar que "Ser demostrable" es expresable y lo hemos logrado. Habíamos dicho, a modo de ejemplo, que queríamos que el lenguaje formal fuera capaz de decir "1 + 1 = 2 es demostrable". En efecto, si llamamos [texx]n_0[/texx] al código de S0 + S0 = SS0 entonces "1 + 1 = 2 es demostrable" equivale a [texx]\exists{x}Dem(x,y/\overline{n_0})[/texx].

Nota: Hemos probado que "Ser una fórmula demostrable" es expresable ¿Qué pasa con los enunciados? Recordemos que los enunciados son casos particulares de fórmulas y volvamos a "1 + 1 = 2 es demostrable", que se traduce como [texx]\exists{x}Dem(x,y/\overline{n_0})[/texx]. En realidad esta traducción dice, correctamente, "[texx]\overline{n_0}[/texx] es el código de una fórmula demostrable" y con eso es sificiente a todos los efectos ya que, fórmula o enunciado, lo que nos interesa decir es que "1 + 1 = 2 es demostrable". Por eso en el título de este comentario puse que "Ser demostrable" es expresable, sin indicar si me refería a fórmulas o a enunciados.

8  Matemática / Lógica / Re: Teorema de Gödel : 04/04/2017, 07:17:58 pm
Continuando, ese lenguaje básico es el que está generado usando los axiomas de Peano:


Tal vez convenga entonces mostrar, a modo de ejemplo, un conjunto recursivo de axiomas aritméticos. El sistema clásico es el de los "axiomas de Peano de primer orden", que se pueden escribir así (dejo tácitos todos los cuantificadores universales (los [texx]\forall{}[/texx]) necesarios para que las fórmulas sean enunciados):

1. [texx]Sx = Sy \Rightarrow x = y[/texx]
2. [texx]Sx\neq 0[/texx] (que es una abreviatura de [texx]-(Sx = 0)[/texx])
3. [texx]x + 0 = x[/texx]
4. [texx]x + Sy = S(x + y)[/texx]
5. [texx]x\cdot{0} = 0[/texx]
6. [texx]x\cdot{Sy} = x\cdot{y}+x[/texx]
7. [texx]P(0)\Rightarrow (\forall{x}(P(x)\Rightarrow P(Sx))\Rightarrow \forall{y}P(y))[/texx]


Si solamente nos atenemos a ellos, las únicas fórmulas del sistema serían ecuaciones con sumas y multiplicaciones, posiblemente cuantificadas, agrupadas con operadores lógicos.


9  Matemática / Lógica / Re: ¿Son los Elementos un sistema axiomático? : 04/04/2017, 03:53:34 pm
Seguramente que la teoría atómica de Dalton no tiene mucho que ver con la mecánica cuántica, ni siquiera con el modelo de Rutherford–Bohr. Pero ignorar que es el precedente histórico es hacerse el difícil.

Con Euclides mucho más, puesto que no solo es el primer caso de teoría deductiva con axiomas (postulados no es lo mismo que axiomas, pero no nos pongamos exquisitos). No es arqueología, sino historia viva.

Pruebas al canto: si fuera un fósil, Dieudonné no habría lanzado su famoso "À bas Euclide!".

Y mientras cualquiera puede aprender geometría con Euclides, para encontrar alguna utilidad a la axiomatización de Hilbert hay que saber mucha geometría y matemáticas en general de antemano. Hilbert sirve para hacer rigurosa una teoría sin agregarle nada nuevo. Euclides creó la geometría del plano, y sentó las bases de las teorías axiomáticas, y está aún vigente.
10  Matemática / Lógica / El barbero de Russell no es paradójico con Lógica Normativa : 04/04/2017, 03:01:03 pm
En la versión de la paradoja de Russell con el barbero, y con el lenguaje deliberadamente primitivo que usa para construirla (para aproximarlo al lenguaje de la aritmética), el barbero sólo puede quedar paralizado ante la contradicción:

“Barbero afeita x si y sólo si x no afeita x”

Luego, reemplazando x por “barbero”:

“Barbero afeita barbero si y sólo si barbero no afeita barbero”.

Pero si usamos un lenguaje en modo normativo (entendiéndolo como una forma “diferida” del modo imperativo) y temporal (que no por eso es menos científico, porque la física usa un lenguaje matemático, al que incorpora el tiempo, desde hace siglos, y el lenguaje en modo normativo está incorporado a todos los procedimientos, por lo menos desde el algoritmo de Euclides):

“El barbero debe afeitar a x, si y sólo si x no ha afeitado a x”.

Entonces, al reemplazar x por “el barbero”, resulta:

“El barbero debe afeitar al barbero, si y sólo si el barbero no ha afeitado al barbero”.

Ninguna contradicción, ninguna paradoja. El resultado es más bien trivial: si el barbero no se ha afeitado, debe afeitarse. La navaja de Hume [*1] fue contraproducente, quizás, en este caso .

-------------------------------


[*1] Me refiero al famoso texto en el que Hume declara que no hay forma de deducir una proposición normativa de otra descriptiva. Pero el barbero no está recibiendo lecciones morales, sino una orden. Y las órdenes a cumplir en el futuro, curiosamente, adoptan la misma forma gramatical que las normas morales.
11  Matemática / Lógica / Re: Novedad sobre el tema : 03/04/2017, 01:39:53 pm


A ver, gracias a las explicaciones de Gustavo Piñeiro, sé que hace mucho tiempo que dejó este foro, pero no voy a negar que fue con su explicación con lo que entendí que había fórmulas de PA que afirmaban la propia consistencia de la teoría.Lo que no llego a entender es esto:

La sentencia indecidible de Gödel pertenece al metalenguaje interno del sistema: sentencias que hablan de otras sentencias. Pero no hay ninguna sentencia del lenguaje objeto (ecuaciones diofánticas, eventualmente cuantificadas, y combinaciones booleanas de ellas).


https://www.academia.edu/s/990bdb21d6/unlocking-the-godel-enigma

La sentencia de Gödel (en su interpretación natural no afirma la consistencia de los axiomas de Peano)


Estimado Raúl:

Comienzo por aclarar que, efectivamente, la sentencia de Gödel no afirma la consistencia de los axiomas de Peano. Es una hipótesis del teorema, no una tesis. Hasta allí estamos de acuerdo.

Respecto de los niveles de lenguaje en el sistema de Gödel, comencemos por dejar establecido que el sistema original es el de Whitehead-Russell con el añadido de los axiomas de Peano.

Las operaciones definidas por los axiomas de Peano son sólo dos: suma y producto, y la única función es "sucesor".

De modo que el lenguaje básico está compuesto por ecuaciones diofánticas:

[texx]t_1 + t_2 + ... + t_n = 0[/texx]

donde cada término [texx]t_i[/texx]es un producto, que puede contener variables libres.

Estas ecuaciones pueden estar cuantificadas.

Y por último podemos reunir varias combinándolas con operadores booleanos OR, AND e implicaciones.


Saludos

12  Disciplinas relacionadas con la matemática / Foro general / ¿Es posible demostrar el teorema de Gödel sin la hipótesis de consistencia? : 30/03/2017, 01:13:14 pm
http://rinconmatematico.com/foros/index.php?topic=22263.msg380216;topicseen#msg380216


En castellano:

https://www.academia.edu/s/268c61bdf4/desvelando-el-enigma-godel?source=link

En inglés:

https://www.academia.edu/s/990bdb21d6/unlocking-the-godel-enigma
13  Matemática / Lógica / Novedad sobre el tema : 30/03/2017, 01:04:15 pm
La sentencia indecidible de Gödel pertenece al metalenguaje interno del sistema: sentencias que hablan de otras sentencias. Pero no hay ninguna sentencia del lenguaje objeto (ecuaciones diofánticas, eventualmente cuantificadas, y combinaciones booleanas de ellas).

Esto permite producir una demostración nueva del primer teorema de incompletitud, que prescinde de la hipótesis de consistencia.

Pero ¿comprometería este resultado la consistencia del sistema?

https://www.academia.edu/s/990bdb21d6/unlocking-the-godel-enigma
14  Matemática / Lógica / Epiménides el mentiroso ¿paradoja o falacia? : 07/12/2016, 07:52:21 pm
Epiménides el mentiroso ¿paradoja o falacia?

La larga historia de la llamada paradoja del mentiroso comenzó en el siglo VI antes de nuestra era, cuando el filósofo cretense Epiménides dijo "Los cretenses son mentirosos".

Siendo el autor de la frase un cretense, cabe preguntar si en el momento de pronunciarla mentía. En ese caso, lo que dijo es falso, por lo tanto lo cierto es que "Los cretenses no son mentirosos". Pero hemos dicho que al pronunciarla mintió, por lo tanto esto último tampoco es cierto, y volvemos al comienzo.

Sin embargo, las deducciones que hacemos no son categóricas, por la vaguedad del lenguaje en que fue formulado el enunciado. Con "los cretenses" ¿se refería a todos o sólo a algunos? Cuando dice que "son mentirosos", ¿implica que mienten siempre, o, como es lo más común, que mienten frecuentemente, y también son veraces a veces?

Para que sea una verdadera paradoja, las deducciones deben ser categóricas, y no dejar resquicio alguno para escapar del círculo vicioso.

Por lo tanto, debería ser formulada así:

"Todos los cretenses mienten siempre".

En ese caso, dicho por el cretense Epiménides, el enunciado es falso. Pero entonces nos encontramos que, formulada con precisión, la supuesta paradoja pierde su fuerza:

"No todos los cretenses mienten siempre"
o bien
"Algunos cretenses no mienten siempre".

Es un juicio tan vago, que no nos permite concluir que el primer enunciado es verdadero, que sería lo necesario para completar el círculo.

Viendo esto, algunos lógicos consideraron que la real paradoja estaba representada por una oración de este tipo:

"Epiménides dice que Epiménides miente".

Pero ¿qué puede haber dicho para implicar esto? Podría ser:

"Yo estoy mintiendo".

Si se considera que mentir es aseverar un enunciado falso, cabría preguntar cuál es el enunciado. Podría ser:

"El enunciado que estoy pronunciando es falso"

Pero hay aquí un problema de vacío de significado, porque sólo puede aseverarse la falsedad o veracidad de un enunciado completo e independiente de otros enunciados. Si el enunciado en cuestión se está construyendo en el mismo momento en que se dice de él que es falso, y esto es todo lo que contiene, es claramente una oración incompleta, no un enunciado.

LA CONVENCIÓN "T" DE TARSKY Y LA VERDAD

Más allá de la cuestión de si es una definición de la verdad o no, la convención "T" describe correctamente la forma en que usamos el predicado veritativo.

La oración "la nieve es blanca" es verdadera
si y sólo si
la nieve es blanca.

Su contraparte para el predicado falsatorio:

La oración "la nieve es blanca" es falsa
si y sólo si
no es el caso que la nieve es blanca.


Puede parecer tautológica, vacía de capacidad explicativa, y todo lo que se quiera. Pero sintácticamente nos aclara mucho las cosas. 

Entonces podemos ver con claridad meridiana que las versiones de Epiménides que llevan inexorablemente a la paradoja son en realidad falsos enunciados, oraciones defectuosas e incompletas.

"El enunciado que estoy pronunciando" es falso
si y sólo si
no es el caso que el enunciado que estoy pronunciando [...incompleto...]

El famosísimo ejemplo de Gödel:

"Supóngase que el 4 de mayo de 1934 X hace una única afirmación: 'Cualquier afirmación que X haga el 4 de mayo de 1934 es falsa' ".

"Cualquier afirmación que X haga el 4 de mayo de 1934" es falsa
si y sólo si
No es el caso que cualquier afirmación que X haga el 4 de mayo de 1934 [...incompleto...]

PROPUESTA DE INVESTIGACIÓN EMPÍRICA

Lo que propongo, entonces, es que todas las versiones del mentiroso son oraciones mal formadas por incompletas, o abiertas (tienen una variable libre si se trata de fórmulas del lenguaje formal). Por lo tanto, la oración sub examen no es verdadera ni falsa, simplemente es una ristra de caracteres sin sentido.

La metodología es experimental: si alguien cree que conoce una versión que es un auténtico enunciado, y además paradójico, lo examinamos con el método de Tarski, y decidimos.

Si se quiere debatir cuestiones teóricas, dejémoslo para luego de terminada la investigación, que propongo extender hasta el fin del verano austral, o el invierno boreal, el 21 de marzo de 1917.

Quedan todos invitados a proponer sus enunciados paradójicos y autoreferenciales como versiones de la paradoja de Epiménides.


[[ Tomado de una publicación de Abel Luis Peralta en Facebook.com y en Academia.edu. Derechos reservados ]]

15  Matemática / Lógica / El barbero de Russell y la doble negación en ciertas paradojas : 22/11/2016, 12:35:52 pm
EL BARBERO DE RUSSEL, LA DOBLE NEGACIÓN DEL HALTING PROBLEM Y OTROS ACERTIJOS (COMO DIRÍA WITTGENSTEIN)

La paradoja del barbero parece ineludible: parece que el pobre barbero estará siempre en falta. Pero todo reside en una mala elección de las palabras por parte del capitán del barco. Si en vez de decirle: "Afeita a un tripulante si y sólo si no se afeita por sí mismo", bastaba con decirle: "Debes afeitar solamente a quienes no se hayan afeitado a sí mismos". En ese caso, el barbero del barco afeitaría a aquellos que no se hayan afeitado a sí mismos (y si hay alguno que está afeitado por otro, no hay manera de distinguirlo), y sólo a ellos, y por otra parte, no habría contradicción alguna en afeitarse él mismo, y de hecho, DEBE hacerlo. Porque si no lo hace, falta a su deber de tener la tripulación afeitada (incluyéndose), y si lo hace, no falta a la regla, porque los seres humanos, a diferencia de los números, somos temporales: en un momento determinado, él está entre quienes no se han afeitado a sí mismos, pero si lo hace, no incumple la regla porque afeitó a alguien que NO se había afeitado a sí mismo, hasta ese momento.

La intemporalidad, y la falta de modalidad propias del lenguaje matemático le juega una mala pasada a Russell, al querer aplicarla a un ejemplo de la vida real.

De la misma manera, podríamos razonar el problema del programa que detecta los ciclos infinitos en todos los programas.

En el pueblo hay un par de gemelos idénticos, indistinguibles en todo sentido, salvo en este: uno de ellos siempre dice la verdad, y el otro siempre miente.

Entonces, si uno se encuentra con uno de ellos, y sólo puede hacerles una pregunta, hay que aprovechar la dicotomía, y preguntarles: "Si fueras tu hermano gemelo, ¿dirías que aprobé mi examen?". Ambos deben mentir.

Pero además, podríamos hacer también que ACTUARAN según nuestros designios. Si les ponemos una condición para la acción, el mentiroso hará lo contrario de lo que la condición le indica, porque si es verdadera la considerará falsa y viceversa. El veraz cumplirá al pie de la letra.

Entonces, si queremos que uno de los gemelos etiquete las listas según se autoreferencien o no, le podemos pedir que, si encuentran autoreferencia, copien las listas tal cual están y las coloquen en pilas separadas.

Si el gemelo que actúa es el veraz, hará todo según lo solicitado. Si es el mentiroso, hará exactamente lo contrario, agregando a las listas no autoreferentes su propio nombre, y borrará de las listas autorreferentes el nombre de las mismas.

Pero no hay problema, porque una vez terminada la tarea, volvemos a mezclar las listas, las colocamos como si fueran listas nuevas, y le pedimos que vuelva a hacer lo solicitado.

Si es veraz, las nuevas pilas y listas estarán perfectamente acordes, y si es el mendaz, también, porque al invertir el carácter y la ubicación de las listas la primera vez, e invertirlo de nuevo la segunda, deja las listas en la condición y el lugar correctos.

El Halting Problem funciona en realidad de la misma manera, pero eso queda como tarea para el hogar.


Tomado de una publicación de Abel-Luis Peralta en Facebook.com y en Academia.edu.

16  Matemática / Autómatas y lenguajes formales / Argumento de la doble negación en el Halting Problem : 21/11/2016, 05:08:59 pm
https://www.academia.edu/s/15dd3a0b3e/la-indefinibilidad-de-la-autoaplicacion?source=link
17  Matemática / Autómatas y lenguajes formales / The argument of the double negation in the Halting Problem : 20/11/2016, 11:04:29 pm
https://www.academia.edu/s/e8c8f3dfd4/the-indefinability-of-the-self-reference-in-the-halting-problemdoc?source=link
18  Matemática / Autómatas y lenguajes formales / El argumento de la doble negación contra la irresolubilidad del Halting Problem : 11/11/2016, 10:34:55 am
19  Matemática / Autómatas y lenguajes formales / Revertir al Programa Negador : 09/11/2016, 11:05:51 pm
Según al versión clásica de la irresolubilidad del Halting Problem, si hay un predicado X Para con Y, que vale ssi el programa X para con el input Y.
Pero también existe un programa Negador que hace lo contrario de lo que el predicado Para dice: Si X Para con Y, entonces volver a ejecutar el Negador.
Es obvio que si aplicamos el Negador a su propio código, el predicado Para enloquece:

   Negador Para con su propio código
   si y sólo si
   Negador NO Para con su propio código

Por lo cual, el resultado clásico concluía que era imposible construir un predicado que determinara si un programa cualquiera para con un input arbitrario.

Lo que propongo es definir un predicado No_Para, que es válido ssi X NO PARA con Y

Al igual que en el caso de mentirosos y veraces, No_Para da un resultado siempre falso, sin importar que haya o no un Negador de por medio. Miente siempre. Pero nos sirve, porque es un detector de circularidad.

¿Qué sucedería si alguien, anoticiado de esto, codifica un nuevo Negador, NegadorRecargado usando el nuevo predicado?

No hay muchas opciones: o sigue siendo un Negador, con lo cual nada cambia, o es un programa neutro sobre la propiedad de parar o no parar de los otros programas, en cuyo caso tampoco afecta en nada.

Funciona como el cuento de los gemelos, uno de los cuales miente siempre y el otro siempre dice la verdad. No sabes distinguirlos, pero no importa. Si quieres saber cómo te fue en un examen, y te encuentras con uno de ellos, le preguntas: "Según lo que diría tu hermano gemelo, ¿aprobé el examen?". Ambos se ven obligados a mentir; el veraz, porque tú se lo pides. El mentiroso, porque es su compulsión. Y tú sabes que lo contrario de lo que diga es cierto.

Por lo tanto, el reverso del programa de negación puede eludir la refutación que la argumentación clásica sostiene sobre el problema de la detención.

              [[ Este es un esbozo de una versión completa y formalizada. ]]

              [[ Reserva de Copyright por Abel-Luis Peralta, Buenos Aires, Argentina. ]]

https://www.academia.edu/s/dad3b06621/la-doble-negacion-contra-la-irresolubilidad-del-halting-problem-the-double-negation-against-the-unsolvability-of-the-halting-problem?source=link
20  Matemática / Autómatas y lenguajes formales / Re: La doble negación contra la irresolubilidad del Halting Problem : 08/11/2016, 09:06:09 pm
En lugar del predicado Halt(x, y), que es válido si y sólo si el programa x para con el input y, definamos:

NoHalt(x, y) es válido si y sólo si el programa x  NO PARA con el input y.

Hay un programa Burlador que hace lo contrario de lo que Halt(x, y) dictamina:

Bur:
Input: <x de tipo código de programa, y input válido para x>
   Si Halt ( x, y ) ejecutar Bur .

Veamos qué sucede contemplando todas las posibilidades.

Si x es un Bur, y el programa z que Bur usa como argumento sí para, el Bur no para con y, entonces Nohalt(x, y) es VÁLIDO.

Si x es un Bur, y el programa z que Bur usa como argumento NO para, el Bur para con y, Nohalt(x, y) NO es VÁLIDO.

Si x NO es un Bur, y el programa x sí para con y, Nohalt(x, y) es VÁLIDO.

Si x NO es un Bur, y el programa x NO para con y, Nohalt(x, y) NO es VÁLIDO.

Entonces NoHalt siempre da un resultado falso, haya o no un burlador de por medio, pero basta invertir la semántica:

NoHalt( m, n ) si y sólo si Pm  no para con input n.

¿Qué sucedería si alguien, anoticiado de esto, codifica un nuevo burlador, BurladorRecargado usando el nuevo predicado?

BurRec:
Input: <x de tipo código de programa, y input válido para x>
   Si ¬NoHalt ( x, y ) ejecutar BurRec .

BurRec funciona exactamente igual que el Bur original. Y puesto que NoHalt no usa en su construcción ni a Bur ni a BurRec, no se ve alterada en sus resultados por esta nueva definición de Bur.

Esto refuta la falsación de cualquier Halting Function por medio de un programa burlador, con el método de Marvin Minsky o Martin Davis. No así para el teorema de la circularidad de Alan Turing, pues el planteo es distinto: sostiene que cualquier detector de circularidad entraría en un círculo infinito con su propio código.

Buenos Aires, 8 de noviembre de 2016.





Páginas: [1] 2 3 ... 18
Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!