Autómatas

Teoría de Autómatas.

Antes de entrar a la teoría de autómatas necesitamos previos conocimientos de lógica matemática. A continuación veremos  definiciones básicas.

Definición I.

Preposición: Expresión  enunciativa a la que se le puede atribuir  un sentido o función lógica en la cual se puede predicar su veracidad o falsedad, esta puede ser verdadera o falsa. 

Lógica proporcional.

Negación.

Definición II. Sea p una preposición, su negación se escribe  ¬p  o ~p, se lee no p.

Tabla de verdad.

p	¬p
F	V
V	F

Es verdadera cuando p es falsa y viceversa.

Conjunción.

Definición III. Sean dos proposiciones p y q, la conjunción de estas dos preposiciones se escribe p  ^ q y se lee p y q.

Tabla de verdad.

p	q	p^q
V	V	V
F	F	F
V	F	F
F	V	F

p y q es verdadera cuando ambas son verdaderas, y falsas en otro caso.

Disyunción.

Definición IV. Sean dos proposiciones p y q, la disyunción de p y q se escribe p v q y se lee p o q.

Tabla de verdad.

p	q	p v q
V	V	V
F	F	F
V	F	V
F	V	V

p o q  es verdadera cuando al menos una de ellas es verdadera, solo es falsa cuando las dos preposiciones son falsas.

Condicional.

Definición V. Sean dos preposiciones p y q, la condicional  de p y q se escribe p → q y se lee p entonces q.

Tabla de verdad.

p	q	p → q
V	V	V
F	F	V
V	F	F
F	V	V

p → q solo es falsa cuando p (el antecesor) es verdadero y q (consecuente) es falso.

Se dice que es una causa y efecto  si p entonces q.

Equivalencia.

Definición VI. Sean dos proposiciones p y q, la equivalencia se escribe p ↔ q y se lee p si y solo si q o p equivale a q.

Tabla de verdad.

p	q	p ↔ q
V	V	V
F	F	V
V	F	F
F	V	F

P equivale  a q, es verdadera cuando p y q son ambas verdaderas o ambas falsas.

La equivalencia también se conoce como doble implicación o como bicondicional. 

Nota: En los motores de busqueda como Google, Altavista , etc, se pueden utilizar las sentencias or and y not por ejemplo  (discretas or finitas) and matematicas, colocando esto en la  busqueda  se desplegaran todas las paginas con contenidos de matematicas discretas  o matematicas finitas

Bibliografía.

Scribd.com:

http://www.scribd.com/doc/3984030/Logica-Proposicional.

mitecnologico.com:

http://www.mitecnologico.com/Main/Proposiciones.

Introducción a la lógica matemática. P, Suppes /S, Hill. ISBN: 9789686708011.

Matemáticas discretas sexta edición. Richard Johnsonbaugh. ISBN: 9702606373.

Historia V

Breve historia de la computación teórica parte final

Conclusiones.

La teoría computacional  trabaja en la construcción de formalismos matemáticos para así razonar sobre la existencia de algoritmos efectivos para problemas particulares. Estos resultados obtenidos dentro de esta teoría deben ser también aplicables a todas las arquitecturas computacionales, independientemente de sus parámetros por ejemplo la velocidad del procesador o el tamaño de memoria.

.

Historia IV

Breve historia de la computación teórica parte IV.

Stephen Cole Kleene

Nació el 5 de enero de 1909 en Hartford, Connecticut, Estados Unidos y muere el 25 de enero de 1994 en madison, Wisconsin.

Kleene trabajo en la lógica matemática, sus aportaciones a la teoría computacional son la teoría de las funciones μ-recursivas la cual  basa su  mecanismo de computo en la composición de funciones y no en la transición entre estados (programación funcional), también se especializo en el estudio de las funciones recursivas y la teoría de los autómatas. 

Las funciones μ-recursivas.

Son una clase de funciones de los números naturales donde los números naturales son computables  desde un sentido intuitivo, las funciones  recursivas  pueden ser calculadas  con un formalismo de cómputo con una maquina de Turing.

