Feeds:
Posts
Comments

Archive for the ‘Semantic Web’ Category

Theorem: “The limit of The Artificial Intelligence”.

 

 

The limit of the Artificial Intelligence 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 this is what Gödel’s theorems remark, the final tautology of each construction or metonymic mathematical language, which leads to inconsistencies. The construction of the Artificial Intelligence is an Undecidible Problem .

 

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 this is impossible to reflect on a machine because of the perceived lack of the required self-awareness is acquired with the absence.

 

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

 

If you suppose as a theorem, that it is possible to construct a machine, with a Intelligence with capabilities similar to human Intelligence, 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” or stop of calculation.

 

So all efforts faced toward Artificial Intelligence 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 metaphor that is what leads to the conclusion or “stop”.

Read Full Post »

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

 

 

The limit 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 this is what Gödel’s theorems remark, the final tautology of each construction or metonymic Mathematical Language , which leads to inconsistencies. The construction of the Semantic Web is an Undecidible Problem .

 

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 this 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”.

Read Full Post »

Cerebro, Computadoras y Mente: Del Lenguaje y del Pensamiento de los Seres Humanos, las Máquinas y los Animales. El fracaso de la Inteligencia Artificial y de la Web Semántica.

 

Francisco Antonio Cerón García

Physic’s Spanish Real Society

fcerong@gmail.com

 

Índice

 

1.- Introducción                                                                    1

    

2.- Situación actual de la Ciencia de la Computación.        3

 

3.- Los límites de las herramientas de la Ciencia: la Lógica Formal y la Experimentación                                               4

 

4.- Los mecanismos fundamentales del Lenguaje y del Pensamiento.                                                                      8

 

5.- Estructuralismo.                                                             9

 

6.- Conocimiento y Transmisión del Conocimiento.          11

 

7.- Naturaleza y Representación del Conocimiento.         14

 

8.- ¿Porque no intentar enseñar a hablar y/o a pensar a una máquina? Limitaciones y fracasos de la aproximación de la Lógica Descriptiva.                                                   17

 

9.- El Pensamiento y el Lenguaje.                                     19

 

10.- El Pensamiento no es lo mismo que el Lenguaje, y el Cerebro no es lo mismo que la Mente. ¿Qué es la Inteligencia?. ¿Qué es el Pensamiento?.                          20

 

11.- Diferencia entre los animales y los seres humanos    21

 

12.- Conclusión: Imposibilidad del Lenguaje y Pensamiento humano en las Máquinas, y el fracaso de la Inteligencia Artificial y de la Web Semántica.                                        23

 

13.- Teorema: “El Límite de la Inteligencia Artificial”.         25 

 

14.- Teorema:  De la lógica a la ontología: “El Límite de la Web Semántica”.                                                                27

 

15.- Bibliografía.                                                                 29                                                                                                                         

 

 

 

 

1.- Introducción

 

De la lectura de “Minds, Machines and Gödel”  por
J.R. Lucas
, y de otros autores como Roger Penrose, hay un numeroso trabajo previo de argumentación de la imposibilidad de hacer pensar y/o hablar a las máquinas u ordenadores.

 

 

La metonimia, el primer mecanismo del pensamiento y el lenguaje humano, ya la tenemos incorporada en las máquinas u ordenadores, es el sustrato mismo de la Lógica Simbólica y/o formal (y por lo tanto también de las Matemáticas), pero nos falta la metáfora, que es lo que a los seres humanos nos permite “concluir” en el sentido estricto del término en Psicoanálisis, la metáfora nos introduce en lo real como paso del tiempo.

 

Y este es mi gran reto: Inventar una lógica o no consistente o no completa (pero no ambas a la vez como pretende la lógica formal), que además de la metonimia presente en la lógica matemática consistente, tenga también incorporada la metáfora.

 

 

2.- Situación actual de la Ciencia de la Computación.

 

El intento de construir la Web Semántica a partir de la Lógica Descriptiva, la cual a su vez toma como base a la Lógica Simbólica o Lógica Matemática, es contradictorio e incoherente, pues aunque la lógica simbólica o matemática es consistente, sin embargo por definición sólo tiene sentido único o unívoco (significado único), lo cual es totalmente contradictorio con la semántica del lenguaje (natural) ,  la cual es de sentido ambigua o multívoca (varios significados).

 

Si lo que perseguimos es, por ejemplo, como una aplicación de la Web Semántica, cuando hacemos una búsqueda en Google, obtener unos pocos y precisos resultados, en lugar de los varios millones de ambiguos que se suelen obtener, tenemos que partir de otras herramientas más adecuadas al lenguaje, que tengan sentido multívoco y no sólo unívoco, y por lo tanto hay que construir nuevas herramientas en lugar de las ya existentes que tomen en cuenta dicha diferencia.

 

Tenemos que acudir a las Ciencias que estudian el lenguaje, y más aún, a las Ciencias que estudian el pensamiento y la mente humana, allí podemos encontrar las herramientas que buscamos, y proyectarlas, si es posible, sobre las Matemáticas, inventando, si es necesario, una nueva lógica menos parcial que la Lógica Formal, la Lógica Simbólica y/o matemática actual, que nos dé lugar a una nueva y distinta lógica que la Lógica Descriptiva actual, que constituye un completo y sonoro fracaso en semantizar  Internet.

 

Todo lo anterior tiene sentido si analizamos el marco en el que se ha desarrollado el conocimiento humano, desde inclusive la misma prehistoria. A grandes y fundamentales rasgos, y de forma también muy simplificada, lo único que nos diferencia verdaderamente de los animales es que somos “seres hablantes”, o lo que es lo mismo, que hacemos uso del lenguaje, y lo importante en nuestro caso es que hacemos uso del lenguaje como medio de comunicación, lo que nos ha servido para la transmisión de conocimientos a lo largo de toda la historia de la humanidad.

 

Lo único que verdaderamente a cambiado la manera de transmisión de lo exclusivamente oral (habla), ha sido la invención de la escritura, que ha permitido la perdurabilidad y acumulación sucesiva de los conocimientos, desde el papel de papiro y las tablas de arcilla, pasando por los libros manuscritos y llegando a  la invención de la imprenta por Gutenberg. Con esta última abaratamos sustancialmente los costes de transmisión del conocimiento, y posteriormente con el invento de Internet (y los ordenadores) disminuimos el coste de transmisión de los conocimientos a casi cero (al menos en los países desarrollados); así el conocimiento, por primera vez en la historia de la humanidad, está hoy día casi al alcance de todo el mundo y no unos pocos privilegiados, como por ejemplo en el medioevo.

 

Pero ahora si además lográramos “semantizar” Internet, donde “la Web Semántica es una visión de la información que sea comprensible por los ordenadores, de modo que puedan realizar mejor el tedioso trabajo de encontrar, compartir y combinar la información de la Web”, el ahorro ya no sólo sería una cuestión económica y monetaria, el ahorro además sería de economía del tiempo de pensamiento, o lo que es lo mismo del tiempo necesario para buscar y encontrar el conocimiento.

 

Por otra parte, además de la reseña histórica y en los rasgos fundamentales en la transmisión del conocimiento y su logro correspondiente, que es toda la civilización humana, hay que “enmarcar”, definir el marco en el cual se ha realizado el mismo en toda la historia de la humanidad, y no es un tema banal y sin importancia ni mucho menos, sino y de la mayor importancia. Hoy día hay ciencias específicas del estudio del conocimiento como la Epistemología, Gnoseología y otras. Pero aún así necesitamos más herramientas de otras áreas, como el Psicoanálisis, la Lingüística, etc. Lo cual fundamentaré a continuación.

 

 

3.- Los límites de las herramientas de la Ciencia: la Lógica Formal y la Experimentación.

 

Primeramente quiero decir que el enfoque “neurocientífico”, donde todo lo relacionado al ser humano tiene una explicación y aplicación directa exclusivamente  “neurológica” y/o “biológica”, cuando no y además “genética”, es incompleto y muy parcial. La hipótesis de trabajo fundamental de toda  la Ciencia actual es que la Mente y el Cerebro son iguales o equivalentes, y todo ello viene dado y ocasionado por la preponderancia y exclusividad en la Ciencia de los métodos estadísticos y estocásticos, cuantitativos (despreciando y excluyendo lo cualitativo), y lógicos formales, estos últimos aunque rigurosos sin embargo son incompletos y/o contradictorios tal y como nos muestran múltiples resultados y paradojas tanto en Matemáticas (Teoremas de Gödel), como en otras áreas de la Ciencia. Pero el ser humano con el lenguaje va mucho más allá de dicho reduccionismocientífico” (considerando a la Ciencia como un sistema  sólo y exclusivamente formal del pensamiento como así se la  define de forma ortodoxa y tradicional), el ser humano va mucho más allá de todo lo meramente biológico, tal y como demuestra el Psicoanálisis, en particular Freud y Lacan, y en la clínica.

 

Freud y Lacan descubrieron que hay un sujeto (persona) particular en cada ser humano, que le constituye (por ejemplo con su inconsciente), y que no es generalizable, y sobre todo en el sentido reduccionista de la Ciencia, sea la genética, sea la biología, sea  la química, sea la física, sea las matemáticas, y más ampliamente aún sea desde el punto de vista de la lógica formal; porque este sistema de pensamiento es por definición cerrado y completo sobre sí mismo, pero como es una aproximación solamente metonímica a lo real, carente de la metáfora del lenguaje y pensamiento humanos, es una aproximación muy pobre al final (a pesar de los frutos tecnológicos que ha obtenido nuestra civilización de ello), y ella nos ha llevado a sus propios límites en el conocimiento de lo real, lo cual es claramente visible en numerosas las paradojas matemáticas (Teoremas de incompletitud de Gödel), informáticas (Máquina de Turing y Problema de la parada –  Turing Machine & Halting Problem), e inclusive físicas (la teoría de la relatividad es  incompatible matemática y físicamente con la teoría de la mecánica cuántica -nuestras dos teorías fundamentales de la Ciencia y la tecnología y más cercanas al mundo real-).

 

 

