Feeds:
Posts
Comments

Archive for January 27th, 2008

From Logic to Ontology: The limit of “The Semantic Web”

 

 

(Some post are written in English and Spanish language) 

http://www.linkedin.com/answers/technology/web-development/TCH_WDD/165684-18926951 

From Logic to Ontology: The limit of “The Semantic Web” 

 http://en.wikipedia.org/wiki/Undecidable_problem#Other_problems

If you read the next posts on this blog: 

Semantic Web

The Semantic Web

What is the Semantic Web, Actually?

The Metaweb: Beyond Weblogs. From the Metaweb to the Semantic Web: A Roadmap

Semantics to the people! ontoworld

What’s next for the Internet

Web 3.0: Update

How the Wikipedia 3.0: The End of Google? article reached 2 million people in 4 days!

Google vs Web 3.0

Google dont like Web 3.0 [sic] Why am I not surprised?

Designing a better Web 3.0 search engine

From semantic Web (3.0) to the WebOS (4.0)

Search By Meaning

A Web That Thinks Like You

MINDING THE PLANET: THE MEANING AND FUTURE OF THE SEMANTIC WEB

The long-promised “semantic” web is starting to take shape

Start-Up Aims for Database to Automate Web Searching

Metaweb: a semantic wiki startup

http://www.freebase.com/

The Semantic Web, Collective Intelligence and Hyperdata.

Informal logic 

Logical argument

Consistency proof 

Consistency proof and completeness: Gödel’s incompleteness theorems

Computability theory (computer science): The halting problem

Gödel’s incompleteness theorems: Relationship with computability

Non-formal or Inconsistency Logic: LACAN’s LOGIC. Gödel’s incompleteness theorems,

You will realize the internal relationship between them linked from Logic to Ontology.  

I am writing from now on an article about the existence of the semantic web.  

I will prove that it does not exist at all, and that it is impossible to build from machines like computers.  

It does not depend on the software and hardware you use to build it: You cannot do that at all! 

You will notice the internal relations among them, and the connecting thread is the title of this post: “Logic to ontology.”   

I will prove that there is no such construction, which can not be done from the machines, and that does not depend on the hardware or software used.  

More precisely, the limits of the semantic web are not set by the use of machines themselves and biological systems could be used to reach this goal, but as the logic that is being used to construct it does not contemplate the concept of time, since it is purely formal logic and metonymic lacks the metaphor, and that is what Gödel’s theorems remark, the final tautology of each construction or metonymic language (mathematical), which leads to inconsistencies. 

This consistent logic is completely opposite to the logic that makes inconsistent use of time, inherent of human unconscious, but the use of time is built on the lack, not on positive things, it is based on denials and absences, and that is impossible to reflect on a machine because of the perceived lack of the required self-awareness is acquired with the absence.  

The problem is we are trying to build an intelligent system to replace our way of thinking, at least in the information search, but the special nature of human mind is the use of time which lets human beings reach a conclusion, therefore does not exist in the human mind the halting problem or stop of calculation.  

So all efforts faced toward semantic web are doomed to failure a priori if the aim is to extend our human way of thinking into machines, they lack the metaphorical speech, because only a mathematical construction, which will always be tautological and metonymic, and lacks the use of the time that is what leads to the conclusion or “stop”.  

As a demonstration of that, if you suppose it is possible to construct the semantic web, as a language with capabilities similar to human language, which has the use of time, should we face it as a theorem, we can prove it to be false with a counter example, and it is given in the particular case of the Turing machine and “the halting problem”.  

Then as the necessary and sufficient condition for the theorem is not fulfilled, we still have the necessary condition that if a language uses time, it lacks formal logic, the logic used is inconsistent and therefore has no stop problem.

This is a necessary condition for the semantic web, but it is not enough and therefore no machine, whether it is a Turing Machine, a computer or a device as random as a black body related to physics field, can deal with any language other than mathematics language hence it is implied that this language is forced to meet the halting problem, a result of Gödel theorem.   

De la lógica a la ontología: El límite de la “web semántica”  

Si lee los siguientes artículos de este blog: 

http://es.wikipedia.org/wiki/Web_sem%C3%A1ntica  

Wikipedia 3.0: El fin de Google (traducción Spanish)

Lógica 

Lógica Consistente y completitud: Teoremas de la incompletitud de Gödel (Spanish)

Consistencia lógica (Spanish)

Teoría de la computabilidad. Ciencia de la computación.

Teoremas de la incompletitud de Gödel y teoría de la computación: Problema de la parada 

Lógica inconsistente e incompletitud: LOGICAS LACANIANAS y Teoremas de la incompletitud de Gödel (Spanish)  

Jacques Lacan (Encyclopædia Britannica Online)

Usted puede darse cuenta de las relaciones internas entre ellos, y el hilo conductor es el título de este mismo post: “de la lógica a la ontología”.  

Probaré que no existe en absoluto tal construcción, que no se puede hacer desde las máquinas, y que no depende ni del hardware ni del software utilizado.   

Matizando la cuestión, el límite de la web semántica está dado no por las máquinas y/o sistemas biológicos que se pudieran usar, sino porque la lógica con que se intenta construir carece del uso del tiempo, ya que la lógica formal es puramente metonímica y carece de la metáfora, y eso es lo que marcan los teoremas de Gödel, la tautología final de toda construcción y /o lenguaje metonímico (matemático), que lleva a contradicciones.  

Esta lógica consistente es opuesta a la lógica inconsistente que hace uso del tiempo, propia del insconciente humano, pero el uso del tiempo está construido en base a la falta, no en torno a lo positivo sino en base a negaciones y ausencias, y eso es imposible de reflejar en una máquina porque la percepción de la falta necesita de la conciencia de sí mismo que se adquiere con la ausencia.   

El problema está en que pretendemos construir un sistema inteligente que sustituya nuestro pensamiento, al menos en las búsquedas de información, pero la particularidad de nuestro pensamiento humano es el uso del tiempo el que permite concluir, por eso no existe en la mente humana el problema de la parada o detención del cálculo, o lo que es lo mismo ausencia del momento de concluir.  

Así que todos los esfuerzos encaminados a la web semántica están destinados al fracaso a priori si lo que se pretende es prolongar nuestro pensamiento humano en las máquinas, ellas carecen de discurso metafórico, pues sólo son una construcción matemática, que siempre será tautológica y metonímica, ya que además carece del uso del tiempo que es lo que lleva al corte, la conclusión o la “parada”.  

Como demostración vale la del contraejemplo, o sea que si suponemos que es posible construir la web semántica, como un lenguaje con capacidades similares al lenguaje humano, que tiene el uso del tiempo, entonces si ese es un teorema general, con un solo contraejemplo se viene abajo, y el contraejemplo está dado en el caso particular de la máquina de Turing y el “problema de la parada”.  

Luego no se cumple la condición necesaria y suficiente del teorema, nos queda la condición necesaria que es que si un lenguaje tiene el uso del tiempo, carece de lógica formal, usa la lógica inconsistente y por lo tanto no tiene el problema de la parada”, esa es condición necesaria para la web semántica, pero no suficiente y por ello ninguna máquina, sea de Turing, computador o dispositivo aleatorio como un cuerpo negro en física, puede alcanzar el uso de un lenguaje que no sea el matemático con la paradoja de la parada, consecuencia del teorema de Gödel.