Aportaciones en autómatas.

AF→ER. Teorema de Kleene

ER→AF. Teorema de Kleene.

Publicaciones:

La representación de eventos en redes nerviosas y autómatas finitos. Estudio de autómatas 1956.

Bibliografía.

student.cs.uwaterloo.ca:

http://www.student.cs.uwaterloo.ca/~cs462/Hall/kleene.html

Computacion, Curso 2007-08, Universidad de Sevilla:

www.cs.us.es/curso/comp/comp-t4.pdf

www-history.mcs.st-and.ac.uk:

www-history.mcs.st-and.ac.uk/Mathematicians/Kleene.html 

Documentos del dominio publico sin autor.

Historia III

Breve historia de la computación teórica parte III.

Alonzo Church.

Nació el 14 de junio de 1903, Washington y muere el 11 de agosto de 1995. Se especializo  en lógica matemática  y matemáticas.

Su obra más conocida es el desarrollo de el lambda cálculo a pesar de que en esa época las computadoras no existían  se pudo considerar como el primer lenguaje funcional de la historia, sus fundamentos son la base de la teoría de la programación funcional y de lenguajes funcionales posteriores.

El cálculo lambda  se uso en 1936 para resolver el Entscheidungsproblem. Puede se utilizado para definir  de manera concreta y precisa que es  un función computable.

El lambda cálculo es universal  para cualquier función computable, puede ser expresada y evaluada como también lo hace la maquina de Turing. Según la tesis de Church-Turing, ambos modelos pueden expresar cualquier cómputo  posible.

Bibliografía.

Biografiasyvidas.com:

http://www.bigrafiasyvidas.com/biografia/c/church_alonzo.html

Enciclopedia.us.es:

http://enciclopedia.us.es/index.php/C%C3%A1lculo_lambda

Monografias.com:

http://www.monografias.com/trabajos30/paradigma-funcional/paradigma-funcional.shtml

Articulos de dominio publico sin autor.

Historia II

Breve historia de la computación teórica parte II.

Teoremas de incompletud.

Kurt Godel  nace el 28 de Abril de 1906 en Brunn Moravia, Austro-Hungría actualmente República  Checa y muere  el 14 de Enero de 1978 en Princeton, New Jersey  como ciudadano estadounidense.

Conocido por sus celebres teoremas de la incompletud, que fueron publicados  en 1931 cuando el tenia 25 años.

Sus teoremas son una gran contribución ya que con ellos, posteriormente Alonzo Church y Alan Turing  resolvieron el Entscheidungsproblem de Hilbert. 

Teoremas de incompletud.

Publicados en un articulo llamado Preposiciones Formalmente Indecidibles en Principia  Mathematica y Sistemas Relacionado, donde se dan a conocer como el teorema VI.

A continuación se presentan los teoremas:

Teorema I: En cualquier formalización consistente de las matemáticas que sea lo bastante fuerte para definir el concepto de número naturales, se puede construir una afirmación que ni se puede demostrar y tampoco refutar dentro de ese sistema.

El segundo teorema, se demuestra formalizando  parte de la prueba del primer teorema dentro de su propio sistema, se puede frasea de la siguiente manera.

Teorema II: Ningún sistema consistente se puede usar para demostrase a sí mismo.

Números Calculables.

Alan Mathison Turing nace el día 23 de junio de 1912 en Maida Vale, Londres y muere en el 7 de junio de 1954 en Cheshire, Inglaterra.

En 1937 Turing publico un artículo que trataba sobre los números calculables con una aplicación al Entscheidungsproblem  de Hilbert (On computable numbers, with an application to the Entscheidungsproblem). Donde Turing reformuló los resultados obtenido por Kurt Godel (Teoremas de incopletud).

Donde sustituye el lenguaje forma universal usado por Godel por lo que en la actualidad conocemos como maquina de Turing.  La maquina de Turing es una entidad matemática abstracta que formaliza el concepto  de algoritmo.