Porque en toda la historia de la humanidad, tanto las ciencias, las exactas, como la física, química, matemática, como las otras, tales como la biología, la genética, la neurología, la medicina, las neurociencias, etc., y además todas sus aplicaciones en toda la tecnología pasada y presente, están todas ellas basadas en una lógica formal del pensamiento, y precisamente desde Gödel, encontramos numerosos ejemplos de paradojas…Todo lo cual nos muestra que estamos en los límites del conocimiento que nos puede aportar la lógica formal, la cual por definición está limitada solamente al sentido unívoco de la metonimia, y aunque combinada con la transmisión del conocimiento, ha permitido construir la actual civilización tecnológica, sin embargo estamos en un marco lógico limitado y constreñido a los límites de la lógica formal, y que como ya he dicho es la herramienta del pensamiento científico y la tecnología actuales por su propia definición y en toda su evolución histórica desde la época de la civilización griega.

 

Luego si la lógica formal, que es la base de todo pensamiento de toda la ciencia y la tecnología, puede llegar a ser “contradictoria”, y “limitada” o “incompleta” (Gödel), hay que dar un paso más allá y abrir el horizonte usando unas herramientas más completas y menos parciales, que podemos sacarlas de lo que ha descubierto el Psicoanálisis del ser humano y su constitución como sujeto en tres estructuras: una simbólica, otra imaginaria, y la conjunción de ambas con lo real nos permite apreciar “algo” de lo real, pero de una forma parcial y fragmentada, no hay una coherencia y reciprocidad entre lo que nuestra mente es capaz de llegar a captar, entender y/o comprender de lo real, con lo que verdaderamente es lo real.

 

Y es por esta falta de aceptación y de haberse dado cuenta de lo anterior es que el discurso de la ciencia y la tecnología es alienante, y se empiezan a encontrar plagadas de paradojas y contradicciones; y para colmo de males cuanto más se excluye la metáfora, lo singular y/o particular del sujeto, cuando más metonímico y cerrado se vuelve el discurso científico, tanto más se aleja de lo real, y un ejemplo vivido por todos actualmente y de forma muy cercana es la “crisis” económica mundial, en donde el sistema económico se ha devorado a sí mismo, y tampoco nos ha faltado tanto a la humanidad entera con la alienación de la guerra atómica, no hemos estado ni estamos tan lejos de devorarnos a nosotros mismos, por el “progreso” ilimitado de la ciencia y la tecnología; si no somos conscientes de sus límites y no nos hacemos cargo de ellos, lo real siempre está presente para surgir muy a nuestro pesar, y recordárnoslo y no de forma precisamente agradable.  No propongo un retorno a la naturaleza, que es  “mítico”, sino hacernos cargo de nuestra responsabilidad y asumir los límites del pensamiento científico y tecnológico, pero siendo un científico a mi vez de formación y vocación,  intento a su vez ir un paso más allá, y teniendo presentes estos límites, y mi limitación como la de todos para conocer lo real, intento encontrar nuevas formas de pensamiento aplicables a la ciencia, a la tecnología, y la informática en particular.

 

El peor error de la ciencia es creerse la única verdad fundamental y estar por encima de todo, y sin embargo lo real es tan complejo y tan complicado que requiere como mínimo una gran dosis de humildad, y es por ello que la ciencia actual es tan incapaz de ir más allá de su propio discurso y sus propios límites lógicos, y darse cuenta que mente y cerebro no son equivalentes y/o iguales; este es el gran error de la mayoría de los científicos actuales (Cientifismo) adornado y barnizado con la tecnología. Pero si al menos no se quiere aceptar como una verdad cierta y demostrada, siempre queda usarla como axioma, al igual que miles de conocimientos que en todas las áreas de la ciencia no son demostrables y sin embargo se dan por ciertos, y si mi axioma de que mente y cerebro no son lo mismo, funciona correctamente y nos lleva a resultados coherentes con el mundo real, lo daremos entonces por cierto.

 

 

4.- Los mecanismos fundamentales del Lenguaje y del Pensamiento.

 

Además de lo dicho en los párrafos anteriores, el Psicoanálisis también nos enseña que hay dos mecanismos fundamentales en el Lenguaje (Saussure) y el pensamiento humano, cuales son el desplazamiento o metonimia, y la condensación o metáfora (Freud), o lingüísticamente llamados metonimia y metáfora (Lacan).

 

La metonimia es el mecanismo fundamental del pensamiento científico (y matemático), y es lo que refleja la lógica formal y/o simbólica, donde el sentido ambiguo y multívoco del Lenguaje se ha diseccionado en un sentido preciso y unívoco para conseguir rigor, y consistencia por lo tanto, y excluir la contradicción, pero a costa de suprimir el otro mecanismo del pensamiento, cual es la condensación o metáfora, llegando paradójicamente a resultados contradictorios (véase paradojas…) o incompletos. Dentro de todo el sistema lógico formal ha funcionado permitiéndonos inventar y desarrollar nuestra presente civilización tecnológica, pero como ya he dicho, estamos encontrando su límites lógicos.

 

Ahora entonces, podemos dar un paso más adelante y más allá, con la incorporación de la metáfora a nuestro sistema lógico del pensamiento la ciencia y la tecnología, donde  la incorporación de la metáfora,  podría implicar la pérdida del principio de la generalidad, pero inclusive aún llegando a un sistema incompleto, seguramente tendría una representación más cercana y certera de lo real que con el sistema tradicional. Y ello es lo que me propongo hacer e intentar construir a partir de ahora…

 

Y si logro definir una lógica que además de la metonimia tenga incorporada también la metáfora, tendré incorporados entonces los dos mecanismos fundamentales del pensamiento y del lenguaje humano. Aún así siempre será un sistema parcial y limitado del conocimiento, pero tendrá como ya he dicho anteriormente una  mejor percepción de lo real que con la sola metonimia de la lógica simbólica.

 

La metáfora o condensación es lo que nos permite concluir y lo que nos introduce lo real como paso del tiempo,  mientras que en la lógica simbólica o matemática, lo real entra solamente a través de la cardinalidad de los Números.

 

 

5.- Estructuralismo.

 

El marco teórico y experimental en el que me muevo es  por lo tanto el “Estructuralismo”, comenzando desde Saussure con su estudio de la lengua, siguiendo a Jakobson y a Levis Strauss, y terminando en Freud y Lacan con el descubrimiento del inconsciente, el Psicoanálisis, y la constitución del  ser humano como sujeto.

 

No me propongo ni pretendo hacer una demostración puntillosa, perfecta, completa y rigurosa en el sentido clásico y ortodoxo de la ciencia, porque estaría usando la concepción de la lógica formal del pensamiento tradicional y ortodoxo de la ciencia y la tecnología,  aunque ello no significa renunciar a la coherencia o consistencia interna, aunque mi sistema no sea por definición ni completo, ni por lo tanto cerrado, sólo exigiré, si me es posible, la no contradicción, y sí pretendo a partir del marco teórico y experimental que he definido, encontrar, identificar, y/o inventar si es necesario, unas herramientas que me permitan analizar y estudiar los conocimientos no sólo de una forma metonímica de la lógica formal y/o simbólica, como hasta ahora ha sucedido en Informática e Internet, sino y además que pueda “semantizar” la Web, con el añadido de alguna herramienta que represente la metáfora, y el principio de condensación del lenguaje y el pensamiento humano, que es lo que nos acerca a lo real a través del paso del tiempo y la conclusión.

 

Este sistema lógico por lo explicado anteriormente sobre nuestra percepción de lo real, y también por definición, no será completo, e inclusive podría llegar a ser inconsistente, aunque procuraré hacerlo de tal manera que en lo posible lo evite, como lo es a veces lo mismo real, pero será una útil herramienta para manejar el conocimiento en Internet. No pretendo al final que los ordenadores lleguen a hablar, ya que mi teorema “El Límite de la Web Semántica”, dice que ello es imposible, pero todo lo que pueda caminar en dicho sentido será un avance sustancial para el manejo y transmisión del conocimiento a través de Internet.

 

Y este sistema lógico además de no ser completo implica entonces que no es cerrado, o sea que es abierto, y aunque parece imposible así construir algo “científico”, sin embargo toda la ciencia y la tecnología y sus descubrimientos están imbuidos en buena medida del mismo, ya que aunque hemos intentado formalizarlo con la lógica formal, sin embargo la relación de la ciencia y la tecnología con lo real, pasa a través de nuestra mente y sus mecanismos a veces inconsistentes, pero relacionados directamente con lo real, donde nadie es, desde allí es que pretendo buscar y encontrar este nuevo orden del pensamiento, donde todo no es completo y cerrado, pero donde todo si está conectado a lo real a través de la semantización del lenguaje informático e Internet.

 

Este es mi  proyecto, tal vez disparatado y grandioso, cuan imposible, pero como decía Lacan “lo real es lo único imposible” y a por ello voy…

 

 

6.- Conocimiento y Transmisión del Conocimiento.

 

El conocimiento es, por una parte, el estado de quien conoce o sabe algo, y por otro lado, los contenidos sabidos o conocidos que forman parte del patrimonio cultural de la Humanidad. Por extensión, suele llamarse también “conocimiento” a todo lo que un individuo o una sociedad dados consideran sabido o conocido.

 