Jacques Lacan (Encyclopædia Britannica Online)

Read Full Post »

Jacques Lacan (Encyclopædia Britannica Online) 

http://microscopia2007.blogspot.com/2007/10/logicas-lacanianas.html 

Lógica inconsistente e incompletitud: LOGICAS LACANIANAS y Teoremas de la incompletitud de Gödel

  

La revolución Gödeliana…del Otro que no existe.

Completud, incompletud, consistencia, inconsistencia, decidible e indecidible son conceptos de la metalógica que se refieren a ciertas características de los sistemas lógicos formales, más precisamente a los sistemas axiomáticos. Son conceptos que se atribuyen a K Gödel a partir de sus teoremas de principios del siglo anterior. Surgen en un contexto muy particular de las matemáticas en contraposición al ideal de David Hilbert que consideraba que en ese ámbito todo podría ser demostrable.

Kurt Gödel nació el 28 de abril de 1906 en Brünn, Moravia. Entró a formar parte del Círculo de Viena, siendo a partir de ese momento que comienza a elaborar sus teorías más importantes sobre la completitud de los sistemas formales a partir de dos publicaciones: su tesis doctoral escrita en 1929, y el teorema (Sobre proposiciones formalmente indecidibles en los Principia Mathematica y sistemas afines) publicado en 1931.En el año 1931, Gödel publicaba Sobre proposiciones…,artículo que ponía en cuestión el programa de D Hilbert, porque demostraba que no sólo el sistema de Russel y Whitehead tenía fisuras, sino que todo sistema axiomático los tendría.

Un sistema axiomático está compuesto por un conjunto de enunciados o fórmulas que se admiten sin demostración –axiomas- a partir de los cuales se obtienen todas las demás afirmaciones de la teoría llamadas teoremas. El conjunto de axiomas, más la definición de enunciado o fórmula del sistema (definición que precede al enunciado de los axiomas) y el conjunto de las reglas para la obtención de teoremas a partir de los axiomas (reglas de transformación) constituyen la base primitiva del sistema.

K. Gödel demostró que es imposible establecer la consistencia lógica interna de una amplia clase de sistemas deductivos, a menos que se adopten principios tan complejos de razonamiento que su consistencia interna quede tan sujeta a la duda como la de los propios sistemas, poniendo en juego la imposibilidad de demostrar ciertas proposiciones.

Consistencia, inconsistencia, completud e incompletud. ¿Qué es un sistema, qué significa que sea consistente, inconsistente, completo o incompleto, qué es una proposición, etcétera?
Un sistema es un conjunto de axiomas y reglas de inferencia, una proposición una afirmación que puede ser cierta o falsa. ¿Cuándo un sistema es completo? Cuando dentro de él puede determinarse el valor de verdad o falsedad de toda proposición.

La completud nos asegura que no hay ninguna verdad en nuestro sistema que nosotros no seamos capaces de encontrar Pero solo podremos estar seguros de poder alcanzar toda la verdad si nuestro sistema es completo.

En cambio es incompleto cuando contiene proposiciones sobre las que no podemos decidir su verdad o falsedad. Por otra parte, un sistema es coherente cuando no hay contradicciones de ningún tipo ni tiene ninguna paradoja; y es incoherente cuando nos encontramos con contradicciones y paradojas. Un sistema es consistente si está limpio de paradojas y contradicciones y completo si toda proposición puede ser demostrada o refutada entro de él. Gödel considera que si es consistente es incompleto y si es completo es inconsistente.

 

 

En ese sentido, la consistencia implica que no sea posible deducir, a partir del mismo sistema de axiomas, dos teoremas que sean contradictorios. Cuando se llega a una contradicción semántica, el sistema se muestra inconsistente.


El principio de inconsistencia entonces supone que el valor de verdad de un sistema no puede ser determinado a partir de un conjunto de axiomas sino solo desde un axioma exterior. Es decir que un sistema es inconsistente cuando no puede librarse de sus contradicciones semánticas internas.

  

Artículo original completo:

martes 2 de octubre de 2007

LOGICAS LACANIANAS

¿En qué consiste la Consistencia? (*)

-Usos de Lacan de los conceptos de consistencia, inconsistencia,
completud e incompletud-

Referencias
En su Curso anual Del witz que hay en el síntoma que dicta en la Asociación de Psicoanálisis de La Plata, Enrique Acuña introdujo las nociones de inconsistencia, consistencia, completud e incompletud a las que hace mención Lacan a lo largo de su enseñanza. En su última parte en el seminario 23 El sinthome, en relación al nudo borromeo define a lo imaginario por la consistencia, a lo simbólico por la inconsistencia en relación al equívoco significante, y a lo real por la ex -sistencia. Consistencia o inconsistencia del Otro, incompletud del Otro, consistencia lógica del objeto, consistencia de lo imaginario, son distintos enunciados a lo largo de la enseñanza de Lacan que van cobrando distintos sentidos.

 

 

