MICRO
INVESTIGACION
Cuando hablamos de lenguajes formales y sus máquinas,
primeramente debemos definir que hay determinar que hay lenguajes que son
finitos y no finitos de los cuales tomaremos como una pilar para comprender que
son parte de la construcción de compiladores que incluyen lo que son:
analizador sintáctico, analizador semántico, analizador léxico.
Todos estos conforman el mecanismo de compilación de
un lenguajes independientemente de su generalidad, pero es importante reconocer
que hay lenguaje superior el cual mantiene una interpretación del lenguaje
normal de nosotros los seres humanos con el lenguaje maquinas los cuales son
mecanismo de virtualización de un algoritmo.
Un autómata de puede ir determinando de manera finita
y de pilas, en el cual el finito solo se puede componer de tres tipo de
gramáticas que puede ser te tipo regulares mientras que lo que son de plan son los que únicamente son 2 tipo de
gramáticas que son libres de contexto.
PARTE
1
Investigación
final del proyecto integrado de los problemas irresolubles
Cuando hablamos de los problema irresolubles
primeramente debemos ir haciendo una análisis, desde que habito podemos
llamarlos como problema que no pueden ser resueltos de manera, matemática y
lógica, por lo tanto podemos llegar a tomar como parámetro que una maquina no
los puede resolver, ya que ella aplican las dos parte a la misma ves pero antes
de eso en nuestra investigación logramos encontra concepto que nos ayudara a ir
reconociendo,
De qué tipo de máquinas es que hablamos y de qué
manera podemos ir tomando como problema irresolubles, que has el momento no
puede ser resueltos por persona que sido aplicadas a esta rama.
David Hilbert (1862-1943) formula el Entscheidungsproblem o problema de la decisión; la meta de
Hilbert era crear un sistema matemático formal “completo” y “consistente”, en
el que todas las aseveraciones pudieran plantearse con precisión. Su idea era
encontrar un algoritmo que determinara la verdad o falsedad de cualquier
proposición en el sistema formal.
Luego Alan Turing (1912-1954), en 1937 publicó un
trabajo sobre números calculables que pueden considerarse en parte como el
origen de la Informática Teórica.
Introdujo la Máquina de Turing (MT) como un modelo matemático abstracto que
permite formalizar el concepto de algoritmo.1/
Estos se caracterizan por no poseer ningún algoritmo
que los pueda resolver, sin importar que tengan o no solución. El identificar
entre un problema computable y otro que no lo es, resulta de gran importancia
para percibir el alcance y los límites de la computabilidad. La mayoría de las
demostraciones de no computabilidad se basan en el método de la diagonal.
Dicho método es una argumentación o demostración
matemática vislumbrada por Georg Cantor hacia 1891 para demostrar que el
conjunto de los números reales no es numerable.
Es entonces con el lanzamiento de la máquina de
Turing que comienzan a ponerla en pocas palabras a prueba, determinando una
serie de pasos o situaciones en la cual no puede contribuir con una solución a
una serie de problemas, conocido como el problema de la detención de la MT o el
problema de la parada, este fue el
primer problema que se demostró formalmente que no tenía solución.
“Sea M una máquina de Turing arbitraria con un
alfabeto de entrada Σ. Sea w ∈
Σ*. ¿Puede decidirse si la máquina M parará con la entrada w?”
Solución: La respuesta a esta pregunta es
negativa. No se puede determinar si una
máquina de Turing se detiene con una entrada arbitraria.
En teoría el anterior problema consiste en
determinar si una máquina de Turing cualquiera se parará en un tiempo
determinado sobre una entrada determinada. Podemos decir que no existe ningún
método que permita predecir en todos los casos, una vez que un computador ha
comenzado un cálculo, si dicho cálculo terminará alguna vez. En algunos casos,
lo más que puede hacer es ejecutar el programa y esperar. Este problema y sus
conclusiones son fundamentales en el tratamiento de los bucles infinitos. Para
intentar resolver este problema Turing imaginó una máquina equipada con una
caja negra, un oráculo, que sería un mecanismo que llevaría a cabo las tareas
no computables. El oráculo consistiría en un dispositivo medidor perfecto más
una memoria que contiene un valor de cierta magnitud física. Este valor es un
número irracional, y su propiedad sería que en sus dígitos representaría los
programas que terminan y los que no. Hoy día no existe ninguna forma
practicable de materializar un oráculo. De ser encontrada, el impacto sobre las
ciencias de cómputo sería enorme. Pero mientras tanto, sólo nosotros podemos
ver si un bucle es infinito y saber cuándo parar el proceso.
PARTE
2
Investigación
final del proyecto integrador de los problemas irresolubles
Dentro de la área de la
Teoría de la computación se puede ir comprendiendo que en la rama de los
lenguajes regulares pueden haber problemas que pueden solucionarse con
algoritmos es decir son resolubles, llámese algoritmo a alguna lista ordenada
de operaciones que tienen el propósito de buscar la solución a algún problema
tanto de la vida real simulada como un problema de la área de matemática,
informática, etc.
Analizando lo anterior se puede determinar
que pueden llegar a existir problemas que no pueden ser resueltos por un
algoritmo, es entonces que se pueden explicar que anteriormente existieron
matemáticos, que decidieron plantearse problemas y comprobar si con una maquina
o algún algoritmo podría solucionarse.
Para la aclaración anterior
se conoce poco de los problemas que se presentaran en esta investigación, pero
aun así se determinara de alguna manera que aun al pasar de los tiempos estos
problemas aún siguen siendo como se determina el tema problemas
algorítmicamente irresolubles, la mayoría de estos teoremas o problemas son
basados a la Maquina de Turing (MT) ya que es una maquina “infinita” en cuanto
a la solución de cualquier problema matemático expresándolo por un algoritmo.
Donde se menciona y determina la justificación en la
cual se puede mencionar la importancia de dicha investigación para el grupo
investigador.
En el capítulo 4 se plantean
los objetivos que se establecen como los
logros que esperan obtener con la investigación desarrollada y las deferentes
comprobaciones que se lograron comprendiendo un general para toda la
investigación y algunos específicos.
Se comprende que se relaciona con la teoría que constituye la base donde se
sustentará cualquier análisis, experimento o propuesta de desarrollo de este
trabajo. Incluso de cualquier escrito de corte académico y científico.
El análisis,
interpretación y comprobación de resultados de la investigación se formulan las
conclusiones como grupo establecimos de la misma manera una serie de
recomendaciones para demás personas que se adentren a este mundo de los
problemas algorítmicamente irresolubles.
Se incluye las fuentes bibliográficas de consulta, las fuentes virtuales utilizadas para
tener acceso a las teorías que sustentan de alguna manera el trabajo de
investigación y por lo consiguiente tanto se presenta los anexos que se consideraron
de acuerdo a la investigación.
Y dentro de nuestra
investigación llegamos a concluir en la explicación lógica de por qué los
problema pueden se conocidos como problema irresolubles.
Ejemplo.
Ya estableciendo dicho
problema, podemos dar paso al muy conocido como problema de los puentes de
Königsberg, también llamado más específicamente problema de los siete puentes de Königsberg, El problema, formulado originalmente de manera
informal, consistía en responder a la siguiente pregunta:
“Dado
el mapa de Königsberg, con el río Pregel dividiendo el plano en cuatro regiones
distintas, que están unidas a través de los siete puentes, ¿es posible dar un
paseo comenzando desde cualquiera de estas regiones, pasando por todos los
puentes, recorriendo sólo una vez cada uno, y regresando al mismo punto de
partida?”
Comprendiendo entonces que
establecemos un punto de salida, el cual por más que queramos utilizar y determinar una ruta que
nos lleve de nuevo al punto de salida no existe ya que de manera que siempre se
pasa por un puente dos veces.
Aun en todo caso el mismo creador del teorema
Königsberg, no llego a solucionarlo de manera que resurgiera el algoritmo
correcto.
Es importante destacar como
un simple maquina puede determinar algoritmos para la solución de problemas, y
de como un algoritmo es de carácter general y puede aplicarse a cualquier
operación matemática o a cualquier problema.
Los algoritmos son una de
las herramientas más complejas y aplicables en el área de la informática y el
mundo de los computadores (Maquinas de Turing). Se puede comprobar que mientras
más potente, completo y eficiente es el computador o la aplicación que corre
sobre el mismo más grande, complejo y exacto es el algoritmo que utiliza. Las
técnicas de desarrollo de algoritmos nos permiten encontrar la mejor solución a
los problemas que se nos presentan y deben ser solucionados por el computador,
estas técnicas están orientadas para utilizarse en cada uno de los niveles de
complejidad y variedad o alternativas para las cuales se aplican los
algoritmos. Un algoritmo es el conjunto de operaciones y procedimientos que
deben seguirse para resolver un problema, es por ellos que debemos estudiarlos
y conocerlos.
Dentro de la vida real, nos podemos encontrar con muchos más problemas
que pueden no tener solución pero no los vemos, sin embargo existen personas y
matemáticos que siguen investigando como resolver problemas con algoritmos,
para beneficios de otras personas, como por ejemplo el problema de la parada,
el problema de Axiomatizar toda la física o Probar la finitud de ciertos
sistemas completos de funciones, entre otros.