Sin duda, las ciencias constituyen una de los principales tipos de conocimiento. Las ciencias son el resultado de esfuerzos sistemáticos y metódicos de investigación en busca de respuestas a problemas específicos y cuya elucidación procura ofrecernos una representación adecuada del mundo. Hay también, no obstante, muchos tipos de conocimiento que, sin ser científicos, no dejan de estar perfectamente adaptados a sus propósitos: el «saber hacer» en la artesanía, el saber nadar, etc.; el conocimiento de la lengua, de las tradiciones, leyendas, costumbres o ideas de una cultura particular; el conocimiento que los individuos tienen de su propia historia (saben su propio nombre, conocen a sus padres, su pasado), o aún los conocimientos comunes a una sociedad dada, incluso a la humanidad (saber para qué sirve una martillo, saber que el agua extingue el fuego).

 

Aun cuando en cada momento se genera información, sin embargo, la cantidad de conocimiento humano es necesariamente finita, amén de la dificultad de resolver problemas tales como el origen de la vida y del universo, la muerte, entre muchos otros.

 

Los conocimientos se adquieren mediante una pluralidad de procesos cognitivos: percepción, memoria, experiencia (tentativas seguidas de éxito o fracaso), razonamiento, enseñanza-aprendizaje, testimonio de terceros… Por su parte, la observación controlada, la experimentación, la modelización, la crítica de fuentes (en Historia), las encuestas, y otros procedimientos que son específicamente empleados por las ciencias, pueden considerarse como un refinamiento o una aplicación sistemática de los anteriores. Estos son objeto de estudio de la epistemología.

 

La importancia que atribuye al conocimiento distingue a la humanidad de las otras especies animales. Todas las sociedades humanas adquieren, preservan y transmiten una cantidad sustancial de saberes, notablemente, a través del lenguaje. Con el surgimiento de las civilizaciones, la acumulación y la difusión de conocimientos se multiplican por medio de la escritura. A través de la historia, la humanidad ha desarrollado una variedad de técnicas destinadas a preservar, transmitir y elaborar los conocimientos, tales como la escuela, las enciclopedias, la prensa escrita, las computadoras u ordenadores.

 

Esta importancia va de la mano con una interrogación sobre el valor del conocimiento. Numerosas sociedades y movimientos religiosos, políticos o filosóficos han considerado que el acrecentamiento del saber, o su difusión, no resultaban convenientes y debían limitarse. A la inversa, otros grupos y sociedades han creado instituciones tendentes a asegurar su preservación, su desarrollo y su difusión. Así mismo, se debate cuáles son los valores respectivos de diferentes dominios y clases de conocimientos.

 

En las sociedades contemporáneas, la difusión o al contrario, la retención de los conocimientos, tiene un importante papel político y económico, incluso militar; lo mismo ocurre con la propagación de pseudo-conocimientos (o desinformación). Todo ello contribuye a hacer del conocimiento una fuente de poder. Este papel explica en buena parte la difusión de la propaganda y las pseudociencias, que son tentativas por presentar como conocimientos, cosas que no lo son. Esto le confiere una importancia particular a las fuentes de supuestos conocimientos, como los medios masivos y sus vehículos, tales como Internet.

 

Y así como el invento de la escritura y de la imprenta trajeron aparejada una revolución y explosión en la transmisión del conocimiento, ahora el invento de Internet y el intento de construir una Web Semántica sobre ella, significaría una revolución y explosión exponencial en la transmisión del conocimiento a una escala sin precedente alguno respecto de toda la historia de la civilización, porque ya no sólo todo el conocimiento sería accesible a un coste económico ínfimo como ha dado lugar Internet, sino y además que el coste de tiempo de búsqueda del conocimiento, a través del filtro de la Web Semántica en Internet, se reduciría a casi cero.

 

Para lograr el objetivo de construir la Web Semántica, ya no es suficiente con mecanizar con una máquina la escritura caligráfica y/o “a mano”, que fue lo que hizo “Gutenberg”, ahora necesitamos “enseñarle” el lenguaje a las  computadoras u ordenadores, y para ello es necesario saber:

 

¿Cuál es la naturaleza del conocimiento?

 

¿Cómo representamos al conocimiento?

 

Y estas preguntas y sus respuestas no son fútiles ni de perogrullo, pues tenemos que ser conscientes que este es el paso crucial que representa la Web Semántica: ¡La incorporación del “Lenguaje” en las computadoras u ordenadores! Y aunque mi teorema “The limit of The Semantic Web” dice que ello es un objetivo imposible, sin embargo todo lo que nos acercáramos en dicho sentido nos daría nuevas herramientas de transmisión del conocimiento. Evidentemente si lográramos totalmente dicho objetivo estaríamos muy cerca de que las máquinas tuvieran “pensamiento humano”, que aunque inclusive teniendo dicha habilidad, nunca serían iguales o equivalentes a los seres humanos por su distinta imbricación en lo real.

 

 

7.- Naturaleza y Representación del Conocimiento.

 

La teoría clásica de la transmisión del conocimiento, que es la teoría de la Comunicación nos dice que hay un emisor y un receptor, que es lo que también usa la Psicología como ciencia; pero la novedad del descubrimiento del Psicoanálisis es que además del receptor citado, hay también un segundo receptor que es el mismo emisor también. Y el Psicoanálisis nos descubre al ser humano como un sujeto divido, y por lo tanto nos descubre también la ambivalencia del lenguaje y la inexistencia de un sentido unívoco del mismo, o lo que es lo mismo, del sin sentido del sentido del lenguaje, tal y como Wittgenstein lo indicó.

 

El Psicoanálisis nos explica que en la constitución del sujeto interviene un mundo simbólico, que es el lenguaje, un mundo imaginario, que es la participación que cada uno tiene en el lenguaje, y un mundo real, al que sólo se puede acceder a través precisamente de la representación del mismo que nos da la conjunción de lo simbólico y lo imaginario (lo Real, lo Imaginario y lo Simbólico).

 

Independientemente de todos los complejos detalles al respecto en la teoría Psicoanalítica, léase Freud y Lacan, lo importante es que el ser humano no percibe al mundo o a lo real tal cual es, sino y bajo el prisma de su propia constitución original de sujeto. Por ello la aprensión del conocimiento no es ilimitada, sino y limitada a la propia naturaleza del lenguaje humano ambivalente, lo que establece unos límites del conocimiento de lo real, y un buen ejemplo de ello es el intento del gran matemático Hilbert y otros, de construir un sistema matemático completo axiomáticamente y no contradictorio en sí mismo, pero como Gödel demostró con sus teoremas, si un sistema de conocimiento es completo, entonces es contradictorio, y viceversa, si un sistema es incompleto entonces no es contradictorio; también tenemos otros muchos ejemplos como la máquina de Turing y el Problema de la Parada. Al final lo que nos dice todo esto es que el lenguaje nos arrastra, inclusive a nuestro pesar, a sus propios límites, y si no tenemos esto en cuenta para construir la Web Semántica estamos condenados desde el principio al fracaso.

 

Luego la naturaleza del conocimiento está limitada por el lenguaje como transmisor y por la propia estructura Psicoanalítica de los seres humanos. Y lo que representa el conocimiento entre los seres humanos, no es el pensamiento, sino y su medio transmisor, o sea el lenguaje. Entonces lo importante no es tanto la naturaleza del conocimiento, sino y la naturaleza de su medio transmisor el lenguaje, del que ya he dicho que es ambivalente y no es de sentido unívoco, y esto es lo que tenemos que tener en cuenta para construir la Web Semántica.

 

Un apunte más, los mitos que solemos despreciar por considerarlos anacrónicos, no modernos y anticientíficos, precisamente los mitos son lo que nos indican los límites de nuestra percepción de lo real, los límites de nuestro pensamiento, y todos ellos tienen además en común el uso de la metáfora, la cual nos marca el transcurso de lo real como paso del tiempo en la conclusión, por eso en los seres humanos no existe el problema de la parada como en la Máquina de Turing. Yendo más lejos y abundando más aún, tanto Hegel como Kant consideraron al tiempo no categorizable, o lo que es lo mismo para el Psicoanálisis, el tiempo es una ilusión de nuestra percepción, el tiempo es una forma de representar lo real como una sucesión o transcurso de acontecimientos. Y la Lógica Descriptiva (que son una familia de lenguajes de la Representación del Conocimiento y esta a su vez está basada en la Lógica Formal) que es la base utilizada actualmente para construir la Web Semántica, no puede dar cuenta del lenguaje, pues para empezar le falta la metáfora, ya que es una lógica matemática, la cual es una lógica simbólica consistente, donde por lo tanto se considera que el sistema axiomático es completo, y sólo posee por definición y construcción la metonimia careciendo la metáfora, y por supuesto como muy bien nos demostró ya Gödel, nos lleva finalmente a contradicción, que es lo que hasta ahora pasa con todos los intentos de construir la Web Semántica desde esta base: ¡Han resultado un completo y sonoro fracaso a pesar de la inversión multimillonaria en medios!. Pero sigue faltando lo fundamental, la base adecuada para transmitir el conocimiento, que como he  dicho anteriormente necesita del lenguaje, y el lenguaje tiene dos estructuras fundamentales:

La metonimia y la metáfora. A la metonimia ya la tenemos en el lenguaje matemático, todo en él es un proceso  metonímico, y si en algún momento entra el tiempo es como una ficción, f(t) o función del tiempo, pero no hay un uso de metáfora que es lo que impediría el sin sentido del sólo sentido metonímico, no hay un uso de la metáfora que es lo que introduciría lo real y llevaría a la conclusión solucionando el problema de la parada de la máquina de Turing.

 

Luego lo que tenemos que introducir es la metáfora en los fundamentos de la matemática, la cual nos permitiría construir una lógica inconsistente, pero no por ello contradictoria, similar a la lógica del inconsciente humano como lo entiende el psicoanálisis. Si lográramos tal objetivo, tendríamos las herramientas adecuadas para implementar la Web Semántica en los ordenadores, y funcionaría.

 