José Ferrater Mora en su Diccionario de filosofía, destaca que el concepto de consistencia aparece en tres contextos diferentes: un uso en el que se describe la “real subsistencia en términos de consistencia”,un sentido metafísico en el que queda ligado al término esencia, por declararse que la esencia de algo es aquello en que este “algo” consiste – con cierta derivación hacia la noción de sustancia-, y por último un contexto lógico a partir de expresiones como prueba de consistencia por medio de la cual se prueba si un cálculo es o no consistente.La revolución Gödeliana…del Otro que no existe.
Completud, incompletud, consistencia, inconsistencia, decidible e indecidible son conceptos de la metalógica que se refieren a ciertas características de los sistemas lógicos formales, más precisamente a los sistemas axiomáticos. Son conceptos que se atribuyen a K Gödel a partir de sus teoremas de principios del siglo anterior. Surgen en un contexto muy particular de las matemáticas en contraposición al ideal de David Hilbert que consideraba que en ese ámbito todo podría ser demostrable
Kurt Gödel nació el 28 de abril de 1906 en Brünn, Moravia. Entró a formar parte del Círculo de Viena, siendo a partir de ese momento que comienza a elaborar sus teorías más importantes sobre la completitud de los sistemas formales a partir de dos publicaciones: su tesis doctoral escrita en 1929, y el teorema (Sobre proposiciones formalmente indecidibles en los Principia Mathematica y sistemas afines) publicado en 1931.En el año 1931, Gödel publicaba Sobre proposiciones…,artículo que ponía en cuestión el programa de D Hilbert, porque demostraba que no sólo el sistema de Russel y Whitehead tenía fisuras, sino que todo sistema axiomático los tendría.
Un sistema axiomático está compuesto por un conjunto de enunciados o fórmulas que se admiten sin demostración –axiomas- a partir de los cuales se obtienen todas las demás afirmaciones de la teoría llamadas teoremas. El conjunto de axiomas, más la definición de enunciado o fórmula del sistema (definición que precede al enunciado de los axiomas) y el conjunto de las reglas para la obtención de teoremas a partir de los axiomas (reglas de transformación) constituyen la base primitiva del sistema.
K. Gödel demostró que es imposible establecer la consistencia lógica interna de una amplia clase de sistemas deductivos, a menos que se adopten principios tan complejos de razonamiento que su consistencia interna quede tan sujeta a la duda como la de los propios sistemas, poniendo en juego la imposibilidad de demostrar ciertas proposicionesConsistencia, inconsistencia, completud e incompletud¿Qué es un sistema, qué significa que sea consistente, inconsistente, completo o incompleto, qué es una proposición, etcétera?
Un sistema es un conjunto de axiomas y reglas de inferencia, una proposición una afirmación que puede ser cierta o falsa. ¿Cuándo un sistema es completo? Cuando dentro de él puede determinarse el valor de verdad o falsedad de toda proposición
La completud nos asegura que no hay ninguna verdad en nuestro sistema que nosotros no seamos capaces de encontrar Pero solo podremos estar seguros de poder alcanzar toda la verdad si nuestro sistema es completo..En cambio es incompleto cuando contiene proposiciones sobre las que no podemos decidir su verdad o falsedad. Por otra parte, un sistema es coherente cuando no hay contradicciones de ningún tipo ni tiene ninguna paradoja; y es incoherente cuando nos encontramos con contradicciones y paradojas. Un sistema es consistente si está limpio de paradojas y contradicciones y completo si toda proposición puede ser demostrada o refutada entro de él. Gödel considera que si es consistente es incompleto y si es completo es inconsistente.
En ese sentido, la consistencia implica que no sea posible deducir, a partir del mismo sistema de axiomas, dos teoremas que sean contradictorios. Cuando se llega a una contradicción semántica, el sistema se muestra inconsistente.
El principio de inconsistencia entonces supone que el valor de verdad de un sistema no puede ser determinado a partir de un conjunto de axiomas sino solo desde un axioma exterior. Es decir que un sistema es inconsistente cuando no puede librarse de sus contradicciones semánticas internas.-Variaciones conceptuales: consistencia real, simbólica e imaginaria.
Consistencia del Otro, consistencia del objeto, consistencia de lo imaginario, inconsistencia e incompletitud del Otro…¿qué significado adquieren estos conceptos en estas afirmaciones de Lacan a lo largo de su enseñanza?
Al comienzo, más precisamente antes de la construcción del grafo del deseo, el Otro aparece sin barrar, esto es completo y consistente. Se trata de una consistencia simbólica en tanto adolece de contradicción semántica, y de una completud cuántica en cuanto ningún significante falta. Se trata de un Otro que la creencia neurótica construye.

La inconsistencia de este Otro – introducida por el equívoco significante que devela que no todo puede saberse- se revela con más fuerza en el seminario de La Angustia cuando construye el esquema de la doble causación del sujeto y del objeto a partir de la castración del Otro.
En el seminario De un Otro al otro, la expresión consistencia lógica aparece en relación a la nueva versión del objeto a que está construyendo ligada la versión del plus de gozar. Allí la consistencia no queda ligada a la versión de una lógica simbólica que supone un sistema axiomático libre de contradicción, sino más bien a la versión de una “real consistencia ligada a la esencia”. Real subsistencia en términos de consistencia ligada a la esencia, ya que en ella algo consiste. Esta versión se opone a la deriva de la cadena significante en la que no podemos encontrar ninguna consistencia definida en estos términos. Este objeto “sustancializado” viene a ocupar el lugar vacío del Otro, es decir que la consistencia del objeto toma su peso a partir de la inconsistencia el Otro. El objeto a en su consistencia, tapa la inconsistencia del Otro. Se opone así a la inconsistencia de la deriva de la cadena, la consistencia sustancial del objeto a.
En cuanto al registro imaginario, la completitud se pone en juego al comienzo en el estadio del espejo con relación a esa imagen que viene a velar la fragmentación real del organismo. Imagen completa que en tanto tal llena de júbilo al infans.

 

 

Por otro lado la consistencia en relación a lo imaginario Lacan la pone de manifiesto en el seminario El sinthome cuando la opone a la imposibilidad de lo real y a la inconsistencia semántica de lo simbólico introducida por el equívoco significante. Allí define a la consistencia imaginaria como “lo que mantiene junto”(1)

Enrique Acuña, en clase del 12 de septiembre de su curso anual Del witz que hay en el síntoma en la APLP, hizo mención a la versión del nudo borromeo que Lacan introduce en La Tercera según la cual, esta función de “lo que mantiene junto” la cumple el objeto a.
Es un “a” que da estabilidad. Planteó allí la necesidad de acompañar el trayecto que conduce a Lacan hacia la formulación del sinthome desde el nombre del padre, pasando por el objeto a teniendo como horizonte la pregunta ¿porqué Lacan sustituye en esa función de “lo que mantiene junto”, al objeto “a” por el sinthome?.
Se trata de los usos que Lacan hace de los conceptos extraídos de otras disciplinas- en este caso de la matemática, la lógica y la topología- para intentar decir cada vez de una manera nueva, eso que llamó su síntoma; lo real.
Marcelo Ale
Consultas:
Ferrater Mora Jose Diccionario de filosofía. Ariel, Barcelona. 1999.
Copi I Introducción a la
lógica. Manuales EUDEBA. Buenos Aires.1995.
Cohen, M y Ángel, E Introducción a la lógica y al método científico. Amorrortu. Buenos Aires. 1968. 2 vol.
WWW.Wikipedia.org/wiki teoremas.
Acuña Enrique Curso Anual APLP Del witz que hay en el síntoma. 2007
Lacan J La tercera en Intervenciones y textos 2 Manantial. Buenos Aires. 1988.
El seminario libro 23 El sinthome. Paidós. Buenos Aires. 2007.Notas:
(1) Lacan J. El Seminario 23 El sinthome, Página 63.

0 comentarios:

 

Read Full Post »

Jacques Lacan (Encyclopædia Britannica Online)

The revolution … Another Gödel’s that does not exist!

Completeness, incompleteness, consistency, inconsistency, decidable and undecidable are concepts of meta logic which can be attributed to certain features of the formal logical systems, more precisely axiomatic systems. These are concepts that are attributed to K Gödel from their theorems from the beginning of the previous century. They emerge in a very particular context of mathematics as opposed to the ideal of David Hilbert who believed that everything in that area could be proof.

Kurt Gödel was born on April 28, 1906 in Brünn, Moravia. It became part of the Vienna Circle, and from that moment they begin to develop their most important theories on the completeness of the formal systems from two publications: his doctoral thesis written in 1929, and the theorem (formally on propositions undecidable in the Principia Mathematica and related systems) published in 1931.In 1931, Gödel published About propositions …, article that called into question the agenda D Hilbert, because not only showed that the system Russel and Whitehead had cracks, but the entire system would be axiomatic.

An axiomatic system consists of a set of formulas set forth or allowed without demonstration-axioms-from which all others are derived assertions theory called theorems. The set of axioms over the definition of phrasing or formula System (definition preceding statement of the axioms) and the set of rules for obtaining theorems from the axioms (transformation rules) are the basis of the primitive system.