Con este articulo demostró que dicha maquina es capaz de resolver cualquier problema matemático que pudiera representarse mediante un algoritmo como también demostró que hay problemas irresolubles. Llego a demostrar que no existe solución para el problema de decisión (Entscheidungsproblem).

Con estas afirmaciones se dice que hay problemas irresolubles, tales que ninguna maquina de Turing será capaz de obtener su solución por lo tanto se concluye que tampoco ningún sistema computacional lo obtendrá.

Bibliografía.

thales.cica.es :

http://thales.cica.es/rd/Recursos/rd97/.../08-1-b-godel.html

biografiasyvidas.com :

http://www.biografiasyvidas.com/biografia/t/turing.html

Wikippedia:

http://es.wikipedia.org/wiki/Kurt_G%C3%B6del

http://es.wikipedia.org/wiki/Alan_Turing

Articulos relacionados de dominio publico sin autor.

Historia

 Breve historia de la computación teórica

 Quien es David Hilbert?

Nació el 23 de enero de 1862 en Konigsberg, Prusia  y murió el 14 de febrero de 1943 en Gottingen, Alemania. 

Matemático famoso del siglo XX, estas son algunas de sus aportaciones a las matemáticas: Teoría de invariante, Axiomas de la geometría, Análisis funcional, etc.

En 1900 En el Congreso Nacional de Matemáticos en Paris. Hilbert propuso una lista de 23 problemas sin resolver.

1. Problema de Cantor sobre el cardinal del continuo. ¿Cuál es el cardinal del continuo?
2. La compatibilidad de los axiomas de la aritmética. ¿Son compatibles los axiomas de la aritmética?
3. La igualdad de los volúmenes de dos tetraedros de igual base e igual altura.
4. El problema de la distancia más corta entre dos puntos. ¿Es la línea recta la distancia más corta entre dos puntos, sobre cualquier superficie, en cualquier geometría?
5. Establecer el concepto de grupo de Lie, o grupo continuo de transformaciones, sin asumir la diferenciabilidad de las funciones que definen el grupo.
6. Axiomatización de la física. ¿Es posible crear un cuerpo axiomático para la física?
7. La irracionalidad y trascendencia de ciertos números como e, 2^v2, etc.
8. El problema de la distribución de los números primos.
9. Demostración de la ley más general de reciprocidad en un cuerpo de números cualesquiera.
10. Establecer métodos efectivos de resolución de ecuaciones diofánticas.
11. Formas cuadráticas con coeficientes algebraicos cualesquiera.
12. La extensión del teorema de Kronecker sobre cuerpos abelianos a cualquier dominio de racionalidad algebraica.
13. Imposibilidad de resolver la ecuación general de séptimo grado por medio de funciones de s ólo dos argumentos.
14. Prueba de la condición finita de ciertos sistemas completos de funciones.
15. Fundamentación rigurosa del cálculo enumerativo de Schubert o geometría algebraica.
16. Problema de la topología de curvas algebraicas y de superficies.
17. La expresión de formas definidas por sumas de cuadrados.
18. Construcción del espacio de los poliedros congruentes.
19. Las soluciones de los problemas regulares del cálculo de variaciones, ¿son siempre analíticas?
20. El problema general de condiciones de contorno de Dirichlet.
21. Demostración de la existencia de ecuaciones diferenciales lineales de clase fuchsiana, conocidos sus puntos singulares y grupo monodrómico.
22. Uniformidad de las relaciones analíticas por medio de funciones automórficas: siempre es posible uniformizar cualquier relación algebraica entre dos variables por medio de funciones automorfas de una variable.
23. Extensión de los métodos del cálculo de variaciones.

Algunos ya han sido resueltos, otros no han tenido gran relevancia y algunos siguen siendo un gran reto para los matemáticos actuales.

Más tarde en 1928 en una coferencia internacional Hilbert formula el Entscheidungsproblem de Hilbert.

El  Entscheidungsproblem.

Fue un reto a la lógica simbolica lanzado por Hilbert que preguntaba si existia algún algoritmo general que decidiera si una formula de cálculo de primer orden es un teorema. 

continuara........