Y este es mi gran reto: Inventar una lógica no consistente, que además de la metonimia presente en la lógica matemática consistente, tenga también incorporada la metáfora.

 

 

8.- ¿Porque no intentar enseñar a hablar y/o a pensar a una máquina? Limitaciones y fracasos de la aproximación de la Lógica Descriptiva.

 

Cuando estudiaba ciencias, a lo largo de mi carrera alguno de mis profesores físicos y matemáticos, y con mucha experiencia, me hicieron las dos siguientes observaciones:

 

La primera, que cuando uno se enfrenta a un problema a resolver, el problema no te pregunta cuanto sabes, para así acomodarse a tu conocimiento y poder resolverlo; esto parece una verdad de perogrullo y del más puro sentido común, pero en este caso es más cierto que nunca.

 

La segunda observación, fue que “usualmente” todos los problemas tienen una solución que está “implícita” si la pregunta del problema está bien formulada, o dicho de otra forma si el marco de referencia del problema está bien construido.

 

El recordar y reconsiderar ambas observaciones, me ha hecho cambiar totalmente mi perspectiva inicial para abordar y resolver el problema de construir la “Web Semántica”; y así en lugar de aplicar directamente mis esfuerzos en su resolución, con la profunda y densa formación tanto física como matemática que recibí en mi formación como científico, y que entiendo ha sido la actitud usual de trabajo de todos aquellos que han trabajado hasta ahora en este campo intentando resolver este problema, y hasta ahora con escaso éxito, decía entonces que he preferido alejarme del problema particular y específico, y tomar una visión más general y amplia del mismo (lo que se entiende salir del bosque para poder ver su conjunto y no a un solo árbol), y para ello como decía,  en lugar de intentar directa y rápidamente su solución, estoy dando un largo rodeo, y no absurdo ni carente de sentido de acuerdo a las dos “observaciones” iniciales anteriores, sino y formulando un marco adecuado y lo más completo posible en donde inscribir dicho problema de construir la “Web Semántica”.

 

Para ello empecé estudiando de donde se partía para construir la “Web Semántica” en informática, y se parte actualmente de la Lógica Descriptiva, la cual a su vez toma como base a la Lógica Simbólica o Lógica Matemática .

 

Entonces como sé de las limitaciones de la Lógica Simbólica o formal, reflejada en los teoremas de Gödel y en numerosas paradojas matemáticas y físicas, he ampliado mi campo de conocimiento de las ciencias puras a las Humanidades, y si de lo que se trata entonces es de enseñar a hablar a un ordenador (o lo que es equivalente que un ordenador entienda lo que decimos), estamos preguntando por el lenguaje, y por ello incorporo a la lingüística en el marco de referencia del problema.

 

Podría haber acudido también a la filosofía, pero el problema que encuentro en ella al igual que en las matemáticas puras, es que sólo contempla y usa en sus desarrollos la lógica formal como sistema único de pensamiento, y esta objeción me viene además dada por el Psicoanálisis, el cual demuestra que usando solamente la lógica propia del sujeto o persona es muy fácil engañarse y/o entrar en contradicción, y no quiero autoengañarme en el sentido más literal del término.

 

 

9.- El Pensamiento y el Lenguaje.

 

Pero además la razón de recurrir al Psicoanálisis viene dada también por la necesidad de responder a la pregunta sobré qué es la inteligencia y qué es el pensamiento, necesarios para intentar enseñar de alguna manera a pensar por sí misma a una máquina; y esta respuesta me la puede dar el Psicoanálisis en combinación con la lingüística, no la psicología ni la biología, ni la genética, pues todas ellas al igual que la filosofía sólo usan una aproximación a lo real única y exclusivamente  cuantitativa, estadística, y con una lógica exclusivamente formal, y aunque es el método ortodoxo y propio de la ciencia, la lógica formal tiene graves limitaciones tanto lógicas por una parte, porque si  nuestras hipótesis son completas el sistema entra en contradicción, y si nuestras hipótesis son incompletas entonces el sistema es consistente. Decía que el método ortodoxo de la ciencia tiene graves limitaciones, además de lo anterior, por la exigencia de comprobación experimental, pues no todo lo que existe o es real es verificable experimentalmente, de forma cuantitativa y estadística, y si no se acepta esta limitación de acceso a lo real de forma absoluta, al menos hay que tomarla como hipótesis de trabajo, pues lo que estoy diciendo es que nuestra aproximación ortodoxa del método científico es incompleta y no nos permite resolver el problema del que tratamos. Y más aún, la Mecánica Cuántica de las Ciencias Físicas nos dice que si realizamos cualquier experimento, estaremos a nuestro pesar y aunque así no lo quisiéramos, cambiando las condiciones de aislamiento del experimento en el momento que tomemos de él los resultados, debido a nuestra propia interacción con dicho experimento; por todo ello es una ilusión, fantasía y un gravísimo error, intentar construir un sistema lógico perfecto en ciencia, cuyo único y exclusivo referente y garantía sea la experimentación, y un buen ejemplo de ello es la paradoja del Gato de Schrödinger.

 

 

Según el Psicoanálisis, el ser humano tiene una realidad que va mas allá de lo meramente biológico, por ello el ser humano no sigue exclusivamente y se regula por los instintos como es propio por los animales en el campo de la biología, según el Psicoanálisis el ser humano se regula por su relación con el “Goce” (las Pulsiones o Trieb que no son Instintos) en el sentido técnico de dicho término en Psicoanálisis. La importancia de este término tan “desconocido” para el resto de la ciencia, es que marca precisa y exactamente la diferencia entre los seres humanos y todo el resto de seres  vivos. Y precisamente esta diferencia se refleja y se traduce en que somos seres hablantes, y eso nos ha permitido construir nuestra civilización, cultura y tecnología. Por ello, todo lo lejos que pudiera llegar en hacer pensar o hablar a una máquina, nunca sería equivalente a un ser humano, pues su imbricación en lo real es distinta: el ser humano siente (y piensa) por y con el “goce” y la máquina aunque pudiera pensar o hablar no podría sentir, ya que no tiene ninguna relación con la “falta” y el “goce”. Y el sentido del término sentir, me refiero técnicamente en Psicoanálisis, a la falta de no ser completo, al dolor, que experimenta todo ser humano, de una forma particular para cada sujeto o individuo, y no generalizable en el sentido experimental, estadístico y cuantitativo de la ciencia, pero aún así, que no lo pueda demostrar científicamente no significa ciertamente que no sea real; y este enlace específico y particular del ser humano con la existencia, modifica profundamente su relación con lo real, de tal manera que no es reproducible, no ya experimentalmente fuera de cada sujeto, sino y además que no podemos “crearlo” y/o “reproducirlo” en una máquina; por ello afirmo que aunque lográramos que una máquina hablara, y por extensión tuviera alguna dimensión de nuestro pensamiento, nunca sería completa en el sentido de además experimentar la falta en lo real que experimenta todo ser humano. Las únicas pruebas fehacientes en tal sentido se pueden extraer de la clínica y/o psicopatología del Psicoanálisis, y como para llegar a intentar entender algo de ello es necesario ser un erudito psicoanalítico además de haberse psicoanalizado, lo podemos tomar al menos como una hipótesis y/o premisa cierta de trabajo: Si todas las premisas y/o hipótesis que establezco son correctas, debería de poder encontrar la solución a nuestro problema, y por lo tanto son mis resultados concretos en solucionar dicho problema lo que dará efectividad a la existencia de mis hipótesis de trabajo.

 

 

10.- El Pensamiento no es lo mismo que el Lenguaje, y el Cerebro no es lo mismo que la Mente. ¿Qué es la Inteligencia?.¿Qué es el Pensamiento?.

 

Ahora y a continuación estoy intentando definir que es el pensamiento, y según el Psicoanálisis, y tal como lo entiendo y lo traduzco yo mismo, el pensamiento es la conjunción de lo “simbólico” (el lenguaje), lo “imaginario” (el acceso particular de cada sujeto al lenguaje) y lo real del sujeto mismo, todos los términos formulados en el sentido técnico estricto del Psicoanálisis (lo Real, lo Imaginario y lo Simbólico); y de esta conjunción surge el sujeto o ser humano, por ello entiendo que el lenguaje es el medio del pensamiento mismo, aunque no es el pensamiento. Y el pensamiento es lo mismo que la Inteligencia, por lo que defino también la Inteligencia como  la conjunción de lo “simbólico” (el lenguaje), lo “imaginario” (el acceso particular de cada sujeto al lenguaje) y lo real del sujeto mismo.

 

Luego no necesito llegar a profundizar más en el pensamiento y la inteligencia, ya que no puedo dar un acceso a lo real  a una máquina a través de la “falta” y/o dolor de la existencia propia de los seres humanos (que es lo que da lugar a la condensación y crea las metáforas), por lo que me quedo para los fines que perseguimos solamente con el lenguaje, que me aproximarán a alguna dimensión del pensamiento, no exactamente igual que la de los seres humanos, pero al menos más potente que la mera lógica formal, y de allí saco dos mecanismos del mismo que son los que tenemos que trasladar a nuestra máquina de alguna manera: La metonimia y la metáfora; entiendo que estos son los dos mecanismos fundamentales del lenguaje humano (y del pensamiento), y son los que tendríamos que intentar trasladar a nuestra máquina.

 

 

11.- Diferencia entre los animales y los seres humanos

 