K. Gödel proved that it is impossible to establish consistency internal logic of a broad class of deductive systems, unless it is taken early so complex reasoning that its internal consistency remains as subject to the doubt as to the systems themselves, putting at stake the impossibility proofing certain propositions. Consistency, inconsistency, completeness and incompleteness.What is a system, which means that it is consistently inconsistent, complete or incomplete, which is a proposition, etc.?
A system is a set of axioms and rules of inference, a claim that a proposition can be true or false. When a system is complete? Once inside it can be determined by the value of truth or falsity of any proposition
The completeness assures us that there is no truth in our system that we will not be able to find But we can only be sure of being able to reach the whole truth if our system is complete.Change is incomplete when it contains proposals on which we are unable to determine their truth or falsity. Moreover, a system is consistent when no contradictions of any kind nor does it have any paradox, and is inconsistent when we run into contradictions and paradoxes. A system is consistent if it is clean of paradoxes and contradictions and complete if any proposition can be proved or disproved sign him. Gödel believed that if it is consistent is incomplete and if it is completely inconsistent.In that sense, consistency means that it is not possible to deduce from the same set of axioms, two theorems which are contradictory. When it comes to contradiction semantics, the system is inconsistent.

The principle of inconsistency then assumed that the truth-value of a system can not be determined from a set of axioms, but only from a foreign axiom. That is a system that is inconsistent when it can not get rid of its internal contradictions semantic.

  

  

The article’s complete translation from Spanish Language is:

  

Tuesday October 2, 2007
LACAN’s LOGIC
 What is the consistency? (*)- Uses Lacan of the concepts of consistency, inconsistency, completeness and incompletenessReferences
At its annual course Witz is in the symptom that dictates in the Association of Psychoanalysis of La Plata, Enrique Acuña introduced the notions of inconsistency, consistency, and completeness and incompleteness to mention that Lacan over his teaching. In his last part in the seminar sinthome The 23, in relation to the Borromean knot defined by the imaginary consistency, as symbolic of the inconsistency in relation to significant misunderstanding, and what is real by the former existence. Consistency or inconsistency of the other incompletud Another, logical consistency of purpose, consistency of the imaginary, are different enunciated over the teaching of Lacan gaining different ways.

 

José Ferrater Mora in his Dictionary of Philosophy, stresses that the concept of consistency appears in three different contexts: a use which describes the “actual subsistence in terms of consistency,” a metaphysical sense in which the term is linked essence, by declaring that the essence of what something is that this “something” is – with some referral to the notion of substance, and finally a logical starting expressions as evidence of consistency by which it is tested whether a calculation is consistent or not.

The revolution … Another Gödel’s that does not exist.
Completeness, incompleteness, consistency, inconsistency, decidable and undecidable are concepts of meta logic which can be attributed to certain features of the formal logical systems, more precisely axiomatic systems. These are concepts that are attributed to K Gödel from their theorems from the beginning of the previous century. They emerge in a very particular context of mathematics as opposed to the ideal of David Hilbert who believed that everything in that area could be proof.
Kurt Gödel was born on April 28, 1906 in Brünn, Moravia. It became part of the Vienna Circle, and from that moment they begin to develop their most important theories on the completeness of the formal systems from two publications: his doctoral thesis written in 1929, and the theorem (formally on propositions undecidable in the Principia Mathematica and related systems) published in 1931.

In 1931, Gödel published About propositions …, article that called into question the agenda D Hilbert, because not only showed that the system Russel and Whitehead had cracks, but the entire system would be axiomatic.
An axiomatic system consists of a set of formulas set forth or allowed without demonstration-axioms-from which all others are derived assertions theory called theorems. The set of axioms over the definition of phrasing or formula System (definition preceding statement of the axioms) and the set of rules for obtaining theorems from the axioms (transformation rules) are the basis of the primitive system.
K. Gödel proved that it is impossible to establish consistency internal logic of a broad class of deductive systems, unless it is taken early so complex reasoning that its internal consistency remains as subject to the doubt as to the systems themselves, putting at stake the impossibility proofing certain propositions

Consistency, inconsistency, completeness and incompleteness

What is a system, which means that it is consistently inconsistent, complete or incomplete, which is a proposition, etc.?
A system is a set of axioms and rules of inference, a claim that a proposition can be true or false. When a system is complete? Once inside it can be determined by the value of truth or falsity of any proposition
The completeness assures us that there is no truth in our system that we will not be able to find But we can only be sure of being able to reach the whole truth if our system is complete.

. Change is incomplete when it contains proposals on which we are unable to determine their truth or falsity. Moreover, a system is consistent when no contradictions of any kind nor does it have any paradox, and is inconsistent when we run into contradictions and paradoxes. A system is consistent if it is clean of paradoxes and contradictions and complete if any proposition can be proved or disproved sign him. Gödel believed that if it is consistent is incomplete and if it is completely inconsistent.

In that sense, consistency means that it is not possible to deduce from the same set of axioms, two theorems which are contradictory. When it comes to a contradiction semantics, the system is inconsistent.
The principle of inconsistency then assumed that the truth-value of a system can not be determined from a set of axioms, but only from a foreign axiom. That is a system that is inconsistent when it can not get rid of its internal contradictions semantic.

– Variations concepts: consistency real and imaginary symbolic.
Another Consistency, consistency of purpose, consistency of the imaginary, inconsistency and incompleteness of the Other … what meaning acquire these concepts in these statements Lacan over their teaching?
Initially, more precisely before the construction of the graph of desire, without mark Another appears, that is complete and consistent. This is a symbolic while suffering from semantic contradiction, and a quantum completud as no significant fault. Another is a belief that the neurotic builds.

The inconsistency of this other – introduced by misleading significant that reveals that not everything can be known-is revealed with more force in the workshop of The Anxiety builds when the scheme of dual causation of the subject and the object from the castration of the Other .

The seminar From Another one to the other, the expression appears logical consistency in relation to the new version of the object being constructed linked to the release of more than enjoy. There consistency is not linked to the version of a symbolic logic that represents an axiomatic system free of contradiction, but rather the version of a “real consistency linked to the substance.” Real subsistence in terms of consistency linked to the substance, since it is something. This version is opposed to drift significant chain in which we were unable to find any consistency as defined in these terms. This object “substance” comes to take the place empty Another That is the consistency of the object takes its weight from the inconsistency the Other. The object in its consistency, cover the inconsistency of the Other. Opposes well to the inconsistency of the results from the chain, the consistency of the object substantial a.

As for the registration imaginary, comprehensiveness is at stake in the stadium at the beginning of the mirror with respect to that image that comes to ensuring actual fragmentation of the body. Image complete in itself full of joy to the baby.
On the other hand consistency in relation to the imaginary Lacan the shows at the seminar The sinthome when opposed to the inability of the real and the symbolic semantic inconsistency introduced by misleading significant. There defines consistency imaginary “which holds together” (1)

Enrique Acuña, class of 12 September from its current annual Witz is on the symptom in the APLP, referred to the version of the Borromean knot that Lacan introduces The Third whereby this function “which keeps together “meets the object a.
It is an “a” that gives stability. He raised hence the need to follow the path that leads to Lacan towards formulating the sinthome since his father’s name through the object to the horizon with the question why Lacan replaced in the role of “what holds together” in order “” by the sinthome?.

It is the uses that Lacan makes the concepts drawn from other disciplines-in this case of mathematics, logic and topology-to try to say every time a new way, that he called his symptoms, the real.

 

 

 An the original document is:

 

http://microscopia2007.blogspot.com/2007/10/logicas-lacanianas.html

 

************ EL PSICOANALISIS ENTRE LOS I N T E R s T I C I O S DE LA CULTURA * WWW.APLP.ORG.AR

martes 2 de octubre de 2007

LOGICAS LACANIANAS

¿En qué consiste la Consistencia? (*)

-Usos de Lacan de los conceptos de consistencia, inconsistencia,
completud e incompletud-

Referencias
En su Curso anual Del witz que hay en el síntoma que dicta en la Asociación de Psicoanálisis de La Plata, Enrique Acuña introdujo las nociones de inconsistencia, consistencia, completud e incompletud a las que hace mención Lacan a lo largo de su enseñanza. En su última parte en el seminario 23 El sinthome, en relación al nudo borromeo define a lo imaginario por la consistencia, a lo simbólico por la inconsistencia en relación al equívoco significante, y a lo real por la ex -sistencia. Consistencia o inconsistencia del Otro, incompletud del Otro, consistencia lógica del objeto, consistencia de lo imaginario, son distintos enunciados a lo largo de la enseñanza de Lacan que van cobrando distintos sentidos.

 

 

José Ferrater Mora en su Diccionario de filosofía, destaca que el concepto de consistencia aparece en tres contextos diferentes: un uso en el que se describe la “real subsistencia en términos de consistencia”,un sentido metafísico en el que queda ligado al término esencia, por declararse que la esencia de algo es aquello en que este “algo” consiste – con cierta derivación hacia la noción de sustancia-, y por último un contexto lógico a partir de expresiones como prueba de consistencia por medio de la cual se prueba si un cálculo es o no consistente.La revolución Gödeliana…del Otro que no existe.
Completud, incompletud, consistencia, inconsistencia, decidible e indecidible son conceptos de la metalógica que se refieren a ciertas características de los sistemas lógicos formales, más precisamente a los sistemas axiomáticos. Son conceptos que se atribuyen a K Gödel a partir de sus teoremas de principios del siglo anterior. Surgen en un contexto muy particular de las matemáticas en contraposición al ideal de David Hilbert que consideraba que en ese ámbito todo podría ser demostrable
Kurt Gödel nació el 28 de abril de 1906 en Brünn, Moravia. Entró a formar parte del Círculo de Viena, siendo a partir de ese momento que comienza a elaborar sus teorías más importantes sobre la completitud de los sistemas formales a partir de dos publicaciones: su tesis doctoral escrita en 1929, y el teorema (Sobre proposiciones formalmente indecidibles en los Principia Mathematica y sistemas afines) publicado en 1931.En el año 1931, Gödel publicaba Sobre proposiciones…,artículo que ponía en cuestión el programa de D Hilbert, porque demostraba que no sólo el sistema de Russel y Whitehead tenía fisuras, sino que todo sistema axiomático los tendría.
Un sistema axiomático está compuesto por un conjunto de enunciados o fórmulas que se admiten sin demostración –axiomas- a partir de los cuales se obtienen todas las demás afirmaciones de la teoría llamadas teoremas. El conjunto de axiomas, más la definición de enunciado o fórmula del sistema (definición que precede al enunciado de los axiomas) y el conjunto de las reglas para la obtención de teoremas a partir de los axiomas (reglas de transformación) constituyen la base primitiva del sistema.
K. Gödel demostró que es imposible establecer la consistencia lógica interna de una amplia clase de sistemas deductivos, a menos que se adopten principios tan complejos de razonamiento que su consistencia interna quede tan sujeta a la duda como la de los propios sistemas, poniendo en juego la imposibilidad de demostrar ciertas proposicionesConsistencia, inconsistencia, completud e incompletud
En ese sentido, la consistencia implica que no sea posible deducir, a partir del mismo sistema de axiomas, dos teoremas que sean contradictorios. Cuando se llega a una contradicción semántica, el sistema se muestra inconsistente.
El principio de inconsistencia entonces supone que el valor de verdad de un sistema no puede ser determinado a partir de un conjunto de axiomas sino solo desde un axioma exterior. Es decir que un sistema es inconsistente cuando no puede librarse de sus contradicciones semánticas internas.-Variaciones conceptuales: consistencia real, simbólica e imaginaria.
Consistencia del Otro, consistencia del objeto, consistencia de lo imaginario, inconsistencia e incompletitud del Otro…¿qué significado adquieren estos conceptos en estas afirmaciones de Lacan a lo largo de su enseñanza?
Al comienzo, más precisamente antes de la construcción del grafo del deseo, el Otro aparece sin barrar, esto es completo y consistente. Se trata de una consistencia simbólica en tanto adolece de contradicción semántica, y de una completud cuántica en cuanto ningún significante falta. Se trata de un Otro que la creencia neurótica construye.

La inconsistencia de este Otro – introducida por el equívoco significante que devela que no todo puede saberse- se revela con más fuerza en el seminario de La Angustia cuando construye el esquema de la doble causación del sujeto y del objeto a partir de la castración del Otro.
En el seminario De un Otro al otro, la expresión consistencia lógica aparece en relación a la nueva versión del objeto a que está construyendo ligada la versión del plus de gozar. Allí la consistencia no queda ligada a la versión de una lógica simbólica que supone un sistema axiomático libre de contradicción, sino más bien a la versión de una “real consistencia ligada a la esencia”. Real subsistencia en términos de consistencia ligada a la esencia, ya que en ella algo consiste. Esta versión se opone a la deriva de la cadena significante en la que no podemos encontrar ninguna consistencia definida en estos términos. Este objeto “sustancializado” viene a ocupar el lugar vacío del Otro, es decir que la consistencia del objeto toma su peso a partir de la inconsistencia el Otro. El objeto a en su consistencia, tapa la inconsistencia del Otro. Se opone así a la inconsistencia de la deriva de la cadena, la consistencia sustancial del objeto a.
En cuanto al registro imaginario, la completitud se pone en juego al comienzo en el estadio del espejo con relación a esa imagen que viene a velar la fragmentación real del organismo. Imagen completa que en tanto tal llena de júbilo al infans.

 

 

Por otro lado la consistencia en relación a lo imaginario Lacan la pone de manifiesto en el seminario El sinthome cuando la opone a la imposibilidad de lo real y a la inconsistencia semántica de lo simbólico introducida por el equívoco significante. Allí define a la consistencia imaginaria como “lo que mantiene junto”(1)

Enrique Acuña, en clase del 12 de septiembre de su curso anual Del witz que hay en el síntoma en la APLP, hizo mención a la versión del nudo borromeo que Lacan introduce en La Tercera según la cual, esta función de “lo que mantiene junto” la cumple el objeto a.
Es un “a” que da estabilidad. Planteó allí la necesidad de acompañar el trayecto que conduce a Lacan hacia la formulación del sinthome desde el nombre del padre, pasando por el objeto a teniendo como horizonte la pregunta ¿porqué Lacan sustituye en esa función de “lo que mantiene junto”, al objeto “a” por el sinthome?.
Se trata de los usos que Lacan hace de los conceptos extraídos de otras disciplinas- en este caso de la matemática, la lógica y la topología- para intentar decir cada vez de una manera nueva, eso que llamó su síntoma; lo real.
Marcelo Ale
Consultas:
Ferrater Mora Jose Diccionario de filosofía. Ariel, Barcelona. 1999.
Copi I Introducción a la
lógica. Manuales EUDEBA. Buenos Aires.1995.
Cohen, M y Ángel, E Introducción a la lógica y al método científico. Amorrortu. Buenos Aires. 1968. 2 vol.
WWW.Wikipedia.org/wiki teoremas.
Acuña Enrique Curso Anual APLP Del witz que hay en el síntoma. 2007
Lacan J La tercera en Intervenciones y textos 2 Manantial. Buenos Aires. 1988.
El seminario libro 23 El sinthome. Paidós. Buenos Aires. 2007.Notas:
(1) Lacan J. El Seminario 23 El sinthome, Página 63.