Un comentario más acerca de la naturaleza del pensamiento y el resto de seres vivientes, o sea los animales: los animales sólo tienen acceso a lo imaginario (Estadio del Espejo), que no es el lenguaje (lo simbólico) en sí, y no acceden al lenguaje, porque, entiéndase, que el lenguaje no sólo es la capacidad de hablar y/o transmitir conocimientos, el lenguaje es la capacidad simbólica de aprehender lo real (el mundo), y ello hace que no tengan relación directa con el “Goce” y/o la “falta”, por lo que en gran y/o total medida sus comportamientos están regulados por los “Instintos”, y son factibles de experimentación, y medidas cuantitativas y estadísticas, ya que son mecanismos biológicos y genéticos, y heredados del comportamiento para la supervivencia; mientras que el acceso al lenguaje (lo simbólico) del ser humano, provoca una transformación de la mera naturaleza biológica del cerebro, haciendo surgir la “mente”, la cual está relacionada con el “goce” y la falta. Me reitero expresamente para que se entienda bien: si no hay acceso al lenguaje tampoco hay acceso al “goce” y la “falta”, pero me pregunto: ¿puede haber algún tipo de acceso al lenguaje sin acceso al “goce” y o la “falta”?, y la respuesta la tenemos en los mismos ordenadores, ya que tienen acceso parcialmente al lenguaje, a través de la lógica simbólica, pero no tienen acceso al dolor ni al goce. Por todo ello incorporar el otro mecanismo del pensamiento y/o el lenguaje, la metáfora, a una máquina es muy complicado, porque no sólo tendríamos que construir una estructura lógica que además de la metonimia propia de la lógica simbólica, incorporase además un mecanismo metafórico en la lógica formal, pero eso surge en el ser humano de su relación con la falta y el goce, luego si no puedo incorporar el goce y la falta en una máquina, tampoco puedo incorporar la metáfora, y por lo tanto no podría enseñarle a hablar ni tampoco a pensar.

 

 

12.- Conclusión: Imposibilidad del Lenguaje y Pensamiento humano en las Máquinas, y el fracaso de la Inteligencia Artificial.

 

Luego por todo lo anterior, mi programa es fallido y no es posible enseñar el lenguaje y/o el pensamiento humanos a una máquina, ya que al carecer de relación alguna con el “goce”, no es posible introducir además de la metonimia, el otro mecanismo del lenguaje y del pensamiento, cual es la metáfora. Esta última surge de los procesos de elaboración del inconsciente y es la conclusión de ellos, luego el acceso a lo real como paso del tiempo está dado por la conclusión que nos permite construir la metáfora, y como ya he dicho anteriormente, podemos construir máquinas, pero no podemos construirlas con acceso al “goce”, por lo que es imposible lograr que hablen y/o puedan pensar tal y como lo hacen los seres humanos. Y respecto de los animales, sin embargo tendría que decir, que todos los animales tienen acceso a la “falta” de la existencia, pero al no poder simbolizar, carecen de los mecanismos del pensamiento humano, cuales son la metáfora y la metonimia, y por ello no pueden construir un lenguaje, lo que a su vez les permitiría construir un sistema simbólico que pudiera crear cultura, civilización y tecnología, cual es el caso de los seres humanos. Los animales tienen solamente una estructura imaginaria (estadio del espejo), y sólo son un cuerpo biológico, pues no hay separación del mismo como hacen los seres humanos por su estructura simbólica además de la imaginaria; luego los animales sí tienen “cerebro” pero no tienen “mente”.

Inteligencia es la capacidad de entender, asimilar, elaborar información y utilizarla adecuadamente, y la inteligencia es una facultad de la mente pero no del cerebro, pero para ello es necesario tener acceso al lenguaje, pues el medio de la inteligencia es el sistema simbólico (Lacan), luego si no podemos dar acceso al lenguaje a las máquinas, ¡todo el proyecto de la Inteligencia Artificial es un proyecto fallido!.  ¡No es posible hacer hablar (y por extensión pensar) a los ordenadores construyendo una Web Semántica!

La pregunta final que me surge de toda esta elaboración es entonces: ¿Por qué los seres humanos (que somos animales también) hemos podido hablar construyendo un mundo simbólico que aprehende lo real en un orden simbólico y sin embargo el resto de los seres vivos (los animales) no han podido hacerlo?, o de otra manera: ¿Por qué si tanto los animales como los seres humanos estamos relacionados con lo real de una forma biológica similar (aunque con muy pequeñas diferencias genéticas propias de las diferencias entre todas las especies vivientes) sin embargo el hombre ha accedido a la relación con el “goce” (que le ha permitido hablar) mientras que los animales sólo se han quedado en el estadio imaginario o del espejo y no tienen relación con el “goce”? Y estoy casi absolutamente seguro que las respuestas a ellas no provienen de la biología, la genética, ni de ninguna de las neurociencias…

 

 

13.- Teorema:  “El Límite de la Inteligencia Artificial”.

 

 

Probaré que no existe en absoluto la construcción de la Inteligencia Artificial, 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 Inteligencia Artificial 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 Inteligencia Artificial 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 Inteligencia Artificial, como una inteligencia con capacidades similares a la inteligencia humana, 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 Inteligencia Artificial, 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 de los teoremas de Gödel. La construcción de la Inteligencia Artificial es un problema Indecidible. 

 

 

 

14.- Teorema:  De la lógica a la ontología: “El Límite de la Web Semántica”.

 

 

Probaré que no existe en absoluto la construcción de la Web Semántica, 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 de los teoremas de Gödel. La construcción de la Web Semántica es un problema Indecidible. 

 

 

 

 

15.- Bibliografía y conceptos útiles.

 

 

Si usted lee los noventa y dos primeros post (a continuación más abajo) de Last Post Index & View del Blog Meta Internet, entonces puede estar seguro que entiende y conoce todos los conceptos necesarios para comprender este trabajo. 

También puede usar la búsqueda del mismo blog o buscarlos en Wikipedia en lengua inglesa y luego pinchar en idioma Español:

¡Siento las molestias pero WordPress no me ha permitido publicar los noventa y dos conceptos en Español!, ya que cuando lo hice en Inglés: 

¡Me amenazaron desde WordPress con cerrarme y clausurarme el blog con la excusa de que no había ningún trabajo original y tampoco he podido publicar en ninguna revista científica porque me dicen que no lleva matemáticas!, ¿y los teoremas por reducción al absurdo qué son entonces?

¡Y me tienen bloqueados todos los tags porque me dicen que tengo demasiados! Es cierto que tengo más de 50.000 links de enlaces pero no hay nada en su contrato de servicio que lo prohíba expresamente…

 

Computability theory (computer science) 
Computer science 
Computational complexity theory 
Semantic Web’s Terms & Companies & People & Organizations 
Information 
From Logic to Ontology: The limit of “The Semantic Web”  
Computation 
Computational problem 
Computer 
Mathematical object 
Algorithm 
Computer programming 
Programming language 
Mathematical proof 
Mathematical logic 
Syntax 
Operator Grammar 
Recursive categorical syntax 
Semantics 
Grammar 
In theoretical computer science, a formal grammar (sometimes simply called a grammar) is 
Ferdinand de Saussure 
Metaphor 
Language of thought 
Intuitionistic logic 
Propositional calculus 
First-order logic 
Second-order logic 
Infinitary logic 
Interface metaphor 
Metonymy 
Morphology (linguistics) 
Ferdinand de Saussure 
Phonology 
Language 
Natural language 
Formal language 
Theory of computation 
Formal semantics 
Specification language 
Pragmatics 
Meaning (linguistics) 
Polysemy 
Synchronic analysis 
Historical linguistics (also called diachronic linguistics) is the study of language change. 
Roman Jakobson 
Computational linguistics 
Discourse analysis 
Phonetics 
Sentence (mathematical logic) 
In theoretical computer science, a formal grammar (sometimes simply called a grammar) is a set of formation rules that describe which strings formed from the alphabet of a formal language are syntactically valid within the language. 
Chomsky hierarchy 
First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. 
Second-order logic 
Structuralism 
Ludwig Wittgenstein 
Claude Lévi-Strauss 
Jacques Derrida 
Jacques Lacan 
Metonymy 
Literal 
Literal and figurative language 
Trope (linguistics) 
Emphasis 
Hyperbole 
Parable 
Allegory 
Simile 
Synecdoche 
Irony 
Antanaclasis 
Rhetoric 
Semiotics 
Figure of speech 
Philosophy of language 
Sense and reference 
Connotation 
Denotation 
Reference 
Extension (semantics) 
Intension 
Intensional logic 
Web Ontology Language 
Ontology (the term in philosophy) 
Ontology (information science) 
Semantic Web 
Description logic 
Knowledge representation 
“Minds, Machines and Gödel: A Retrospect” 
Minds, Machines and Gödel — the original paper 

Read Full Post »

Teorema:  “El Límite de la Inteligencia Artificial”.

 

 

Probaré que no existe en absoluto la construcción de la Inteligencia Artificial, 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 Inteligencia Artificial 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 Inteligencia Artificial 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 Inteligencia Artificial, como una inteligencia con capacidades similares a la inteligencia humana, 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 Inteligencia Artificial, 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 de los teoremas de Gödel. La construcción de la Inteligencia Artificial es un problema Indecidible.

Read Full Post »

Teorema:  De la lógica a la ontología: “El Límite de la Web Semántica”.

 

 

Probaré que no existe en absoluto la construcción de la Web Semántica, 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 de los teoremas de Gödel. La construcción de la Web Semántica es un problema Indecidible.

Read Full Post »

Dear All,

I am not spamming the Wikipedia pages, neither Britannica.

I realize that all of you already know how to read the Wikipedia pages, and more, all the scientific literature about the “semantic web”…

I am researching about how to build the semantic web in a new and accurate way, from the foundations on linguistics, mathematics, logics, computers, philosophy, psychology, psychoanalysis, and many areas of knowledge and lot of people ask me:

Where did you read this or that? Then is useful for them to get the feedback to post step by step all the researching that I am doing!

Do you understand this new way of working and researching?

Please take a look about my theorem: The Limit of the “Semantic Web“, and you could realize what I am saying…

If you take a look on the Ninety-two posts below down, then you could realize that you understand the entire frame and the background that is needed to build the semantic web…

My next step is to review the original paper “Minds, Machines and Gödel” (“Minds, Machines and Gödel: A Retrospect”), and introduce the concept of “Time” on logic…

All of the foundations of the semantic web researching on Internet are on the basis of “Description logic”, who is a family of “knowledge representation” languages, but as my theorem has established this is the wrong way!

Then “the right way” is on the basis of the foundations on linguistics, mathematics, logics, computers, philosophy, psychology, psychoanalysis, and many areas of knowledge, where I am researching in a hard way…

 

Best Regards,

Francisco Antonio Ceron Garcia

fcerong @ gmail.com

Read Full Post »

Computability theory (computer science)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

For the branch of mathematical logic called computability theory, see Recursion theory.

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 possible to prove that any NFA is 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

This section may require cleanup to meet Wikipedia’s quality standards. Please improve this section if you can. (April 2009)

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. In other words, M cannot correctly distinguish between a string of equal number of ‘a’s and ‘b’s and a string with (n + d + 1) ‘a’s and n + 1 ‘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 automaton, 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

Main article: Zeno machine

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

1 + {1 \over 2} + {1 \over 4} + \cdots

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

[hide]

v  d  e

Computable knowledge

Topics and
Concepts

Proposals and
Implementations

In fiction

 
 
 
Dr. Know (A.I. Artificial Intelligence) • The Librarian (Snow Crash)

Read Full Post »

Computer science

Computer science

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Computer science (or computing science) is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.[1][2][3] It is frequently described as the systematic study of algorithmic processes that describe and transform information; the fundamental question underlying computer science is, “What can be (efficiently) automated?”[4] Computer science has many sub-fields; some, such as computer graphics, emphasize the computation of specific results, while others, such as computational complexity theory, study the properties of computational problems. Still others focus on the challenges in implementing computations. For example, programming language theory studies approaches to describing computations, while computer programming applies specific programming languages to solve specific computational problems, and human-computer interaction focuses on the challenges in making computers and computations useful, usable, and universally accessible to people.

The general public sometimes confuses computer science with vocational areas that deal with computers (such as information technology), or think that it relates to their own experience of computers, which typically involves activities such as gaming, web-browsing, and word-processing. However, the focus of computer science is more on understanding the properties of the programs used to implement software such as games and web-browsers, and using that understanding to create new programs or improve existing ones.[5]

Contents

[hide]

[edit] History

The early foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks, such as the abacus, have existed since antiquity. Wilhelm Schickard built the first mechanical calculator in 1623.[6] Charles Babbage designed a difference engine in Victorian times[7] helped by Ada Lovelace.[8] Around 1900, punch-card machines[9] were introduced. However, all of these machines were constrained to perform a single task, or at best some subset of all possible tasks.

During the 1940s, as newer and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors. As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s, with the creation of the first computer science departments and degree programs.[4][10] Since practical computers became available, many applications of computing have become distinct areas of study in their own right.

Although many initially believed it impossible that computers themselves could actually be a scientific field of study, in the late fifties it gradually became accepted among the greater academic population.[11] It is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM (short for International Business Machines) released the IBM 704 and later the IBM 709 computers, which were widely used during the exploration period of such devices. “Still, working with the IBM [computer] was frustrating…if you had misplaced as much as one letter in one instruction, the program would crash, and you would have to start the whole process over again”.[11] During the late 1950s, the computer science discipline was very much in its developmental stages, and such issues were commonplace.

Time has seen significant improvements in the usability and effectiveness of computer science technology. Modern society has seen a significant shift from computers being used solely by experts or professionals to a more widespread user base.

[edit] Major achievements

This section requires expansion.

The German military used the Enigma machine during World War II for communication they thought to be secret. The large-scale decryption of Enigma traffic at Bletchley Park was an important factor that contributed to Allied victory in WWII.[12]

Despite its relatively short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society. These include:

[edit] Fields of computer science

As a discipline, computer science spans a range of topics from theoretical studies of algorithms and the limits of computation to the practical issues of implementing computing systems in hardware and software.[17][18] The Computer Sciences Accreditation Board (CSAB) – which is made up of representatives of the Association for Computing Machinery (ACM), the Institute of Electrical and Electronics Engineers Computer Society, and the Association for Information Systems – identifies four areas that it considers crucial to the discipline of computer science: theory of computation, algorithms and data structures, programming methodology and languages, and computer elements and architecture. In addition to these four areas, CSAB also identifies fields such as software engineering, artificial intelligence, computer networking and communication, database systems, parallel computation, distributed computation, computer-human interaction, computer graphics, operating systems, and numerical and symbolic computation as being important areas of computer science.[17]

[edit] Theory of computation

The study of the theory of computation is focused on answering fundamental questions about what can be computed, and what amount of resources are required to perform those computations. In an effort to answer the first question, computability theory examines which computational problems are solvable on various theoretical models of computation. The second question is addressed by computational complexity theory, which studies the time and space costs associated with different approaches to solving a computational problem.

The famous “P=NP?” problem, one of the Millennium Prize Problems,[19] is an open problem in the theory of computation.

P = NP ?
Computability theory Computational complexity theory

[edit] Theoretical computer science

The broader field of theoretical computer science encompasses both the classical theory of computation and a wide range of other topics that focus on the more abstract, logical, and mathematical aspects of computing.

 P \rightarrow Q \, \Gamma\vdash x : Int
Mathematical logic Automata theory Number theory Graph theory Type theory Category theory Computational geometry Quantum computing theory

[edit] Algorithms and data structures

O(n2)
Analysis of algorithms Algorithms Data structures

[edit] Programming methodology and languages

Compilers Programming languages

[edit] Computer elements and architecture

Digital logic Microarchitecture Multiprocessing

[edit] Numerical and symbolic computation

y = sin(x) + c
Bioinformatics Cognitive Science Computational chemistry Computational neuroscience Computational physics Numerical algorithms Symbolic mathematics

[edit] Applications

The following disciplines are often studied from a more theoretical, computer science viewpoint, as well as from a more practical, engineering perspective.

Operating systems Computer networks Computer graphics Computer vision Databases
 
Computer security Artificial intelligence Robotics Human-computer interaction Ubiquitous computing

[edit] Relationship with other fields

Despite its name, a significant amount of computer science does not involve the study of computers themselves. Because of this, several alternative names have been proposed. Certain departments of major universities prefer the term computing science, to emphasize precisely that difference. Danish scientist Peter Naur suggested the term datalogy, to reflect the fact that the scientific discipline revolves around data and data treatment, while not necessarily involving computers. The first scientific institution to use the term was the Department of Datalogy at the University of Copenhagen, founded in 1969, with Peter Naur being the first professor in datalogy. The term is used mainly in the Scandinavian countries. Also, in the early days of computing, a number of terms for the practitioners of the field of computing were suggested in the Communications of the ACMturingineer, turologist, flow-charts-man, applied meta-mathematician, and applied epistemologist.[20] Three months later in the same journal, comptologist was suggested, followed next year by hypologist.[21] The term computics has also been suggested.[22] Informatik was a term used in Europe with more frequency.

The renowned computer scientist Edsger Dijkstra stated, “Computer science is no more about computers than astronomy is about telescopes.” The design and deployment of computers and computer systems is generally considered the province of disciplines other than computer science. For example, the study of computer hardware is usually considered part of computer engineering, while the study of commercial computer systems and their deployment is often called information technology or information systems. However, there has been much cross-fertilization of ideas between the various computer-related disciplines. Computer science research has also often crossed into other disciplines, such as cognitive science, economics, mathematics, physics (see quantum computing), and linguistics.

Computer science is considered by some to have a much closer relationship with mathematics than many scientific disciplines, with some observers saying that computing is a mathematical science.[4] Early computer science was strongly influenced by the work of mathematicians such as Kurt Gödel and Alan Turing, and there continues to be a useful interchange of ideas between the two fields in areas such as mathematical logic, category theory, domain theory, and algebra.

The relationship between computer science and software engineering is a contentious issue, which is further muddied by disputes over what the term “software engineering” means, and how computer science is defined. David Parnas, taking a cue from the relationship between other engineering and science disciplines, has claimed that the principal focus of computer science is studying the properties of computation in general, while the principal focus of software engineering is the design of specific computations to achieve practical goals, making the two separate but complementary disciplines.[23]

The academic, political, and funding aspects of computer science tend to depend on whether a department formed with a mathematical emphasis or with an engineering emphasis. Computer science departments with a mathematics emphasis and with a numerical orientation consider alignment computational science. Both types of departments tend to make efforts to bridge the field educationally if not across all research.

[edit] Computer science education

Some universities teach computer science as a theoretical study of computation and algorithmic reasoning. These programs often feature the theory of computation, analysis of algorithms, formal methods, concurrency theory, databases, computer graphics and systems analysis, among others. They typically also teach computer programming, but treat it as a vessel for the support of other fields of computer science rather than a central focus of high-level study.

Other colleges and universities, as well as secondary schools and vocational programs that teach computer science, emphasize the practice of advanced programming rather than the theory of algorithms and computation in their computer science curricula. Such curricula tend to focus on those skills that are important to workers entering the software industry. The practical aspects of computer programming are often referred to as software engineering. However, there is a lot of disagreement over the meaning of the term, and whether or not it is the same thing as programming.

[edit] See also

[edit] References

  1. ^Computer science is the study of informationNew Jersey Institute of Technology, Gutenberg Information Technologies
  2. ^Computer science is the study of computation.Computer Science Department, College of Saint Benedict, Saint John’s University
  3. ^Computer Science is the study of all aspects of computer systems, from the theoretical foundations to the very practical aspects of managing large software projects.Massey University
  4. ^ a b c Denning, P.J. (2000). “Computer Science: The Discipline” (PDF). Encyclopedia of Computer Science. http://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf. 
  5. ^Common myths and preconceptions about Cambridge Computer ScienceComputer Science Department, University of Cambridge
  6. ^ Nigel Tout (2006). “Calculator Timeline”. Vintage Calculator Web Museum. http://www.vintagecalculators.com/html/calculator_time-line.html. 
  7. ^ “Science Museum – Introduction to Babbage”. http://www.sciencemuseum.org.uk/on-line/babbage/index.asp. Retrieved on 2006-09-24. 
  8. ^ “A Selection and Adaptation From Ada’s Notes found in “Ada, The Enchantress of Numbers,” by Betty Alexandra Toole Ed.D. Strawberry Press, Mill Valley, CA”. http://www.scottlan.edu/Lriddle/women/ada-love.htm. Retrieved on 2006-05-04. 
  9. ^ “IBM Punch Cards in the U.S. Army”. http://www.pattonhq.com/ibm.html. Retrieved on 2006-09-24. 
  10. ^ http://www.cl.cam.ac.uk/conference/EDSAC99/statistics.html
  11. ^ a b Levy, Steven (1984). Hackers: Heroes of the Computer Revolution. Doubleday. ISBN 0-385-19195-2. 
  12. ^ a b David Kahn, The Codebreakers, 1967, ISBN 0-684-83130-9.
  13. ^ a b http://www.cis.cornell.edu/Dean/Presentations/Slides/bgu.pdf
  14. ^ Constable, R.L. (March 2000) (PDF). Computer Science: Achievements and Challenges circa 2000. http://www.cs.cornell.edu/cis-dean/bgu.pdf. 
  15. ^ Abelson, H.; G.J. Sussman with J.Sussman (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. ISBN 0-262-01153-0. “The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology — the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects.” 
  16. ^ Black box traders are on the march The Telegraph, August 26, 2006
  17. ^ a b Computing Sciences Accreditation Board (28 May 1997). “Computer Science as a Profession”. http://www.csab.org/comp_sci_profession.html. Retrieved on 2008-09-01. 
  18. ^ Committee on the Fundamentals of Computer Science: Challenges and Opportunities, National Research Council (2004). Computer Science: Reflections on the Field, Reflections from the Field. National Academies Press. ISBN 978-0-309-09301-9. http://www.nap.edu/catalog.php?record_id=11106#toc. 
  19. ^ Clay Mathematics Institute P=NP
  20. ^ Communications of the ACM 1(4):p.6
  21. ^ Communications of the ACM 2(1):p.4
  22. ^ IEEE Computer 28(12):p.136
  23. ^ Parnas, David L. (1998). “Software Engineering Programmes are not Computer Science Programmes“. Annals of Software Engineering 6: 19–37. doi:10.1023/A:1018949113292. , p. 19: “Rather than treat software engineering as a subfield of computer science, I treat it as an element of the set, Civil Engineering, Mechanical Engineering, Chemical Engineering, Electrical Engineering, ..”

[edit] Further reading

[edit] External links

Sister projectWikibooks has more on the topic of

Sister project Wikiversity has learning materials about Portal:Computer Science

[edit] Webcasts

[hide]

v  d  e

Major fields of computer science

Mathematical foundations

Theory of computation

Algorithms and data structures

Programming languages and Compilers

Concurrent, Parallel, and Distributed systems

Software engineering

System architecture

Telecommunication & Networking

Databases

Artificial intelligence

Computer graphics

Human computer interaction

Scientific computing

NOTE: Computer science can also be split up into different topics or fields according to the ACM Computing Classification System.
 
 
 
 
 
 
 
Computer architecture · Computer organization · Operating systems
 
Computer audio · Routing · Network topology · Cryptography
 
Data mining · Relational databases · SQL • OLAP
 
 
Visualization · Image processing
 
 
 

Read Full Post »

Computational complexity theory

From Wikipedia, the free encyclopedia

Jump to: navigation, search

This article may require cleanup to meet Wikipedia’s quality standards. Please improve this article if you can. (June 2009)

Computational complexity theory is a branch of the theory of computation in computer science that investigates the problems related to the resources required to run algorithms, and the inherent difficulty in providing algorithms that are efficient for both general and specific computational problems.

Contents

[hide]

[edit] Definitions

An engineer might ask “As the size of the input to an algorithm increases, by what factor does the running time and memory requirements increase? And what are the implications of that?” In other words, complexity theory, among other things, investigates the scalability of computational problems and algorithms. In particular, it places practical limits on what computers can and cannot do.

A problem is a collection of related questions, where each question is a finite string, not enumerated but written in an algebra called Big O notation, where the actual amount of resources uses numbers only to represent orders of magnitude and not the exact resources used by a particular machine.

[edit] Analysis

[edit] Big O notation

Main article: Big O notation

The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input, using the most efficient known algorithm. If an instance has length n and can be solved in n2 steps we can say the problem has a time complexity of n2.

But of course, the exact amount of resources will depend on what machine or language is being used. To avoid that difficulty, the Big O notation is generally used (the O stands for the “order” of the calculation). If a problem runs in O(n2) on one computer, then (barring perverse effects) it will also run in O(n2) on all others, even though it may take longer or shorter depending on what resources they have. So this notation allows us to generalize away from the details of a particular computer.

For example, searching an unsorted list of words for a particular word will take, on average, half the time of the size of the list, because if one starts from the beginning or end one must (on average) inspect half the words in the list before finding it. If the word does not exist, one must inspect the whole list to discover that fact, so actually it could be worse, depending on how likely it is that a word in the input is in the list.

But a binary search algorithm is logarithmic in time over size (it is O(log n)). By analogy, humans roughly know where an entry would be in a phone book or dictionary, and use strategies quickly to get to their target, such as using headwords or a thumb index quickly to get roughly to the right place, then use a linear search when they are close to the target.

It is important to note that most computational complexity theory is useful in other engineering fields and has made contributions to mathematics that would be of interest even if computers did not exist.

The master theorem can be useful to calculate the time complexity of a recursive algorithm.

[edit] Worst case analysis

A common approach to computational complexity is the worst-case analysis, the estimation of the largest amount of computational resources (time or space) needed to run an algorithm. In many cases, the worst-case estimates are rather too pessimistic to explain the good performance of some algorithm in real use on real input. To address this, other approaches have been sought, such as average-case analysis or smoothed analysis.

[edit] Axiomatic analysis

Main article: NP-complete

An axiomatic approach to computational complexity was developed by Manuel Blum. He introduced measures of complexity such as the size of a machine and measures of the computational overhead of recursive functions. The complexity of algorithms are special cases of the axiomatic complexity measure. Blum axioms help in the study of computational complexity in the most general cases.

An important aspect of the theory is to categorize computational problems and algorithms into complexity classes. The most important open question of complexity theory is whether the complexity class P is the same as the complexity class NP, or whether it is a strict subset as is generally believed.

Shortly after the question was first posed, it was realised that many important industry problems in the field of operations research are of an NP subclass called NP-complete. NP-complete problems have solutions that are quick to check, yet current methods to find those solutions are not “efficiently scalable” (as described more formally below). If the NP class is larger than P, then NP-complete problems admit no polynomial-time algorithm and any all-purpose solution to the problem is not efficiently scalable.

The fact that the P vs. NP problem has not been solved, prompts and justifies various research areas in the theory, such as:

  • spotting and solving special cases of common computational problems
  • the study of the computational complexity itself
  • finding heuristic solutions
  • researching into the hierarchies of complexity classes
  • exploring multivariate algorithmic approaches such as Parameterized complexity.

[edit] History

The first publication on computational complexity appeared in 1956.[1] But this publication in Russian was for a long time unknown in the Western world.

The beginning of studies in computational complexity can be attributed not only to Trahtenbrot,[2] but also to Rabin.[3][4][5][6][7]

Hartmanis and Stearns’ paper[7] became the most popular in this area. As a result, some researchers attribute the beginning of computational complexity theory only to Hartmanis, Lewis and Stearns.[8]

Andrey Kolmogorov‘s research in the theory of algorithms influenced the development of computational complexity theory. A notable early discovery was the Karatsuba algorithm in 1960, for the multiplication of two numbers. This algorithm disproved Kolmogorov’s 1956 conjecture that the fastest multiplication algorithm must be O(n2), and thus helped launch the study of algorithms in earnest. In 1967, Manuel Blum developed an axiomatic complexity theory based on his axioms and proved an important result, the so called, speed-up theorem.

The field was subsequently expanded by many researchers, including:

On August 6, 2002, the AKS primality test was published in a paper “PRIMES is in P”[9] by three Indian computer scientists. They showed a deterministic primality-proving algorithm they had made. The algorithm determines whether a number is a Prime number or Composite number in polynomial time, and was soon improved by others. The key significance of AKS is that it was the first published primality-proving algorithm to be all of general, polynomial, deterministic, and unconditional. The authors received the 2006 Gödel Prize and the 2006 Fulkerson Prize for their work.

[edit] Computational complexity theory topics

[edit] Time and space complexity

Complexity theory attempts to describe how difficult it is for an algorithm to find a solution to a problem. This differs from computability theory, which describes whether a problem can be solved at all: a branch of science probably made most famous by Alan Turing‘s essay On Computable Numbers, with an Application to the Entscheidungsproblem.

[edit] Decision problems

Much of complexity theory deals with decision problems. A decision problem is one where the answer is always “yes” or “no”. Some problems are undecidable, or at least seem so, so complexity theory can be used to distinguish problems where it is certain to get a correct “yes” or “no” (not necessarily both). A problem that reverses which can be relied upon is called a complement of that problem.

For example, the problem IS-PRIME says “yes” if its input is a prime and “no” otherwise, while the problem IS-COMPOSITE says “yes” if the number is not prime. Either may be unpredictable when the correct result would be “no”, they may say “yes” or perhaps never finish even if they were actually going to produce the right result, given an infinite number of monkeys.

Decision problems are often interesting to researchers because a problem can always be reduced to a decision problem. For instance, a problem HAS-FACTOR may be:

Given integers n and k find whether n has any prime factors less than k.

If we can solve this problem with known maximum resources we can use that solution to solve the next problem FACTORIZE without many more, using a binary search on factors of k until we find the smallest, divide out that factor and repeat until all the factors are found (i.e. we end up with 1 or 0).

[edit] Resources

Complexity theory analyzes the difficulty of computational problems in terms of many different computational resources. A problem can be described in terms of many requirements it makes on resources: time, space, randomness, alternation, and other less-intuitive measures[vague]. A complexity class is the class of all problems which can be solved using a certain amount of a certain computational resource.

There are other measures of computational complexity. For instance, communication complexity is a measure of complexity for distributed computations.

A different measure of problem complexity, which is useful in some cases, is circuit complexity. This is a measure of the size of a boolean circuit needed to compute the answer to a problem, in terms of the number of logic gates required to build the circuit. Such a measure is useful, for example, when designing hardware microchips to compute the function instead of software.

Perhaps the most studied computational resources are for determinism in time or space. These resources represent the amount of time or space needed by a deterministic computer. These resources are of great practical interest, and are well-studied.

Some computational problems are easier to analyze in terms of more unusual resources. For example, a nondeterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that nondeterministic time is a very important resource in analyzing computational problems.

Many more unusual computational resources have been used in complexity theory. Technically, any complexity measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum complexity axioms.

[edit] Complexity classes

A complexity class is the class of all of the computational problems which can be solved using a certain amount of a certain computational resource.

The complexity class P is the class of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases.[10]

The complexity class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. All the problems in this class have the property that their solutions can be checked efficiently.[10]

Many complexity classes can be characterized in terms of the mathematical logic needed to express them – this field is called descriptive complexity.

[edit] NP completeness and other open questions

[edit] P = NP

Main article: Complexity classes P and NP
See also: Oracle machine

The question of whether P = NP (can problems that can be solved in non-deterministic polynomial time also always be solved in deterministic polynomial time?) is one of the most important open questions in theoretical computer science because of the wide implications of a solution.[10] If the answer is yes, many important problems can be shown to have more efficient solutions that are now used with reluctance because of unknown edge cases. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems.[11][12]

The P = NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute the solution of which is a US$1,000,000 prize for the first person to provide a solution.[13]

Questions like this motivate the concepts of hard and complete

[edit] Hard

A class of problems X is hard for a class of problems Y if every problem in Y can be transformed “easily” (that is to say, it may take a lot of effort but the person solving the problem knows a solution exists) into some problem in X that produces the same solution. The definition of “hard” (or rather “easy”) problems differs by context. For P = NP, “hard” means NP-hard— a class of problems that are not necessarily in NP themselves, but to which any they can be reduced to an NP problem in polynomial time.

[edit] Complete

The class X is complete for Y if it is hard for Y and is also a subset of it.

Thus, the class of NP-complete problems contains the most “difficult” problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce another problem, Π1, to a known NP-complete problem, Π2, would indicate that there is no known polynomial-time solution for Π1. This is due to the fact that a polynomial-time solution to Π1 would yield a polynomial-time solution to Π2. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.[10]

[edit] Incomplete

Diagram of complexity classes provided that P ≠ NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.[14]

Incomplete problems are those in NP that are neither NP-complete nor in P. In other words, incomplete problems can neither be solved in polynomial time nor are they hard problems.

It has been shown that if P ≠ NP then there exist NP-incomplete problems.[14][15]

[edit] Graph isomorphism

An important unsolved problem in this context is, whether the graph isomorphism problem is in P, NP-complete, or NP-incomplete. The answer is not known, but there are strong hints that the problem is at least not NP-complete.[16] The graph isomorphism problem asks whether two given graphs are isomorphic.

[edit] The NP = co-NP problem

Co-NP is the class containing the complement problems (i.e. problems with the yes/no answers reversed) of NP problems. It is believed[who?] that the two classes are not equal; however, it has not yet been proven. It has been shown[15] that if these two complexity classes are not equal no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.

Every problem in P is also in both NP and co-NP. Integer factorization is an example of a problem in both NP and co-NP that is not known to be in P.

[edit] Intractability

Problems that can be solved but not fast enough for the solution to be useful are called intractable[17]. Naive complexity theory assumes problems that lack polynomial-time solutions are intractable for more than the smallest inputs. Problems that are known to be intractable in this sense include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable in this sense. To see why exponential-time algorithms might be unusable in practice, consider a program that makes 2n operations before halting. For small n, say 100, and assuming for the sake of example that the computer does 1012 operations each second, the program would run for about 4 × 1010 years, which is roughly the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. Nevertheless a polynomial time algorithm is not always practical. If its running time is, say, n15, it is unreasonable to consider it efficient and it is still useless except on small instances.

The graph shows time (average of 100 instances in msec using a 933 MHz Pentium III) vs.problem size for knapsack problems for a state-of-the-art specialized algorithm. Quadratic fit suggests that empirical algorithmic complexity for instances with 50–10,000 variables is O((log n)2). The data comes from [18]

[edit] Theory vs. practice

What intractability means in practice is open to debate. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time (see graph) and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

[edit] See also

[edit] References

  1. ^ Trahtenbrot (1956). 
  2. ^ Trahtenbrot (1967). 
  3. ^ Rabin, M. O. (1959). “Speed of Computation of Functions and Classification of Recursive Sets”.: 1–2, Proc. 3rd Conference of Scientific Societies. 
  4. ^ Rabin, M. O. (1960), Tech. Report 2, Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets, Jerusalem: Hebrew University, Jerusalem 
  5. ^ Rabin, M. O. (1963). Real-time computation. Israel Journal of Math. pp. 203–211. , Hartmanis, Lewis and Stearns
  6. ^ Hartmanis and Stearns (1964) 
  7. ^ a b Hartmanis and Stearns (1965) 
  8. ^ Aho, Hopcroft and Ullman (1976) 
  9. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin, “PRIMES is in P”, Annals of Mathematics, 160 (2004), 781–793
  10. ^ a b c d Sipser, Michael (2006). “Time Complexity”. Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 0534950973. 
  11. ^ Berger, Bonnie A.; Leighton, Terrance (1998). “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete”. Journal of Computational Biology 5 (1): p27–40. doi:10.1089/cmb.1998.5.27. PMID 9541869. 
  12. ^ Cook, Stephen (April 2000). The P versus NP Problem. Clay Mathematics Institute. http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf. Retrieved on 2006-10-18. 
  13. ^ Jaffe, Arthur M. (2006). “The Millennium Grand Challenge in Mathematics“. Notices of the AMS 53 (6). http://www.ams.org/notices/200606/fea-jaffe.pdf. Retrieved on 2006-10-18. 
  14. ^ a b Ladner, Richard E. (1975). “On the structure of polynomial time reducibility” (PDF). Journal of the ACM (JACM) 22 (1): 151–171. doi:10.1145/321864.321877. http://delivery.acm.org/10.1145/330000/321877/p155-ladner.pdf?key1=321877&key2=7146531911&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618. 
  15. ^ a b Du, Ding-Zhu; Ko, Ker-I (2000). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0. 
  16. ^ Arvind, Vikraman; Kurur, Piyush P. (2006), “Graph isomorphism is in SPP”, Information and Computation 204 (5): 835–852, doi:10.1016/j.ic.2006.02.002 
  17. ^ Hopcroft, et al. (2007), p. 368 
  18. ^ Pisinger, D. 2003. “Where are the hard knapsack problems?” Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

[edit] Further reading

  • Blum, Manuel (1967) On the Size of Machines, Information and Control, v. 11, pp. 257–265
  • Blum M. (1967) A Machine-independent Theory of Complexity of Recursive Functions, Journal of the ACM, v. 14, No.2, pp. 322–336
  • Downey R. and M. Fellows (1999) Parameterized Complexity, Springer-Verlag.
  • Hartmanis, J., Lewis, P.M., and Stearns, R.E. (1965) Classification of computations by time and memory requirements, Proc. IfiP Congress 65, pp. 31–35
  • Hartmanis, J., and Stearns, R.E. (1964) Computational Complexity of Recursive Sequences, IEEE Proc. 5th Annual Symp. on Switching Circuit Theory and Logical Design, pp. 82–90
  • Hartmanis, J., and Stearns, R.E. (1965) On the Computational Complexity of Algorithms, Transactions American Mathematical Society, No. 5, pp. 285–306
  • Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Boston/San Francisco/New York
  • van Leeuwen, Jan, (ed.) Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. Huge compendium of information, 1000s of references in the various articles.
  • Trahtenbrot, B.A. (1956) Signalizing Functions and Table Operators, Research Notices of the Pensa Pedagogical Institute, v. 4, pp. 75–87 (in Russian)
  • Trahtenbrot, B.A. Complexity of Algorithms and Computations, NGU, Novosibirsk, 1967 (in Russian)

[edit] External links

[hide]

v  d  e

Important complexity classes (more)

 
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH 

Read Full Post »

Older Posts »