¿Qué es un sistema, qué significa que sea consistente, inconsistente, completo o incompleto, qué es una proposición, etcétera?
Un sistema es un conjunto de axiomas y reglas de inferencia, una proposición una afirmación que puede ser cierta o falsa. ¿Cuándo un sistema es completo? Cuando dentro de él puede determinarse el valor de verdad o falsedad de toda proposición
La completud nos asegura que no hay ninguna verdad en nuestro sistema que nosotros no seamos capaces de encontrar Pero solo podremos estar seguros de poder alcanzar toda la verdad si nuestro sistema es completo.

.En cambio es incompleto cuando contiene proposiciones sobre las que no podemos decidir su verdad o falsedad. Por otra parte, un sistema es coherente cuando no hay contradicciones de ningún tipo ni tiene ninguna paradoja; y es incoherente cuando nos encontramos con contradicciones y paradojas. Un sistema es consistente si está limpio de paradojas y contradicciones y completo si toda proposición puede ser demostrada o refutada entro de él. Gödel considera que si es consistente es incompleto y si es completo es inconsistente.

 

0 comentarios:

 

 

Read Full Post »

Teoremas de la incompletitud de Gödel:

Problema de la parada

De Wikipedia, la enciclopedia libre

El problema de la parada o problema de la detención para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Consiste en determinar si una máquina de Turing se detendrá con cierta entrada, o bien quedará en un ciclo infinito. Este fue el primer problema que se demostró formalmente que no tenía solución.

El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe un algoritmo que nos permita determinar si el problema tiene solución.

Una de las razones por la que es importante conocer que el problema de la parada no tiene solución, es que nos permite decidir si otros problemas son resolubles o no. El razonamiento a seguir sería: si suponiendo que un problema es decidible, podemos demostrar que el problema de la parada tiene solución, entonces podemos llegar a la conclusión de que el problema en cuestión no la tiene, por reducción al absurdo.

Definición [editar]

Sea M una máquina de Turing arbitraria con un alfabeto de entrada Σ. Sea w \in \Sigma^*. ¿Puede decidirse si la máquina M se detendrá con la entrada w?

Solución [editar]

La respuesta a esta pregunta es negativa. No se puede determinar si una máquina de Turing se detiene con una entrada arbitraria.

Demostración [editar]

Para demostrarlo, supongamos que el problema de la parada tiene solución, es decir, supondremos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing para con una entrada determinada.

Consideremos una máquina de Turing P, que recibe como entrada una máquina de Turing M y una cadena w codificadas en la cinta y una a continuación de la otra (Mw), y que se encarga de ejecutar M sobre la cadena w. La máquina P parará y aceptará la entrada si M para con w, y parará y rechazará la entrada si M no para con w.

Modificamos la máquina P, creando una máquina P’ equivalente. Esta máquina no parará si M para con w, y parará si M no para con w. Obsérvese que esta modificación es trivial en términos de máquinas de Turing.

Ahora crearemos una máquina D, cuya función es la siguiente. Recibe una máquina M, la pasa por una máquina que se encarga de copiar la máquina M a continuación. Por lo tanto, a la salida de la máquina copia, la cinta contendrá MM (la codificación de la máquina repetida). A continuación, D coge este resultado y lo pasa a través de P’. Con esto intentamos decidir si la máquina M para con la entrada M. Es decir, si M para con la entrada M, entonces D no para, y si M no para con la entrada M, entonces D para. Nótese que la máquina de copia no es difícil de implementar.

Por último, tomaremos una máquina D (denominaremos SD), y le aplicaremos como entrada una máquina D. SD aplica como entrada a la máquina que recibe, la misma máquina. Por lo tanto, esta máquina en principio parará si D no para con entrada D, y no parará si D para con entrada D. Pero si SD no para y si D para con entrada D, sabiendo que D=SD, llegamos a una contradicción, por que aplicar D a SD debería dar como resultado lo mismo que aplicar D sobre D. Del mismo modo para el otro caso. Por lo tanto, el problema de la parada no tiene solución.

Todas las máquinas que hemos ido implementando en la demostración son, exceptuando P, relativamente fáciles de hacer, por lo que la clave de la demostración se encuentra, por reducción al absurdo, efectivamente en P, que es quien sostenía la hipótesis acerca de la resolubilidad del problema.

Read Full Post »

Computability theory (computer science)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation.

Computability theory differs from the related discipline of computational complexity theory, which deals with the question of how efficiently a problem can be solved, rather than whether it is solvable at all.

Contents

[hide]

//

[edit] Introduction

A central question of computer science is to address the limits of computing devices. One approach to addressing this question is understanding the problems we can use computers to solve. Modern computing devices often seem to possess infinite capacity for calculation, and it’s easy to imagine that, given enough time, we might use computers to solve any problem. However, it is possible to show clear limits to the ability of computers, even given arbitrarily vast computational resources, to solve even seemingly simple problems. Problems are formally expressed as a decision problem which is to construct a mathematical function that for each input returns either 0 or 1. If the value of the function on the input is 0 then the answer is “no” and otherwise the answer is “yes”.

To explore this area, computer scientists invented automata theory which addresses problems such as the following: Given a formal language, and a string, is the string a member of that language? This is a somewhat esoteric way of asking this question, so an example is illuminating. We might define our language as the set of all strings of digits which represent a prime number. To ask whether an input string is a member of this language is equivalent to asking whether the number represented by that input string is prime. Similarly, we define a language as the set of all palindromes, or the set of all strings consisting only of the letter ‘a’. In these examples, it is easy to see that constructing a computer to solve one problem is easier in some cases than in others.

But in what real sense is this observation true? Can we define a formal sense in which we can understand how hard a particular problem is to solve on a computer? It is the goal of computability theory of automata to answer just this question.

[edit] Formal models of computation

In order to begin to answer the central question of automata theory, it is necessary to define in a formal way what an automaton is. There are a number of useful models of automata. Some widely known models are:

Deterministic finite state machine
Also called a deterministic finite automaton (DFA), or simply a finite state machine. All real computing devices in existence today can be modeled as a finite state machine, as all real computers operate on finite resources. Such a machine has a set of states, and a set of state transitions which are affected by the input stream. Certain states are defined to be accepting states. An input stream is fed into the machine one character at a time, and the state transitions for the current state are compared to the input stream, and if there is a matching transition the machine may enter a new state. If at the end of the input stream the machine is in an accepting state, then the whole input stream is accepted.
Nondeterministic finite state machine
Similarly called a nondeterministic finite automaton (NFA), it is another simple model of computation, although its processing sequence is not uniquely determined. It can be interpreted as taking multiple paths of computation simultaneously through a finite number of states. However, it is proved that any NFA is exactly reducible to an equivalent DFA.
Pushdown automaton
Similar to the finite state machine, except that it has available an execution stack, which is allowed to grow to arbitrary size. The state transitions additionally specify whether to add a symbol to the stack, or to remove a symbol from the stack. It is more powerful than a DFA due to its infinite-memory stack, although only some information in the stack is ever freely accessible.
Turing machine
Also similar to the finite state machine, except that the input is provided on an execution “tape”, which the Turing machine can read from, write to, or move back and forth past its read/write “head”. The tape is allowed to grow to arbitrary size. The Turing machine is capable of performing complex calculations which can have arbitrary duration. This model is perhaps the most important model of computation in computer science, as it simulates computation in the absence of predefined resource limits.
Multi-tape Turing machine
Here, there may be more than one tape; moreover there may be multiple heads per tape. Surprisingly, any computation that can be performed by this sort of machine can also be performed by an ordinary Turing machine, although the latter may be slower or require a larger total region of its tape.

[edit] Power of automata

With these computational models in hand, we can determine what their limits are. That is, what classes of languages can they accept?

[edit] Power of finite state machines

Computer scientists call any language that can be accepted by a finite state machine a regular language. Because of the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language that is not regular, we must construct a language that would require an infinite number of states.

An example of such a language is the set of all strings consisting of the letters ‘a’ and ‘b’ which contain an equal number of the letter ‘a’ and ‘b’. To see why this language cannot be correctly recognized by a finite state machine, assume first that such a machine M exists. M must have some number of states n. Now consider the string x consisting of (n + 1) ‘a’s followed by (n + 1) ‘b’s.

As M reads in x, there must be some state in the machine that is repeated as it reads in the first series of ‘a’s, since there are (n + 1) ‘a’s and only n states by the pigeonhole principle. Call this state S, and further let d be the number of ‘a’s that our machine read in order to get from the first occurrence of S to some subsequent occurrence during the ‘a’ sequence. We know, then, that at that second occurrence of S, we can add in an additional d (where d > 0) ‘a’s and we will be again at state S. This means that we know that a string of (n + d + 1) ‘a’s must end up in the same state as the string of (n + 1) ‘a’s. This implies that if our machine accepts x, it must also accept the string of (n + d + 1) ‘a’s followed by (n + 1) ‘b’s, which is not in the language of strings containing an equal number of ‘a’s and ‘b’s.

We know, therefore, that this language cannot be accepted correctly by any finite state machine, and is thus not a regular language. A more general form of this result is called the Pumping lemma for regular languages, which can be used to show that broad classes of languages cannot be recognized by a finite state machine.

[edit] Power of pushdown automata

Computer scientists define a language that can be accepted by a pushdown automaton as a Context-free language, which can be specified as a Context-free grammar. The language consisting of strings with equal numbers of ‘a’s and ‘b’s, which we showed was not a regular language, can be decided by a push-down automaton. Also, in general, a push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular. This model of computation is thus strictly more powerful than finite state machines.

However, it turns out there are languages that cannot be decided by push-down automaton either. The result is similar to that for regular expressions, and won’t be detailed here. There exists a Pumping lemma for context-free languages. An example of such a language is the set of prime numbers.

[edit] Power of Turing machines

Turing machines can decide any context-free language, in addition to languages not decidable by a push-down automata, such as the language consisting of prime numbers. It is therefore a strictly more powerful model of computation.

Because Turing machines have the ability to “back up” in their input tape, it is possible for a Turing machine to run for a long time in a way that is not possible with the other computation models previously described. It is possible to construct a Turing machine that will never finish running (halt) on some inputs. We say that a Turing machine can decide a language if it eventually will halt on all inputs and give an answer. A language that can be so decided is called a recursive language. We can further describe Turing machines that will eventually halt and give an answer for any input in a language, but which may run forever for input strings which are not in the language. Such Turing machines could tell us that a given string is in the language, but we may never be sure based on its behavior that a given string is not in a language, since it may run forever in such a case. A language which is accepted by such a Turing machine is called a recursively enumerable language.

The Turing machine, it turns out, is an exceedingly powerful model of automata. Attempts to amend the definition of a Turing machine to produce a more powerful machine are surprisingly met with failure. For example, adding an extra tape to the Turing machine, giving it a 2-dimensional (or 3 or any-dimensional) infinite surface to work with can all be simulated by a Turing machine with the basic 1-dimensional tape. These models are thus not more powerful. In fact, a consequence of the Church-Turing thesis is that there is no reasonable model of computation which can decide languages that cannot be decided by a Turing machine.

The question to ask then is: do there exist languages which are recursively enumerable, but not recursive? And, furthermore, are there languages which are not even recursively enumerable?

[edit] The halting problem

Main article: Halting problem

The halting problem is one of the most famous problems in computer science, because it has profound implications on the theory of computability and on how we use computers in everyday practice. The problem can be phrased:

Given a description of a Turing machine and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.

Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the tables and asking a Turing machine to answer a question about another Turing machine. It can be shown (See main article: Halting problem) that it is not possible to construct a Turing machine that can answer this question in all cases.

That is, the only general way to know for sure if a given program will halt on a particular input in all cases is simply to run it and see if it halts. If it does halt, then you know it halts. If it doesn’t halt, however, you may never know if it will eventually halt. The language consisting of all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore called non-computable or undecidable.

An extension of the halting problem is called Rice’s Theorem, which states that it is undecidable (in general) whether a given language possesses any specific nontrivial property.

[edit] Beyond recursive languages

The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever when given input which is a representation of a Turing machine that does not itself halt. The halting language is therefore recursively enumerable. It is possible to construct languages which are not even recursively enumerable, however.

A simple example of such a language is the complement of the halting language; that is the language consisting of all Turing machines paired with input strings where the Turing machines do not halt on their input. To see that this language is not recursively enumerable, imagine that we construct a Turing machine M which is able to give a definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually halt. We can then construct another Turing machine M that simulates the operation of this machine, along with simulating directly the execution of the machine given in the input as well, by interleaving the execution of the two programs. Since the direct simulation will eventually halt if the program it is simulating halts, and since by assumption the simulation of M will eventually halt if the input program would never halt, we know that M will eventually have one of its parallel versions halt. M is thus a decider for the halting problem. We have previously shown, however, that the halting problem is undecidable. We have a contradiction, and we have thus shown that our assumption that M exists is incorrect. The complement of the halting language is therefore not recursively enumerable.

[edit] Concurrency-based models

A number of computational models based on concurrency have been developed, including the Parallel Random Access Machine and the Petri net. These models of concurrent computation still do not implement any mathematical functions that cannot be implemented by Turing machines.

[edit] Unreasonable models of computation

The Church-Turing thesis conjectures that there is no reasonable model of computing that can compute more mathematical functions than a Turing machine. In this section we will explore some of the “unreasonable” ideas for computational models which violate this conjecture. Computer scientists have imagined many varieties of hypercomputers.

[edit] Infinite execution

Imagine a machine where each step of the computation requires half the time of the previous step. If we normalize to 1 time unit the amount of time required for the first step, the execution would require

time to run. This infinite series converges to 2 time units, which means that this Turing machine can run an infinite execution in 2 time units. This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question. By extension, any convergent series would work. Assuming that the series converges to a value n, the Turing machine would complete an infinite execution in n time units.

[edit] Oracle machines

Main article: Oracle machine

So-called Oracle machines have access to various “oracles” which provide the solution to specific undecidable problems. For example, the Turing machine may have a “halting oracle” which answers immediately whether a given Turing machine will ever halt on a given input. These machines are a central topic of study in recursion theory.

[edit] Limits of Hyper-computation

Even these machines, which seemingly represent the limit of automata that we could imagine, run into their own limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. For example, an Oracle machine cannot answer the question of whether a given Oracle machine will ever halt.

[edit] History of computability theory

The lambda calculus, an important precursor to formal computability theory, was developed by Alonzo Church and Stephen Cole Kleene. Alan Turing is most often considered the father of modern computer science, and laid many of the important foundations of computability and complexity theory, including the first description of the Turing machine (in [1], 1936) as well as many of the important early results.

[edit] See also

[edit] References

Read Full Post »

Gödel’s incompleteness theorems

From Wikipedia, the free encyclopedia

[edit] Relationship with computability

As early as 1943, Kleene gave a proof of Godel’s incompleteness theorem using basic results of computability theory.[8] A basic result of computability shows that the halting problem is unsolvable: there is no computer program that can correctly determine, given a program P as input, whether P eventually halts when run with no input. Kleene showed that the existence of a complete effective theory of arithmetic with certain consistency properties would force the halting problem to be decidable, a contradiction. An exposition of this proof at the undergraduate level was given by Charlesworth (1980).[9]

By enumerating all possible proofs, it is possible to enumerate all the provable consequences of any effective first-order theory. This makes is possible to search for proofs of a certain form. Moreover, the method of arithmetization introduced by Gödel can be used to show that any sufficiently strong theory of arithmetic can represent the workings of computer programs. In particular, for each program P there is a formula Q such that Q expresses the idea that P halts when run with no input. The formula Q says, essentially, that there is a natural number that encodes the entire computation history of P and this history ends with P halting.

If, for every such formula Q, either Q or the negation of Q was a logical consequence of the axiom system, then it would be possible, by enumerating enough theorems, to determine which of these is the case. In particular, for each program P, the axiom system would either prove “P halts when run with no input,” or “P doesn’t halt when run with no input.”

Consistency assumptions imply that the axiom system is correct about these theorems. If the axioms prove that a program P doesn’t halt when the program P actually does halt, then the axiom system is inconsistent, because it is possible to use the complete computation history of P to make a proof that P does halt. This proof would just follow the computation of P step-by-step until P halts after a finite number of steps.

The mere consistency of the axiom system is not enough to obtain a contradiction, however, because a consistent axiom system could still prove the ω-inconsistent theorem that a program halts, when it actually doesn’t halt. The assumption of ω-consistency implies, however, that if the axiom system proves a program doesn’t halt then the program actually does not halt. Thus if the axiom system was consistent and ω-consistent, its proofs about which programs halt would correctly reflect reality. Thus it would be possible to effectively decide which programs halt by merely enumerating proofs in the system; this contradiction shows that no effective, consistent, ω-consistent formal theory of arithmetic that is strong enough to represent the workings of a computer can be complete.

Read Full Post »

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad  

Teoría de la computabilidad

De Wikipedia, la enciclopedia libre

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:

  • ¿Qué problemas puede resolver una máquina de Turing?
  • ¿Qué otros formalismos equivalen a las máquinas de Turing?
  • ¿Qué problemas requieren máquinas más poderosas?
  • ¿Qué problemas requieren máquinas menos poderosas?

La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

Tabla de contenidos

[ocultar]

//

Antecedentes [editar]

El origen de los modelos abstractos de computación se encuadra en los años ’30 (antes de que existieran los ordenadores modernos), para el trabajo de los lógicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en el desarrollo teórico como en abundantes aspectos de la práctica de la computación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.

El punto inicial de estos primeros trabajos fueron las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de un congreso internacional.

Lo que Hilbert pretendía era crear un sistema matemático formal completo y consistente en el cual, todas las aseveraciones fueran planteadas con precisión. Su intención era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. Al problema en cuestión se le denominó Entscheidungsproblem. En caso de que Hilbert hubiese cumplido su objetivo, cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo.

Pero fueron otros los que mediante una serie de investigaciones mostraron que esto no era posible. En contra de esta idea K. Gödel sacó a la luz su conocido Primer Teorema de Incompletitud. Este viene a expresar que todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo. Gödel construyó una fórmula que es satisfactoria pero que no puede ser probada en el sistema. Como consecuencia, no es posible encontrar el sistema formal deseado por Hilbert en el marco de la lógica de primer orden, a no ser que se tome un conjunto no recursivo de axiomas.

Una posterior versión, que resulta más general, del teorema de incompletitud de Gödel, indica que ningún sistema deductivo que contenga los teoremas de la aritmética, y con los axiomas recursivamente enumerables puede ser consistente y completo a la vez. Esto hace pensar, a nivel intuitivo, que no va a ser posible definir un sistema formal.

¿Qué problemas puede resolver una máquina de Turing? [editar]

No todos los problemas pueden ser resueltos. Un problema indecidible es uno que no puede ser resuelto con un algoritmo aún si se dispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:

  • El Entscheidungsproblem (problema de decisión en alemán) que se define como: Dada una frase del cálculo de predicados de primer orden, decidir si ella es un teorema. Church y Turing demostraron independientemente que este problema es indecidible.
  • El Problema de la parada, que se define así: Dado un programa y su entrada, decidir si ese programa terminará para esa entrada o si correrá indefinidamente. Turing demostró que se trata de un problema indecidible.
  • Un número computable es un número real que puede ser aproximado por un algoritmo con un nivel de exactitud arbitrario. Turing demostró que casi todos los números no son computables. Por ejemplo, la Constante de Chaitin no es computable aunque sí que está bien definido.

¿Qué otros formalismos equivalen a las máquinas de Turing? [editar]

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden ser computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.

Los computadores electrónicos, basados en la arquitectura Eckert-Mauchly así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos.

Entre los formalismos equivalentes a una máquina de Turing están:

Los últimos tres ejemplos utilizan una definición ligeramente diferente de aceptación de un lenguaje. Ellas aceptan una palabra si cualquiera, cómputo acepta (en el caso de no determinismo), o la mayoría de los cómputos aceptan (para las versiones probabilística y cuántica). Con estas definiciones, estas máquinas tienen el mismo poder de expresión que una máquina de Turing.

¿Qué problemas requieren máquinas más poderosas? [editar]

Se considera que algunas máquinas tienen mayor poder que las máquinas de Turing. Por ejemplo, una máquina oráculo que utiliza una caja negra que puede calcular una función particular que no es calculable con una máquina de Turing. La fuerza de cómputo de una máquina oráculo viene descrita por su grado de Turing. La teoría de cómputos reales estudia máquinas con precisión absoluta en los números reales. Dentro de esta teoría, es posible demostrar afirmaciones interesentes, tales como «el complemento de un conjunto de Mandelbrot es solo parcialmente decidible».

Read Full Post »

Older Posts »

%d bloggers like this: