Gramatica Libre de Contexto y Autómata PushDown

ApuntesDeLaura

 

Gramatica Libre de Contexto

Dejemos de prestar atención a los lenguajes regulares para una clase mayor de lenguajes, los llamados “lenguajes libre de contexto”. Estos lenguajes tienen una notición de manera natural, una notación recursiva.

Se puede decir que es una notación para describir lenguajes.

Es mas poderosa que cualquier autómata finito, pero aun así no puede describir todos los lenguajes.


Partes de un Lenguaje Libre de Contexto

Captura de pantalla 2017-04-20 a las 2.26.37 p.m.

Diagrama de como Verlos

Una Explicación mas Detallada

  • T: Terminales / Alfabeto de Símbolos de Entrada, podemos también llamarlo las terminales, o símbolos terminales.
  • V: Conjunto de Variables, también los llaman no terminales o categorías sintácticas. Cada variable representa con conjunto de strings, digamos un sub lenguaje.
  • S: Conjunto de variables “Especiales”, representa un lenguaje bien definido, lo llaman también el símbolo inicial, también puede ser que haya otras variables que sean auxiliares.
  • P: Una Función de Producción / Derivación, son un conjunto finito de reglas que muestran de manera recursiva una definición del lenguaje.

  Es más esto vale la pena verlo, veamos como:

Cada Producción Consta de:

Captura de pantalla 2017-04-20 a las 3.04.39 p.m.

Una variable que esta siendo (parcialmente) definido por la producción, esta variable la llaman de forma común la cabeza de la producción.

Una cadena de cero o mas variables y quizá algunos terminales, el string lo suelen llamar el cuerpo de la producción, que representa una forma de generar los strings, donde simplemente basta con sustituir las variables que estén dentro del cuerpo.

Captura de pantalla 2017-04-20 a las 2.46.04 p.m.

Ejemplo

Ideas Generales

  • Usar las variable para formar conjuntos de strings, osea lenguajes.
  • Estas variables están definidas de manera recursiva, en términos de otras.
  • Las reglas recursivas solo tienen que ser concatenaciones.
  • Puedes genera una unión de lenguajes con dos reglas alternativas.

 

Derivación

  1. Para crear una palabra del Lenguaje, lo que tendremos que hacer será:
  2. Iniciar con nuestra variable de cadena o string
  3. Sustituir esa expresión en alguna regla de Producción.
  4. Repetir el Paso 3 hasta que no queden mas que terminales.

 


Ejemplo:

Veamos un ejemplo de estos lenguajes de esta manera:

Crear Strings Binarios de la Forma  0^n 1^n

  • Terminales : { 0, 1 }
  • Variables : { S }
  • Simbolo de Inicio : { S }
  • Producto :
    • S -> 01
    • S -> 0S1

 

 

 


Notación BNF:

Hay varias formas estándar de trabajar estos lenguajes, esta notación es muy muy común en programación, es conocida como Backus-Naur Form así que veámosla:

  • (V) Variables – Se ponen así: <Variable>
  • (T) Terminales – Se ponen así: TerminalUno / TerminalDos
  • (->) Producción – Se ponen así: ::=
  • (S -> a | b) Simplificación para dos reglas usando la misma regla: S -> a y S -> b

Ejemplos:

Usando esta notación nos permite hacer cosas como esta, Naturales:

  • Terminales : { 0, 1, 2, 3, 4, 5, 6,7 8, 9 }
  • Variables : { U, D }
  • Simbolo de Inicio : { U }
  • Producto :
    • U  ::=  UD | D
    • U  ::=  0|1|2|3|4|5|6|7|8|9

 

 

 

 

 


Automatas de Pila

Podemos pensar en los Autómatas PushDown de la siguiente manera:

  • Un Automata ε-NFA
  • Un Pila bastante especial
Captura de pantalla 2017-04-17 a las 8.52.53 p.m.

Un Dibujito nunca esta de más

Así con cada simbolo que va leyendo el autómata puede hacer 2 acciones:

  • Moverse a otro estado
  • También si lo necesita afecta (push, pull) la pila

De manera totalmente formal podemos definir cualquiera de los PDA como:

Captura de pantalla 2017-04-17 a las 8.50.07 p.m.

Definición Formal

¿Parece bastante sencillo verdad?

Pues la verdad es que no es tan complejo como tu te podrías imaginar.

Estado Inmediato

Podemos describir el “estado” en cada momento con toda la información del autómata con 3 cosas:

  • El estado actual del autómata
  • El símbolo que estamos leyendo
  • El simbolo en el tope de la pila

Lenguajes y Expresiones Regulares

Ahora vamos a centrar nuetra atención a lo que llamaremos una expresión regular, esta sirve como una descripcion algebraica de un lenguaje, de un lenguaje regular, la gran ventaja de trabajar con expresiones regurales en vez de con automatas que es las primeras te permiten ver visulamente (o de forma declarativa) las cadenas que vamos a aceptar.



Operaciones

Antes de nada veamos las operaciones en las expresiones regulares:

Unión:

Captura de pantalla 2017-03-31 a las 11.45.47 a.m..png

Veamos un ejemplo:

Captura de pantalla 2017-03-31 a las 11.51.20 a.m.

Concatenación:

La concatenación es el conjunto de todos las cadenas que se crean de concatenar cualquiera de las cadenas de los dos lenguajes.

Captura de pantalla 2017-03-31 a las 11.56.24 a.m.

Veremos un ejemplo:

Captura de pantalla 2017-03-31 a las 11.56.16 a.m.

Recuerda que epsilon es la “identidad” de las concatenaciones, es decir, que calculo la cadena concatenada con epsilon es la misma cadena.

Cerradura de Kleene:

Captura de pantalla 2017-03-31 a las 12.29.39 p.m..png

La cerradura es una operacion muy importante, esta te devuelve todos los strigns que pueden ser formados con al hacer la concatenacion de cualquier cantidad de strings de L.
Veamos un ejemplo, así podemos sacar las primeras iteraciones:

Captura de pantalla 2017-03-31 a las 12.29.25 p.m..png

Formas de una RE

Tenemos que saber que no solo hay una forma de expresar las expresiones regulares, por ejemplo, veamos como hacer una RE que sea capaz de recibir cadenas alternantes de 1 y 0.

L = { ε, 0, 1, 101, 10101, 1010101 … 01, 010, 01010 …}

Captura de pantalla 2017-03-31 a las 12.52.39 p.m.

Forma A

Captura de pantalla 2017-03-31 a las 12.52.50 p.m.

Forma B

Ejemplos:

(0 + 10*) L = { 0, 1, 10, 100, 1000, 10000, … }
(0*10*) L = {1, 01, 10, 010, 0010, …}
(0 + ε)(1 + ε) L = {ε, 0, 1, 01}
(a+b)*  L = { ε, a, b, aa , ab , bb , ba, aaa, …}
(a+b)*abb  L = {abb, aabb, babb, aaabb, abad, …}

Propiedades

Captura de pantalla 2017-03-31 a las 1.22.09 p.m.

Básica

Captura de pantalla 2017-03-31 a las 1.22.34 p.m.

No tan básicas

Captura de pantalla 2017-03-31 a las 1.22.26 p.m.

Las más Hardcore

 


De Expresiones Regulares a Autómatas

 

Para lograr esto vamos a ver varias “ε-NFA” base que nos sirve para encontrar RE más complejas:

  • Si el ε-NFA describe un RE: a

automata4

  • Si el ε-NFA describe un RE: Ø

Es deir, es imposible que exista tal RE.

automata5

 

  • Si el ε-NFA describe un RE: ε

Es decir, acepta cualquier RE.

automata6

  • Si el ε-NFA describe un RE: RS

Es decir, acepta cualquier RE que sea la concatenación de R seguido de S.

automata2.png

  • Si el ε-NFA describe un RE: R*

Es decir, acepta cualquier RE que sea la cerradura de R*.

automata1

  • Si el ε-NFA describe un RE: R+S

Es decir, acepta cualquier RE que bien R o S.

automata3

 

Ejemplo:

Usando esto, como piezas de LEGO, podemos hacer cualquiera RE, veamos todo esto con un ejemplo:

Captura de pantalla 2017-04-15 a las 4.30.53 p.m.

 

  • Primer Paso: Hacer un RE que exprese 0 + 1

Captura de pantalla 2017-04-15 a las 4.31.11 p.m.

  • Segundo Paso: Hacer un RE que exprese (0 + 1)*

Captura de pantalla 2017-04-15 a las 4.31.20 p.m.

  • Tercer Paso: Hacer un RE que exprese (0 + 1)*1(0 + 1)

Captura de pantalla 2017-04-15 a las 4.31.38 p.m.

 

 

 


De Automata a Expresión Regular

Los K-Caminos

No haré la explicación pero basado en estos diagramas podemos llegar a :

Captura de pantalla 2017-03-31 a las 1.48.03 p.m.

Captura de pantalla 2017-03-31 a las 1.48.10 p.m.

Recuerda que K no puede ser mas grande que la cantidad de estados:

Captura de pantalla 2017-03-31 a las 1.54.28 p.m.

Formula más pro

Espera, espera, ¿Que significa esta “fórmula”?

Para encontrar el Universo de las RE que acepta nuestro autómata tenemos que encontrar los K-Caminos…. Si, esto se explica mejor con un ejemplo…

Encontrar la RE de nuestro DFA (Ejemplo):

Captura de pantalla 2017-03-31 a las 2.11.27 p.m.

Nuestro Ejemplo

Nunca olvides que cuando i=j tenemos que añadir el epsilon.

Ahora si, los K-Caminos:

El pase de diapositivas requiere JavaScript.

La Solución

La expresión regular de un autómata es la union de todos los k-caminos en lo que i sea el estado inicial, j es el estado final.

Así en nuestro caso solo importa RE = (1∗0)(0 + 1)∗

 

 

 

 

 


Pumping Lemma

Este teorema es tan conocido que ni siquiera quise traducirlo, es demasiado famoso, total, veamos para que sirve el que s considerado el teorema mas importante de las expresiones regulares:

El Pumping Lemma sirve para probar que un lenguaje no es regular, NO ES REGULAR, es decir no nos sirve para probar que sea regular, sino mas bien solo para probar que no es regular.

Digamos que nuestro lenguaje L, es un lenguaje regular, entonces todas las cadenas que pertenezcan a L las podremos dividir en 3 SubStrings usando un numero n (que obviamente tiene que ser menor que la longitud del string original):

  • “y” no puede ser un string vacío: y ≠ε
  • La concatenación de los primeros dos tiene que ser menor que n: |xy| ≤ n
  • Para todas las cadenas con k ≥0, la cadena “x·y^k·z” también esta en el lenguaje L.

Esto es, en español que siempre podremos encontrar una y, no tal lejos del origen que puede ser “repetida o pumped” tantas veces como se quiera (incluso 0 con k=0) y que el string resultante esta aún en L.

 

Autómatas: Esos pequeños demonios

ApuntesDe

La teoría de los autómatas es el estudio de las maquinas “abstractas” de la computación, su objetivo es describir como es que una computadora analiza la información (ignorando la molesta parte física y concentrándonos en la lógica).

Los autómatas son como podemos aplicar las máquinas de Turing en la vida real, son un modelo computacional, es decir, no “son código”, son ideas, ideas abstractas que nos permite solucionar problemas.

Características:

  • Es una máquina de estados finitos, es decir, no puede tener una cantidad infinita de estados.
  • Es ahistórico, es decir, no tiene memoria, no puede guardar nada. Siempre se enfoca en el presente.

Funcionamiento

Un autómata recibe un string, un string de un alfabeto conocido, en general el binario o el ASCII y lo va leyendo un carácter a la vez, nuestro autómata esta hecho de “estados”, empezamos en uno (generalmente lo llamamos q0) y dependiendo de que carácter veamos, iremos a otro estado, y así consecutivamente hasta que lleguemos al final de la cadena, cuando llegue este momento, veremos si nuestro estado actual es el final.

Diagramas

Para poder dibujar estos autómatas de manera mas cómoda hemos llegado a un acuerdo sobre cómo podemos dibujarlo.

Todo autómata de estas características, se puede dibujar con las siguientes características:

  • Un círculo que representa un estado
  • Unas flechas que representan a qué estado se tiene que ir dependiendo de qué caracter lee en este momento
Captura de pantalla 2017-02-21 a las 9.07.26 a.m..png

Puedo tener “bucles”

También cada autómata tiene que tener un estado inicial, generalmente a menos que se nos diga otra cosa es el q0:

Captura de pantalla 2017-02-21 a las 9.38.52 a.m..png

El autómata siempre empieza en q0

Y también tiene un estado (o más de un uno) que son estados finales, es decir que nos importará cuando termines la cadena, estos son los círculos que tienen un circulo dentro.

automata.png

El estado inicial también puede ser la final también

Crear Diagramas Online


Ejemplos:

Paridad

Por ejemplo el autómata que ve si la cadena tiene paridad de cero y uno (osea que la cantidad de ceros y la cantidad de unos es par.)

turing

La Función de Transición

Podemos describir de gran manera como es que se comporta un autómata por su función de transición, esta son las flechas, toma como entrada un estado y un carácter o símbolo y regresa un nuevo estado al que hay que dirigirse.

Hablaremos más de esta función al ver lo tipos de Automátas, pero quería que supieras que existe.

Representación

Como vimos, hay dos formas generales de representarlo, ya sea un diagrama o una tabla de estado:

Si nos queremos poner muy formales, vamos a ver como los podemos clasificar:


DFA

Autómatas Finitos Deterministico

Aquí la palabra clave es DETERMINISTICO.

Eso quiere decir, que sin importar si lo corremos una vez o mil, si lo hacemos de día o de noche, siempre saldrá el mismo resultado ,es más eso, quiere decir que el azar no entra en ningún lado, que un estado solo puede tener un camino por símbolo.

Repito: Que un estado SOLO puede salir a otro por cada posibilidad. Es decir, que por ejemplo para el estado q3 solo puede haber una flecha que te indique a donde ir si vez un 1.

Partes:

captura-de-pantalla-2017-03-02-a-las-5-32-02-p-m

  • Un conjunto finito de estados (Q)
  • Un conjunto finito de entrada (Σ)
  • Una Función de Transición  (Delta, no se como escribir eso es ASCII)
  • Un estado inicial que pertenezca a Q (qo)
  • Un subconjunto de Q que llamamos estados finales (F)

Además podemos definir el lenguaje de unos de estos autómatas como:

Lenguaje

Podemos definir de forma “formal” al lenguaje de uno de estos Automátas como aquel conjunto de strings que cumple con la siguiente expresión:

captura-de-pantalla-2017-02-27-a-las-5-15-08-p-m

Es decir, en español: Son todos los string que cuando los pasamos por un autómata finito determinado ( o DFA ) que cuando se le pasan por el autómata, terminan en uno de los estados finales.

Por ejemplo usando algunos autómatas muy comunes algunos Lenguajes Regulares son:

  • Todos los string binarios que acaban en 01.
  • Todos los strings binarios que tengan una cantidad par de ceros y unos.

Delta Gorro

Para poder “analizar” string, usamos una función extra, una que solemos llamar “delta gorro”, esta es:

captura-de-pantalla-2017-03-02-a-las-5-16-45-p-m

Función

Para analizar este automata:


NFA

Autómatas Finitos NO-Deterministico

Aquí la palabra clave es NO DETERMINISTICO.

Son casi iguales que los anteriores, pero hay algo que los hace diferentes y esa única diferencia es la clave, pueden estar varios lugares a la vez.

 Esto es porque tiene varios caminos para una misma entrada.

¿Qué?

Pues que basicamente a mi forma de verlo es como la física y la cuántica, cuando nuestro autómata se enfrenta a la decisión, cuando tiene delante dos camino igual de validos, lo que nosotros hacemos es crear dos “universos” uno donde se va por ejemplo por la derecha y otro donde se va a la izquierda, un universo donde va a a q0 y otro donde va a q3 por ejemplo, veamos un diagrama de estas cositas.

¿Qué hace este autómata cuando ve un 0 y esta en q0?

diagrams2

diagrams1

Partes:

captura-de-pantalla-2017-03-02-a-las-5-32-02-p-m

  • Un conjunto finito de estados (Q)
  • Un conjunto finito de entrada (Σ)
  • Una Función de Transición  (Delta, no se como escribir eso es ASCII)
  • Un estado inicial que pertenezca a Q (qo)
  • Un subconjunto de Q que llamamos estados finales (F)
captura-de-pantalla-2017-03-02-a-las-5-33-15-p-m

y tiene su tableta también

Delta Gorro

Es en Delta Gorro donde encontramos las mayores diferencias, pues NO regresa un estado, sino un conjunto, un conjunto de todos los posibles estados, un conjunto de todos los posibles “universos”.

captura-de-pantalla-2017-03-02-a-las-5-33-20-p-m

Lenguaje

Podemos definir de forma “formal” a un lenguaje de un NDA:

captura-de-pantalla-2017-03-02-a-las-5-35-44-p-m

Es decir, en español: Son todos los string que cuando los pasamos por un autómata finito NO determinado ( o NFA ) que cuando se le pasan por el autómata, me regresan un conjunto donde AL MENOS uno de sus miembro pertenece a uno de los estados finales.

(O aun más formal: Que entre nuestro conjunto de estados que sale de evaluar w, al hacerle la intersección con el conjunto de los estados finales encontramos que no es nula, es decir, existen estados que estan en nuestro conjunto y que al mismo tiempo son estados finales).


De NFA a DFA

Supongamos el siguiente autómata que se encarga de aceptar cualquier cadena que acabe en 0,1.

Captura de pantalla 2017-03-06 a las 1.54.09 p.m..png

Para pasarlo a un Autómata determinada, primero tenemos que hacer una tabla, donde estén: Cada Elemento del Conjunto Potencia, es decir: cada posible subconjunto de todo los estados del autómata, como la siguiente:

Captura de pantalla 2017-03-06 a las 1.54.41 p.m.

Conjunto Potencia

Una vez, listo, podemos hacer una tabla de que pasa a cada subconjunto si ve cada elemento:

Recuerda que la flecha señala al estado inicial y los asteriscos a los estados finales:

(También podemos pasarlo a letras si te es mas cómodo para no escribir tanto)

Ahora lo que hacemos es iniciar por el estado inicial y ver a cuales subconjuntos nos podemos mover hasta llegar al final o a un ciclo.

Gracias a esto podemos dibujarlo:

Captura de pantalla 2017-03-06 a las 1.55.05 p.m.

Diagrama de un Deterministico

¡Y listo!

Ejemplo 2:

El pase de diapositivas requiere JavaScript.

 

Veamos una de mis tareas a ver si deja las cosas más claras:

Documento de NFA

 

 


ε-NFA

Transiciones Epsilon

Añadiremos una nueva característica a nuestro autómata, la que nos permita que lea “nada” literalmente que nos permita no leer nada. Una cadena vacía. Epsilon.

Es más puedes imaginar que nuestra cadena tiene una cantidad necesaria de epsilon dentro de la misma cadena.

Veamos la utilidad en todo esto:

Podemos desarrollar un autómata que se encarga de aceptar decimales, estos consisten en :

  •  Un “+” o “” opcional
  • Una cadena de decimales
  • Un punto decimal
  • Una cadena (otra) de decimales

Es totalmente  posible que una de las dos cadenas este vacía, pero obvio no las dos.

Por ejemplo:

  • “1.0”
  • “32.”
  • “-.2323”

Captura de pantalla 2017-03-15 a las 8.05.37 p.m.

Cerradura Epsilon

Como siempre, hay que hacer nuestra tabla, pero también hay que contar a epsilon:

 Captura de pantalla 2017-03-16 a las 9.03.51 a.m.

En la columna de epsilon va lo que se conoce como la cerradura de epsilon, es decir, es la que nos dice a donde podemos ir solo moviéndonos entre caracteres varios.

Es decir:

Captura de pantalla 2017-03-16 a las 9.12.01 a.m.

Para poder quitarle los epsilon, tenemos que empezar en q0, mas bien tenemos que empezar en la cerradura de epsilon de cada elemento:

Captura de pantalla 2017-03-16 a las 9.20.25 a.m..png

Veamos una de mis tareas a ver si deja las cosas más claras:

Documento de e-NFA

Introducción a las Máquinas de Turing

fuentes

¿Qué es un algoritmo?

A principios del siglo XX los matemáticos estaban fascinados por la pregunta: ¿Cuántas matemáticas podemos hacer? … no usando nuestros sentimientos o intuiciones, sino sólo reglas muy muy cuidadosamente, osea usando un algoritmo.

A final de toda esta cuestión y para que nuestra respuesta tenga algo de sentido tenemos que pensar, ¿Qué entendemos por un programa o algoritmo?

algoritmo


Alan Turing

turing.pngY aquí es donde Alan Turing entra en escena con su noción de una máquina de Turing.

Alan Turing es el hombre que debemos agradecer por un mundo libre de Nazis y lleno de computadoras.

En 1936, Alan Turing publicó un artículo titulado “Computables Numbers, with a Application to the Entscheidungs problem”, en el que presentaba la noción de una máquina universal (más tarde llamada “máquina universal de Turing” y luego “máquina de Turing”) capaz de computar cualquier cosa que sea computable. El concepto central de la computadora moderna se basó en el papel de Turing.

mat31.jpg

Propuesta de una máquina de Turing

Deja que te lo explique de otra manera, el en su cabeza pensó en una maquina que pudiera calcular todo aquello que fuera calculable… sin crearla…Antes siquiera de que existiera la primera computadora moderna.


Máquinas de Turing

Como podemos leer, Alan es uno de los grandes padres de la computación, y realizo muchísimo trabajos en grandes áreas, así que por ahora nos centraremos en uno de ellos. Su documento “Computables Numbers, with a Application to the Entscheidungs problem”

Como parte de su prueba tenía que trabajar con la noción de cualquier algoritmo posible o cualquier máquina posible. Él tenía que llegar a una forma muy general de como los algoritmos o programas o máquinas trabajan.

Aquí es donde su noción de la máquina de Turing entra. La forma en que Turing describió a estas máquinas es algo como esto:

mat32

Tienes una manera de escribir información en forma codificada: Su manera era pensar en una cinta que sea lo largo que sea necesario, esta se divide en cuadrados y cada uno de los cuadrados hay un cero o uno  o podemos tener algunos espacios.

Ahora lo que hace nuestra máquina es que mira la cinta un cuadrado a la vez.

Así que se podría imaginado como una pequeña caja corriendo por encima de la cinta, quizás en las ruedas pequeñas, mirando.

turing32.png

Ejemplo de Máquina de Turing

a

Ejemplo B de la representación de la máquina

Esta cuenta codifica nuestro problema solucionado (una vez que la máquina de Turing haya terminado) lo que una máquina de Turing hace es realmente sencillo:

Operación

En cualquier momento en el tiempo está en un estado particular y está mirando un cuadrado en la cinta, y tiene un libro de registro, un libro de programas. Y eso lo dice que hacer.

Forma A:

turing31.png

Computerphile

Si por ejemplo estás en el número de estado 23, Y está mirando un cero, entonces borrar el cero, lo cambia a uno, muévete un cuadrado a la derecha, y pasar al estado número 359.

O si estás en la número 359 y usted está mirando una deje ese uno como es, mueva un cuadrado a la izquierda y pasar al estado número veinte.

Son puras instrucciones sencillas.

Forma B de Entenderlo:

captura-de-pantalla-2017-01-31-a-las-8-57-48-p-m

Máquina y su “programa”

Este programa basicamente de dice a la máquina que operación hacer, toda máquina Turing debería tener un inicio, ese esta denotado por:

a

Estado inicial

Y las operaciones o “instrucciones” más bien tienen esta sintaxis:

a

Destino e instrucción

Básicamente dice:

Digito1 / Digito 2, Dirección

Ya sabemos que los Dígitos puedes ser: {1,0} y las direcciones: {L(izquierda) , R(derecha) y .(Quédate ahí)}

Así en lenguaje natural la instrucción se lee:

“Si Digito1 es tu dígito actual, continua leyendo, sino para, si continuas leyendo cambia tu estado actual por Digito2 y avanza en Dirección, finalmente estas en el estado q1.”

Si sigues esta idea puedes ver como la máquina va avanzando siguiendo el diagrama:

a

Diagrama

captura-de-pantalla-2017-01-31-a-las-9-09-13-p-m

Primer paso

captura-de-pantalla-2017-01-31-a-las-9-08-56-p-m

Segundo paso

b

Tercer Paso

c

Cuarto Paso

d

Paso Final

Esa qh significa Halt, que en español quiere decir “parado” es el paso en el que se dice que se terminaron de ejecutar todas las instrucciones y nuestra máquina a terminado su trabajo y se quedará ahí.

Lo que la máquina hace, es que comienza con un cierto patrón de unos y ceros. Esa sigue estas reglas un cuadrado a la vez, transformando esa cadena de unos y ceros en una cadena diferente de unos y ceros.

Y eventualmente ( y con suerte) la máquina se mueve en un estado de parada.

Está terminado, está hecho. Y lo que queda en la cinta es la respuesta a nuestro problema, codificados como unos y ceros. Eso es un simple proceso, pero resulta que es el esencia de la computación.

Lo que sea cualquier computadora puede hacer, podría en teoría ser hecho por ese sistema mirando a los unos y ceros en una cinta.

Así que por eso decimos que Turing al llegar con su idea de máquinas de Turing, en efecto, surgió un plan para los modernos ordenadores digitales.

Básicamente hacen lo que hacen las máquinas de Turing.

Y usamos esta idea para evaluar la fuerza de los modernos programas de computador. Cuando un programa de computadora puede hacer lo que una máquina de Turing puede hacer, lo llamamos “Turing completa”. Y es la cima de la jerarquía de la fuerza del programa.

0478510_please-wait-turing-complete-womens-tshirt

Así que el programa más fuerte que podemos obtener hace exactamente uno que haga lo que una máquina de Turing puede hacer. Nunca hemos encontrado una forma de calcular más cosas que las que podríamos hacer con una máquina de Turing.


Máquina Universal de Turing

De forma más abstracta podemos decir que una máquina de Turing es como una caja negra, de este estilo:

a2

Máquina Típica de Turing, casual

Así que para evitar tener que desarrollar una nueva máquina para cada operación (lo cual resultaría incontable) se desarrolló la “Máquina Universal de Turing”

Que tenía una entrada P que le diría como tenía que comportarse y esta máquina para el mundo exterior serviría exactamente igual que una máquina de Turing normal, si de esas que te encuentras todos los días.

a1


El Problema de la Parada “The Halting Problem”

Hay también un problema muy famoso relacionado con el bueno de Turing y de como en la solución de ese problema, Alan Turing casi inadvertidamente inventó la computadora digital moderna.

Así que empezamos de nuevo al principio del Siglo XX, donde los matemáticos tenían planteado este problema:

En lógica estamos interesado en encontrar  la respuesta a la pregunta: “¿Estas premisas implican esta conclusión? 

Las premisas son los bits con los que comienzas, son los pedacitos que sabemos en el principio (osea los supuestos) y la conclusión es el a lo que quieres llegar.

Hay una prueba llamada Halting que nos diría si las premisas conducen a las conclusiones por medio de la lógica. Es decir ¿Hay una manera automática de averiguar si lo hacen o si no lo hacen? , así que ese es el problema, se llama el también el Problema de Decisión.

alan

Turing es feliz

Los matemáticos querían saber hay una respuesta al problema de la decisión para la lógica de primer orden (Ese es el tipo de lógica que aprendes en Filosofía o matemáticas en la universidad).

Alan Turing fue uno de los primeros en descubrir que la lógica de primer orden no es decidiste, es decir puede probar automáticamente si las premisas llevan a la conclusión.

Para probar esto es realmente difícil (conceptualmente) porque tenemos que ser capaz de demostrar no hay ningún programa posible que pueda darnos la respuesta.
Pero, ¿cómo lo haces hacemos ¿Cómo se muestra algo de todos los programas posibles que puedan existir?

Turing surgió con una brillante solución, su idea es algo así:

box

ComputerPhile

Supongamos que tenemos un programa y vamos a dibujar como una caja negra, (una de las maquinas de Turing)

Esta máquina va a tomar unas premisas y conclusiones y te dice que las premisas llevan a la conclusión de manera automática, es decir resulte el problema de Halting.

Ahora aquí hay otra pregunta que podemos hacer, que es equivalente:

¿Alguna vez el programa terminará?

Veamos todos los posibles programas que existen y sólo pensemos en ellos como cajas negras y por el momento lo único que nos interesa saber es si algún día pararan de “correr”.

No nos importa que respuesta nos den estos programas, simplemente saber si nos darán una respuesta.

Si no terminara nunca de “ejecutarse” el programa significa que quedo atrapado en un bucle infinito. Nunca sabríamos si va a termina hoy, mañana o nunca.

Lo asombroso resulta en que nuestro problema lógico: ¿Estas premisas implican esta conclusión? es muy similar a este Problema de Detención.

La parte inteligente de la prueba de Turing es que para mostrar que es imposible que existe una máquina, no importa lo compleja que sea que resuelva el problema de la Parada… Pero ¿Cómo lo hizo?


La solución de Turing

Supongamos que tenemos una máquina o un programa que soluciona el problema, no nos preocupemos de como lo hace, simplemente lo hace.

final

La vamos a llamar Máquina H

Esta máquina recibe dos entradas, un programa y un “entrada de programa” y nos regresa un “si” si en algún momento el programa P se detendrá dado la entrada I, y un “no” si… si no (obvio).

b.png

Máquina H+

Usando H como base podemos crear esta nueva máquina en la que si el resultado es verdadero entonces haremos que se quede en un bucle para siempre y si la respuesta es no, entonces regresamos un “si parará”.

La magia ocurre cuando alimentas a H+ con H+

h.png

Así que la pregunta que ahora estoy haciendo es que estoy haciendo es preguntarle a la máquina:  ¿H + se parará con la entrada H+?

Y aquí es donde todo va mal porque si H+ detiene recibimos una respuesta afirmativa, pero entonces inmediatamente entra en un bucle infinito, y por consiguiente no se detiene.

Por otro lado si recibimos un “no se detiene” de H entonces la máquina nos devuelve un “Si se detiene” y se detiene.

No es que hayas entendido mal, es que es una paradoja, no tiene sentido, pero lo que muestra es que empezamos suponiendo que podemos resolver el problema y hemos terminado con una paradoja, por lo tanto la suposición era mala.

alan

Ahora entiendes este meme

Resulta que no hay máquina posible, ningún programa posible que resuelva el Problema de la Parada.

btn1 btn
btn

¿Qué son los Lenguajes de Programación? (Vista Formal)

Para empezar con esto, veremos antes ¿Qué es un lenguaje desde un punto de vista completamente matemático?

Para definir un lenguaje  (que es la parte fundamental de la teoría de autómatas) tenemos que definir algo más elemental, un alfabeto:

Un Alfabeto

sum

Un alfabeto es finito (y que obviamente no esta vacío, sino no tiene sentido) de forma común usamos el símbolo de suma.

Algunos alfabetos comunes son:

  • El Alfabeto Binario
  • El Alfabeto ASCII

sum2

Strings – Cadenas

Un string o una palabra es una secuencia finita de símbolos de un alfabeto. Por ejemplo, 01101 es una cadena del alfabeto binario. La cadena 111 es otra cadena de este alfabeto.

Cadena Vacía: Hay una cadena muy especial y que siempre tiene que existir, y es un string sin ningún símbolo.

captura-de-pantalla-2017-02-02-a-las-9-00-15-p-m

Longitud de un String

A menudo es útil clasificar cadenas por su longitud, es decir, el número de símbolos en la cadena. Por ejemplo, 01101 tiene longitud 5.  La notación estándar para la longitud de una cadena:

in

Potencias de un Alfabeto

Si tenemos un alfabeto cualquiera, podemos expresar el conjunto de todas las cadenas de una cierta longitud usando la notación de potencia.

Así elevar un alfabeto a una potencia K es lo mismo que preguntar por todos los posibles strings con longitud K.

a3

De aquí podemos sacar la gran pregunta, ¿Cuál es la diferencia entre el la segunda y la tercera línea? El primero es un alfabeto; sus miembros 0 y 1 son símbolos. El segundo es un conjunto de strings cual longitud son uno.

Así para denotar el conjunto de todos los posible strings usamos:

a2

A veces es útil excluir a la cadena vacía, por lo que tenemos la siguiente notación y propiedades:

a1

Lenguajes

Un conjunto de cadenas de todo el universo posible es lo que llamamos un lenguaje. Es decir:

b

No es necesario incluir todas las cadenas posibles, solo un conjunto de ese conjunto enorme que tenemos para elegir.

La elección del término “lenguaje” puede parecer extraña. Sin embargo, los idiomas se pueden ver como conjuntos de cadenas. Un ejemplo es el inglés, donde la colección de palabras es un conjunto de cadenas sobre el alfabeto que consiste de todas las letras. Otro ejemplo es C, o cualquier otro lenguaje de programación.

Aquí otros ejemplos:

  • El lenguaje binario donde todos los strings tienen las mismas cantidades de unos y ceros.
  • El lenguaje binario donde todos los strings son K unos seguidos de K ceros.

La única restricción importante en lo que puede ser un lenguaje es que todos los alfabetos son finitos. Así aunque un lenguaje puede tener un número infinito de cadenas, solo puede sacarlos de un numero finito de símbolos.

 

 

Lenguajes: Historia, Códigos Fuente y Compiladores

 

fuentes

Definiciones

  • Un ordenador/Computador: Es una máquina que procesa datos
  • Una instrucción: Es la tarea más simple que puede ejecutar un computador, como por ejemplo sumar dos números o mover un registro.
  • Programa: Un conjunto de instrucciones e hacen algo cuando se ejecuta o se corre el programa.

Objetivo de un Programa: Obtener datos, procesarlos y dar un resultado.

Compiladores.png

Esto es algo muy común en computación, es conocido (al menos por mi) como la idea de la caja negra:

Caja Negra

Una caja negra es una idea muy útil, por ejemplo para entender como funciona el internet tal vez alguien te lo explique usando HTML y PHP , pero ..¿Cómo funciona un hipervínculo?  ¿Cómo es que se conecta una computadora a otra sin cables? De eso no tenemos ni puta idea.

Y no te sientas mal por no saber algo, este mundo es complejo y es muy difícil entenderlo todo, por eso usamos la idea de la caja negra, por ejemplo en software hay funciones, por ejemplo printf que para casi todos es una caja negra.

¿Cómo funciona printf ? Nunca lo sabremos o no nos importa.

Compiladores-2.png

Le decimos que lo haga y lo hace. Eso es común en computación, la idea de que ciertas cosas son obvias, como los axiomas en mate.


Códigos y Compiladores

Un código es la forma en la que tenemos para que la computadora haga lo que queremos.

Código Maquina

apple_ii_monitor

  • Utiliza unos y ceros
  • Los procesadores ejecutan instrucciones en binario

Pero claro, el problema es que alguien le tiene que decir a los ordenadores que hacer, y ese alguien son seres humanos y digamos que no son muy buenos en crear códigos o leerlos si solo son un montón de números.

…Ahora imagínate para encontrar un bug : o


Código Fuente

El código fuente es una forma de traducir las ordenes que e damos una computadora a un lenguaje mas entendible para los humanos. De modo que en vez de trabar en el leguaje hecho para la máquina trabajábamos en un hecho para personas.

A lo largo del tiempo se han hecho distintos códigos para trabajar con ordenadores:

Ensamblador

suma.png

El problema con ensamblador es que cualquier operación compleja como sumar o multiplicar requería de muchas instrucciones que también acaban convirtiéndose en repetitivas.

Lenguajes de Alto Nivel

nivel.png

Se trabaja de una manera mucho mas cómoda como puedes ver, entonces para resumir:

Lenguajes de Alto Nivel

  • Intenta ser lo más independiente del procesador posible.
  • Yo digo como quiero que sea mi programa, como lo ejecute el procesador es otra historia.
  • Cualquier maquina puede ejecutar el código.

Lenguajes de Bajo Nivel

  • Trabaja cerca del procesador y permite sacarle todo el provecho al hardware.
  • Puede dar problemas cuando intento cambiar a otra máquina a ejecutarlo.

¿Cómo hace la maquina para entender el lenguaje de alto nivel?

Pues justo eso lo hace a través de un compilador, esa es la clave. Compilador.

Es decir esos códigos fuentes los transforma en un código maquina que la computadora puede entender.

codigo.png

La gran ventaja que nos dan los compiladores ademas que permiten la potabilidad, pues saben las instrucciones indicadas para cada máquina.

Captura de pantalla 2017-01-29 a las 8.26.19 p.m..png


Historia de los Lenguajes

Así como el Hardware (las cosas que puedes golpear) el software también a cambiado a lo largo de los años, a evolucionado. Y mucho.

Antes de 1940

Los primeros lenguajes de programación preceden a la computadora moderna. En un inicio los lenguajes eran códigos.

La máquina del telar de Jacquard, creada en 1801, utilizaba los orificios en tarjetas perforadas para representar los movimientos de un brazo de la máquina de tejer, con el objetivo de generar patrones decorativos automáticamente.

En 1843 Ada Lovelace tradujo las memorias del matemático italiano Luigi Menabrea acerca de la nueva máquina propuesta por Charles Babbage, la Máquina Analítica.

ada.jpg

¡Eso es programar con estilo!

Con estos escritos, ella añadió unas notas en las cuales especificaba en detalle un método para calcular los números de Bernoulli con esta máquina, el cual es reconocido por muchos historiadores como el primer programa de computadora del mundo.

Para algunas personas, lo que sería el primer lenguaje de programación moderno depende de cuánto poder y legibilidad humana se requería antes de que se concediera el estado de “lenguaje de programación”.

Tanto el telar de Jacquard como la Máquina Diferencial de Babbage, tenían lenguajes muy simples y extremadamente limitados para describir las acciones que estas máquinas realizaran.


Las décadas de 1950 y 1960

En los cincuenta, los tres primeros lenguajes de programación modernos, cuyos descendientes aún continúan siendo utilizados, son:

  • FORTRAN (1955): Basado en algo procedimiento de las matemáticas
  • LISP (1958)
  • COBOL (1959): Basado en el uso de finanzas

cobol1

Ensamblador

Se genera como un lenguaje de tipo bajo que usa palabras por ejemplo: Add – 011101110

Y mediante un programa llamado ensamblador se traducía estas palabras a los códigos correspondientes. A partir de aquí surgen dos grandes caminos:

CISC

  • Gran cantidad de instrucciones
  • Son los más usados actualmente y son los procesadores de escritorio

RISC

  • Usados con pocas instrucciones
  • Gran eficiencia de energía
  • Tiene la subfamilia ARM usado en dispositivos móviles

Década de 1890

La década de 1980 fueron años de consolidación relativa en los lenguajes imperativos. En vez de inventar nuevos paradigmas, se comenzó a trabajar a partir de las ideas inventadas en la década anterior. C++ combinaba la programación orientada a objetos y la programación de sistemas.

c.png


La Década de 1990

El rápido crecimiento de Internet en la década de 1990 fue el siguiente gran acontecimiento histórico para los lenguajes de programación. Con la apertura de una plataforma totalmente nueva para los sistemas informáticos, Internet creó una oportunidad adoptar nuevos lenguajes.

java.png

En particular, el lenguaje de programación Java se hizo popular debido a su pronta integración con el navegador web Netscape Navigator, y varios lenguajes de scripting alcanzaron un amplio uso en el desarrollo de aplicaciones personalizadas para servidores web.

 

 

btn1 btn
btn

 

Teoría Computacional: Introducción

Las computadoras calculan. Eso parece bastante intuitivo. ¿Pero la informática es exclusiva de las computadoras? Cuando una computadora está haciendo su trabajo para abrir una aplicación, realizar operaciones aritméticas ¿qué está haciendo exactamente? 


¡Hora de Definiciones!

¿Qué es computación?

CS, Computer Science, informática o computación es el estudio de las computadoras y los sistemas computacionales. (si, no pienso poner una definición más escrita, creo que todos entendemos eso)

legacy-codeLos informáticos diseñan y analizan algoritmos para resolver programas y estudiar el rendimiento del hardware y software de la computadora. Los problemas que encontramos van desde lo abstracto, determinando qué problemas pueden resolverse con los ordenadores y la complejidad de los algoritmos que los resuelven, hasta las aplicaciones de diseño tangible que funcionan bien en dispositivos de mano, fáciles de usar y que defienden las medidas de seguridad.

Principio de la Computación: La informática se basa fundamentalmente en los procesos de información. Una de las grandes ideas de la informática es que los procesos de información pueden realizarse puramente mecánicamente mediante la manipulación de símbolos.

El agente que hace la computación, ya sea un ser humano pensante o una máquina (computadora), no importa. 

¿Qué estudia la Teoría Computacional?

La Teoría computacional es matemática y abstracta en espíritu, pero deriva su motivación de la computación práctica y cotidiana.

mat32

Su objetivo es comprender la naturaleza de la computación y, como consecuencia de este entendimiento, proporcionar metodologías más eficientes. Todos los trabajos que introduzcan o estudien conceptos y métodos matemáticos, lógicos y formales son bienvenidos, siempre y cuando su motivación se desprenda claramente del campo de la informática.

Teoría de la Computación
peter_j-_denningSegún Peter Denning, la pregunta fundamental que subyace a la informática es “¿Qué puede automatizarse (eficientemente) “.

La teoría de la computación se centra en responder a preguntas fundamentales sobre lo que se puede calcular y la cantidad de recursos necesarios para realizar esas Computaciones.

En un esfuerzo por responder a la primera pregunta, la teoría de la computabilidad examina qué problemas computacionales son solubles en varios modelos teóricos de computación.

La segunda pregunta es abordada por la teoría de la complejidad computacional, que estudia los costos de tiempo, recursos y espacio asociados con diferentes enfoques para resolver una multitud de problemas computacionales.


Preguntas más importantes en esta materia:

¿De que partes esta echa nuestra computadora de estudio?

Suele considerarse que una computadora digital consta de tres partes:

  • Almacenamiento
  • Unidad procesadora
  • Control

Almacenamiento

El almacenamiento es el acopio de información y corresponde al papel sobre el que se efectúa la computación humana, ya sea el papel en que la persona realiza los cálculos o aquél en el cual está impreso el libro de reglas. Del mismo modo que el computador humano efectúa sus cálculos con su cabeza, parte del almacenamiento corresponde a la memoria de la máquina.

Unidad Procesadora

La unidad procesadora es el sector que realiza las distintas operaciones de cálculo. La naturaleza de estas operaciones varía de una máquina a otra. Generalmente pueden efectuar operaciones bastante largas, tales como “Multiplicar 3540675445 por 7076345687”, pero en algunas máquinas sólo pueden llevarse a cabo operaciones muy simples, tales como “Escribe 0”.

Control: Donde pasa lo interesante

Hemos mencionado que el “libro de reglas”, de que se vale el computador, se sustituye en la máquina por una parte del almacenamiento. Esta se denomina “tabla de instrucciones”. Corresponde al control comprobar que las instrucciones se sigan correctamente y en su debido orden.

El control está construido de tal manera que es infalible. La información almacenada suele estar dividida en paquetes de tamaño relativamente modesto. En una máquina concreta, por ejemplo, el paquete puede constar de diez dígitos decimales. Se asignan números a las partes del almacenamiento en que se guardan los diversos paquetes de información, con arreglo a una modalidad sistemática.

Playbook_cover.jpg

Un ejemplo de instrucción corriente podría ser: “Suma la cifra almacenada en la posición 6809 a la situada en la 4302 y devuelve el resultado de la última posición de almacenamiento”.

Ni que decir tiene que la operación no se desarrolla en la máquina expresada de este modo, sino que se lleva a cabo siguiendo una codificación como 6809430217. La cifra 17 indica cuál de las posibles operaciones hay que efectuar con las dos cifras. En cuyo caso la operación es la anteriormente descrita: “Suma la cifra…”.

Se advertirá que la instrucción consta de diez dígitos y, por lo tanto, constituye exactamente un paquete informativo.

El control suele captar las instrucciones a seguir en el orden de posición en que están almacenadas, aunque a veces pueda surgir una instrucción como ésta: “Sigue ahora la instrucción almacenada en la posición 5606 y continúa”, o bien: “Si la posición 4505 contiene 0, sigue la instrucción almacenada en 6707; en caso contrario continúa”.

Las instrucciones de este tipo son muy importantes porque permiten la repetición de una secuencia de operaciones una y otra vez hasta que se cumple un determinado requisito, pero, al hacerlo, la máquina sigue en cada repetición, no nuevas instrucciones, sino las mismas indefinidamente.

El concepto de computadora digital es antiguo. Charles Babbage, profesor de matemáticas en la Universidad de Cambridge entre 1828 y 1839 concibió una a la que denominó Máquina Analítica, pero no la terminó. Aunque Babbage expuso los principios fundamentales, la máquina no representaba en aquella época gran interés. Su rapidez habría sido mucho mayor que la de un computador humano, pero unas 100 veces inferior a la de la máquina de Manchester, que a su vez es una de las máquinas modernas más lentas. El almacenamiento era puramente mecánico y se efectuaba por medio de ruedas y tarjetas.

450_1000

El hecho de que la Máquina Analítica de Babbage estuviera concebida de forma totalmente mecánica nos ayudará a despejar cualquier superstición. Muchas veces se atribuye importancia al hecho de que las computadoras digitales modernas son eléctricas, igual que el sistema nervioso. Como la máquina de Babbage no era eléctrica, y como todas las computadoras digitales son en cierto modo equivalentes a ella, el empleo de la electricidad no es teóricamente relevante.

btn1 btn
btn

Arquitecturas Von-Newman VS Harvard

Arquitectura Von-Newman

La arquitectura Von Neumann o Princeton, es una arquitectura de computadoras creada en 1945.

Tradicionalmente los sistemas con microprocesadores se basan en esta arquitectura, en la cual la unidad central de proceso (CPU), está conectada a una memoria principal única (casi siempre sólo RAM) donde se guardan las instrucciones del programa y los datos. A dicha memoria se accede a través de un sistema de buses único (control, direcciones y datos):

image00

En un sistema con arquitectura Von Neumann el tamaño de la unidad de datos o instrucciones está fijado por el ancho del bus que comunica la memoria con la CPU. Así un microprocesador de 8 bits con un bus de 8 bits, tendrá que manejar datos e instrucciones de una o más unidades de 8 bits (bytes) de longitud.

Si tiene que acceder a una instrucción o dato de más de un byte de longitud, tendrá que realizar más de un acceso a la memoria. El tener un único bus hace que el microprocesador sea más lento en su respuesta, ya que no puede buscar en memoria una nueva instrucción mientras no finalicen las transferencias de datos de la instrucción anterior.

Limitaciones

Las principales limitaciones que nos encontramos con la arquitectura Von Neumann son:

  • La limitación de la longitud de las instrucciones por el bus de datos, que hace que el microprocesador tenga que realizar varios accesos a memoria para buscar instrucciones complejas.
  • La limitación de la velocidad de operación a causa del bus único para datos e instrucciones que no deja acceder simultáneamente a unos y otras, lo cual impide superponer ambos tiempos de acceso.

 

Cuello de Botella de Von Neumann

El canal de transmisión de los datos compartido entre CPU y memoria genera un cuello de botella de Von Neumann, un rendimiento limitado (tasa de transferencia de datos) entre la CPU y la memoria en comparación con la cantidad de memoria.


Arquitectura Harvard

Este modelo, que utilizan los micro controladores PIC, tiene la unidad central de proceso (CPU) conectada a dos memorias (una con las instrucciones y otra con los datos) por medio de dos buses diferentes.

image01

Una de las memorias contiene solamente las instrucciones del programa (Memoria de Programa), y la otra sólo almacena datos (Memoria de Datos). Ambos buses son totalmente independientes lo que permite que la CPU pueda acceder de forma independiente y simultánea a la memoria de datos y a la de instrucciones. Como los buses son independientes éstos pueden tener distintos contenidos en la misma dirección y también distinta longitud.

También la longitud de los datos y las instrucciones puede ser distinta, lo que optimiza el uso de la memoria en general. Para un procesador de Set de Instrucciones Reducido, o RISC (Reduced Instruction Set Computer), el set de instrucciones y el bus de memoria de programa pueden diseñarse de tal manera que todas las instrucciones tengan una sola posición de memoria de programa de longitud.

Además, al ser los buses independientes, la CPU puede acceder a los datos para completar la ejecución de una instrucción, y al mismo tiempo leer la siguiente instrucción a ejecutar.

Ventajas de esta arquitectura

  • El tamaño de las instrucciones no está relacionado con el de los datos, y por lo tanto puede ser optimizado para que cualquier instrucción ocupe una sola posición de memoria de programa, logrando así mayor velocidad y menor longitud de programa.
  • El tiempo de acceso a las instrucciones puede superponerse con el de los datos, logrando una mayor velocidad en cada operación.

 


VS

La Arquitectura Von Neumann

  1. Los datos y las instrucciones(secuencia de control), Se almacenan en una misma memoria de lectura/escritura.
  2. No se pueden diferenciar entre datos e instrucciones al examinar una posición de memoria (Location).
  3. Los contenidos de la memoria son direccionados por su ubicación(location), sin importar el tipo de datos contenido all.
  4. La ejecución ocurre en modo secuencial mediante la lectura de instrucciones consecutivas desde la memoria.

 

La Arquitectura Harvard

  1. Las instrucciones y los datos se almacenan en caches separadas para mejorar el rendimiento.
  2. Por otro lado, tiene el inconveniente de tener que dividir la cantidad de cach entre los dos, por lo que funciona mejor sólo cuando la frecuencia de lectura de instrucciones y de datos es aproximadamente la misma.
  3. Esta arquitectura suele utilizarse en DSPs, o procesador de señal digital, usados habitualmente en productos para procesamiento de audio y video.

 

 

btn1 btn
btn

 

Historia de las Computadoras (y generaciones)

FuentesLibros.png

FuentesLibros-2.png

¡Hola!

He decido empezar este curso de varias maneras, así que es normal que haya cosas que no entiendas mientras lees estas líneas por primera vez, así que no te preocupes, el objetivo de esta lección es sencilla. Es mostrarte como fuimos del punto A al Punto B:

 

¿Cómo empezó todo esto?

Antes incluso que la primera foto tuvo que pasar muchas, muchas cosas. Los padres de las computadoras son las calculadoras, pero para entender como llegamos a una computadora hay que entender primero la historia de sus padres, las calculadoras.

Calculadora de Antikythera: ¿Viajes en el Tiempo?

La primera calculadora conocida sigue siendo un auténtico misterio. En 1900, submarinistas cazadores de esponjas en Grecia descubrieron cerca de la diminuta isla de Antikythera restos de un antiguo naufragio del primer siglo antes de Cristo.

nama_machine_danticythere_1Entre las estatuas y vasijas rotas se encontraron algunas piezas de bronce corroído, que parecían ser parte de una máquina.

Cincuenta años tardaron los estudiosos en descubrir cómo encajaban estas piezas y lograr que el aparato funcionara.

El resultado fue una especie de calculadora astronómica, que funcionaba igual que un ordenador analógico moderno, con piezas mecánicas para hacer los cálculos. Al girar una manivela se accionaban unas palancas; estas, a su vez, accionaban unos cuadrantes con los que se podía leer la posición del Sol y los planetas del zodiaco.

Ningún filósofo, poeta, matemático, científico o astrónomo hace referencia a un objeto así. Además, según los conocimientos actuales sobre la ciencia de la antigua Grecia, no había tradición ni conocimiento capaz de producir tal máquina.


“Historia Moderna”: Calculadora de Schickard

Después, durante más de mil quinientos años, nada. En general, se considera la primera calculadora “real” la que fabricó en 1623 William Schickard. Schickard era amigo del astrónomo Johannes Kepler, que descubrió las leyes de los movimientos planetarios.

replicarelojcalculador

Kepler despertó el interés latente por las matemáticas del catedrático de hebreo, cuya habilidad para realizar cálculos se había apolillado un poco con el paso

de los años. Así que decidió fabricar una máquina que lo ayudara con sus sumas. La máquina de Schickard se ha descrito como un “reloj de cálculo”. Se pretendía que sirviera de ayuda a los astrónomos, al permitirles calcular las efemérides (las futuras posiciones del Sol, la Luna y los planetas).


Calculadora de Pascal: Ese tipo estaba en todo

Pero volvamos al ordenador digital. El siguiente avance en este campo vino de la mano del matemático francés del siglo XVII, Blaise Pascal, que casualmente nació en 1623, el mismo año en que Schickard había inventado el “reloj de cálculo” original.


Calculadora de Leibniz: Lo que nunca fue

El siguiente avance significativo para el ordenador digital lo logró el filósofo alemán Gottfried Leibniz, el Leonardo da Vinci de su época.

Entre otras muchas cosas, Leibniz creó nada menos que dos filosofías (una optimista y otra pesimista), un plan detallado para la invasión de Egipto, una historia en 15 volúmenes de la Casa de Hannover y una calculadora muy superior a la de Pascal. El interés de Leibniz por las calculadoras no era únicamente práctico.

leibniz

Una madrezota

En cuanto Leibniz hubo terminado su máquina, cruzó el Canal de la Mancha para mostrarla a la Royal Society de Londres. Sus miembros no parecieron impresionados, y abandonó el proyecto cuando aún no tenía más que un prototipo. A pesar de estas limitaciones, la máquina de Leibniz era extraordinaria. Al igual que la de Pascal, se accionaba mediante una sucesión de ruedas dentadas, pero era capaz de hacer muchas más cosas que la de Pascal. Desde el primer momento podía multiplicar (mediante sumas repetidas), pero además Leibniz pronto añadió unos dispositivos que permitían efectuar divisiones y calcular también raíces cuadradas.

Calculadoras: La solución a Todo
Para él, algún día, las calculadoras resolverían todas las disputas éticas. Bastaría con insertar los diferentes argumentos y la máquina “calcularía” cuál era superior (aunque las bases precisas para semejante cálculo quedaron en la misma categoría que el cálculo de las posibilidades de la inexistencia de Dios: es decir, siguen siendo un misterio para todos, salvo para el genio que las concibió).

Del mismo modo, Leibniz predijo también que las calculadoras quitarían trabajo a los jueces: los tribunales del futuro estarían presididos por calculadoras que emitirían tanto el fallo como la sentencia adecuada.


Máquina de Babbage: ¡Papá esta en casa bitches!

En general, se reconoce a Charles Babbage como el padre de las computadoras. Al igual que muchos genios prácticos, era increíblemente poco práctico en cualquier sentido de la palabra, pero sus descubrimientos y logros estaban un siglo por delante de su tiempo.

Babbage decidió que había una única solución para el problema de las tablas astronómicas erróneas. Había que construir una calculadora grande, infalible y multiusos.
450_1000
Este proyecto era enormemente ambicioso: la máquina de Babbage tenía que ser capaz de calcular cifras de hasta 20 dígitos; también tenía que almacenar una serie de números y efectuar sumas con estos. Los cálculos de la máquina podían reducirse a sumas porque utilizaría el método de las múltiples diferencias

Como sus antecesores, la “máquina diferencial n o 1” utilizaba ruedas dentadas y funcionaba con el sistema decimal, pero su fabricación superaba con mucho la complejidad de las máquinas anteriores, lo que hizo necesarios diversos avances dentro de la ingeniería mecánica.

Después de diez años de trabajo, Babbage había convertido su proyecto original en una máquina de 25 000 piezas (y solo se habían fabricado 12 000), y el coste se elevaba a 17 470 libras (en aquellos días, esa suma era suficiente para fabricar un par de buques de guerra). Babbage había puesto grandes sumas de su propio bolsillo, pero el Gobierno decidió frenar el proyecto.

Era mejor invertir en una flota que en una máquina que podría acabar contribuyendo a la deuda nacional en una cifra que solo esa misma máquina podría calcular.

La “máquina diferencial n o 2” se convirtió en la primera máquina analítica: una máquina cuyo funcionamiento estaba controlado por un programa externo.

220px-jacquard-loom-cardsBabbage había oído hablar de la idea de Jacquard sobre las tarjetas perforadas para controlar el mecanismo de una máquina y decidió incorporarla a su propia máquina. Esto le permitiría realizar cualquier cálculo aritmético en función de unas instrucciones insertadas en tarjetas perforadas.

Al igual que la primera máquina diferencial, también necesitaba una memoria para almacenar números, pero la nueva máquina debería poder realizar una secuencia de operaciones con esos números almacenados. Babbage había dado con las características esenciales del ordenador moderno.

Babbage había definido las características básicas del ordenador moderno, pero sus máquinas presentaban una desventaja fundamental: funcionaban solo dentro de las matemáticas decimales. Este problema se solucionó gracias al trabajo de George Boole.


Boole: Un lenguaje para dominarlos a todos

En 1854, Boole publicó su Investigation of the Laws of Thought (Investigación de las leyes del pensamiento), que introdujo lo que actualmente se conoce como álgebra booleana.

En esta obra, Boole sugería que la lógica pertenece al ámbito de las matemáticas, más que al de la filosofía. Al igual que la geometría, se basa en una serie de axiomas sencillos. Además, al igual que la aritmética tiene unas funciones primarias, como la suma, la multiplicación y la división, la lógica puede reducirse a operadores como:

  • AND
  • OR
  • NOT

Estos operadores pueden utilizarse en un sistema binario (el sistema digital tiene diez dígitos; el sistema binario funciona igual, pero solo con dos). El “verdadero” y “falso” de la lógica se reducen al 0 y 1 de la matemática binaria.

images

Boss

Así, el álgebra binaria reduce cualquier proposición lógica, independientemente del número de términos que contenga, a una simple secuencia de símbolos binarios. Eso cabría en una simple tira de papel, en la que el álgebra binaria se reduce a una secuencia de orificios (y ausencia de orificios). De este modo, se podría introducir todo un “argumento” lógico o programa en una máquina.

Con dígitos binarios, las máquinas podrían seguir instrucciones lógicas y su matemática se adaptaba perfectamente al circuito eléctrico de encendido/apagado. Así, el dígito binario (o bit) llegó a ser la unidad fundamental de información de los sistemas informáticos.


Herman Hollerith: Money, money!

ibm-launches-services-to-tackle-fraud-financial-crime1En lo que al mundo respecta, el siguiente paso importante lo dio Herman Hollerith, un estadístico estadounidense. Hollerith desarrolló una “máquina de censo”, que podía leer tarjetas de hasta 288 orificios, y almacenar la información. Su máquina electromecánica podía leer hasta 80 tarjetas por minuto.

Cuando se utilizó para el censo de estadounidenses de 1890, la máquina de Hollerith procesó todos los datos en seis semanas (la elaboración del anterior censo, de 1880, había llevado tres años). En 1896 Hollerith se metió en el mundo de los negocios, y creó la Tabulating Machine Company, que más adelante se convertiría en la International Business Machine Corporation (IBM).

¿Y ahora que hacemos con esto?

Se habían descubierto los elementos necesarios para el ordenador moderno (incluyendo la explotación comercial). Lo único que faltaba era que alguien descubriera qué podía hacer: las posibilidades y limitaciones teóricas. Esto fue lo que hizo Alan Turing.


Alan Turing

turing.png

Estúpido y sensual Turing

Alan Turing es el hombre que debemos agradecer por un mundo libre de Nazis y lleno de computadoras.

…Y lo feo es que no tienes ni idea de lo mal que lo tratamos.

En 1936, Alan Turing publicó un artículo titulado “Computables Numbers, with a Application to the Entscheidungs problem”, en el que presentaba la noción de una máquina universal (más tarde llamada “máquina universal de Turing” y luego “máquina de Turing”) capaz de computar cualquier cosa que sea computable. El concepto central de la computadora moderna se basó en el papel de Turing.

mat31.jpg

Propuesta de una máquina de Turing

Deja que te lo explique de otra manera, el en su cabeza pensó en una máquina que pudiera calcular todo aquello que fuera calculable… sin crearla…Antes siquiera de que existiera la primera computadora moderna. ESO ES SER UN GENIO.

Durante los próximos dos años, Turing estudió matemáticas y criptología en el Instituto de Estudios Avanzados de Princeton.codebreaker-replica-ft.jpg

Después de recibir su Doctorado volvió a Cambridge, y entonces tomó una posición a tiempo parcial con el código del gobierno y la escuela del Cypher, una organización británica que descifraba códigos.

397px-turing-statue-bletchley_11Durante la Segunda Guerra Mundial, Turing fue un participante destacado en el Código Enigma. Las contribuciones de Turing al proceso de codificación no se detuvieron allí: también escribió dos artículos sobre métodos matemáticos para descifrar más códigos.

Turing se trasladó a Londres a mediados de la década de 1940 y comenzó a trabajar para el National Physical Laboratory. Entre sus contribuciones más notables mientras trabajaba en la instalación, Turing lideró el trabajo de diseño para el Mecanismo Automático de Computación.

Aunque una versión completa de la ACE nunca fue construida, su concepto ha sido utilizado como un modelo por las corporaciones de tecnología en todo el mundo durante varios años, influyendo en el diseño del DEUCE y el Bendix G-15-acreditado por muchos como la primera computadora personal del mundo.

alan.jpg

Abordó el tema de la inteligencia artificial en su artículo de 1950, “Computación de maquinaria e inteligencia”, y propuso un experimento conocido como “Prueba de Turing”, un esfuerzo para crear un estándar de diseño de inteligencia para la industria tecnológica.


Von Neumann

Nació Budapest (Hungría) en 1903, es my famosa la historia de que desde que era pequeño tenía una memoria fotográfica, era capaz de memorizar y recitar una página de una guía de teléfonos en pocos minutos.

Cita-4.png

Publicó su primer trabajo matemático en colaboración con su maestro los 18 años  y decidió estudiar matemáticas en la Universidad de Budapest en 1921 y durante los años siguientes asistió a la Universidad de Berlín y al Instituto Federal Suizo de Tecnología en Zurich. En 1926, recibió su Doctorado en matemáticas.

Von Neumann se describe comúnmente como un bromista y siempre se la vivía de fiesta. Lo cual contrasta mucho con la idea que siempre tenemos de los científicos y los computologos, retraídos y muy tímidos. Von Neumann era como el R. Feynman de la computación.

Serio.png

Foto 100% Real no Fake

A pesar de sus peculiaridades de personalidad, nadie podía negar que Von Neumann era brillante. A partir de 1927, Von Neumann aplicó nuevos métodos matemáticos a la teoría cuántica. Su trabajo fue instrumental en las posteriores interpretaciones “filosóficas” de la teoría.

Además es uno de los grandes padres de las teoría del juego en especial gracias a su libro “Theory of Games and Economic Behavior”.

cita-2

Era tan seguro de sus teorías que desde el comienzo de la Segunda Guerra Mundial confiaba en la victoria de los Aliados, es más esbozó un modelo matemático del conflicto del que dedujo que los Aliados ganarían, aplicando algunos de los métodos de la teoría que el mismo había desarrollado. Incluso trabajo en el Proyecto Manhattan.

¿Y las computadoras?

“De todo el trabajo de posguerra de Von Neumann, su desarrollo de la computadora digital es el que causó mas impacto al día de hoy.” (Poundstone página 76) .

Después de examinar el ENIAC del ejército durante la guerra, Von Neumann se volvió casi loco porque estaba lleno de ideas para diseñar una computadora mejor, usando sus habilidades matemáticas para mejorar el diseño lógico de la computadora.

von.jpg

Aquí pasando el rato – Von “Pillin” Neumann

Una vez que la guerra había terminado, la Marina de Estados Unidos proporcionó fondos para la máquina de Von Neumann, que él afirmó sería capaz de predecir con precisión los patrones climáticos.

Capaz de 2.000 operaciones por segundo, la computadora no predijo el tiempo muy bien (XD) , pero se hizo bastante útil haciendo un conjunto de cálculos necesarios para el diseño de la bomba de hidrógeno.

Cita-3.png

Cita también real

Von Neumann también es acreditado con la idea de basar los cálculos de la computadora en números binarios, teniendo programas almacenados en la memoria del ordenador en forma codificada en contraposición a tiras de papel (que quizá recuerdes), y varios otros desarrollos cruciales. La esposa de Von Neumann, Klara, se convirtió en uno de las primeros programadoras.

Von Neumann más tarde ayudó a diseñar el sistema informático SAGE diseñado para detectar un ataque nuclear soviético

 


John Hopcroft

Siempre es común hablar de el junto con su colega  Jeffrey D. Ullman a través de la investigación pionera y libros de texto de gran alcance, John Hopcroft y Jeffrey D. Ullman son conocidos como dos de las figuras más influyentes responsables de dar forma al campo de la informática.

jehyoung

Ese men

Estos gigantes de la informática se conocieron por primera vez en 1964 cuando el Dr. Ullman tomó el curso de teoría de autómatas del Dr. Hopcroft en la Universidad de Princeton.

41f8m0325wl-_sx343_bo1204203200_

Juntos, escribieron el libro sobre la teoría de autómatas y lenguajes formales que fue utilizado por las universidades de todo el mundo para educar a la primera generación de informáticos, las lenguas formales y su relación con los autómatas, su sucesor, Teoría de los Autómatas, Lenguajes y Computación, todavía está en uso hoy en día.

El Dr. Hopcroft es considerado uno de solamente un puñado de los informáticos que crearon la disciplina de la informática teórica, unificando la teoría de los autómatas y lenguajes formales durante los últimos años 60.

También determinó que la programación de computadoras podría ser sintetizada en una teoría de algoritmos y que estos algoritmos podrían ser evaluados por su complejidad asintótica. Esto condujo a un conjunto de principios de diseño que podrían utilizarse para diseñar algoritmos óptimos. Un compañero de la vida de IEEE, el Dr. Hopcroft es también un miembro de la Academia Nacional de las Ciencias y de la Academia Nacional de la Ingeniería.

Actualmente es el Profesor de Ingeniería y Matemáticas Aplicadas de IBM en la Universidad de Cornell, Ithaca, N.Y.

 

 


Dennis Ritchie

El es uno de los padres de la computación actual, si hoy en día tenemos celulares en nuestras casas, ordenadores, o demás es porque el motivado el gran boom! del software.

Cita.png

Mi humilde traducción a este:

dennis_ritchie

Precioso meme

El al crear C,  que es lo que ha hecho crecer al mundo de los ordenadores, hablando de fechas, el creo C en 1972 mientras trabajaba para Bell Labs junto con Kerrigan todo el equipo estaba trabajando en el desarrollo de un nuevo sistema operativo….UNIX. C fue creado con un solo propósito: CREAR Y TRABAJAR en UNIX.

 

 

 


Generaciones de las Computadoras

Una forma común de entender a las computadoras es entenderlas por generaciones, he de aclarar antes de empezar que esto es un desorden (como la historia en general) ¿Qué es la historia moderna?¿ En que día empezó el imperialismo?

Esta categoría no tiene las líneas o límites claro, y no busca eso, sino más bien busca darte una idea de la evolución de estas maquinas.

 


Primera Generación (1942-1958)

eniac-2

ENIAC

En esta generación había una gran desconocimiento de las capacidades de las computadoras, puesto que se realizó un estudio en esta época que determinó que con veinte computadoras se saturaría el mercado de los Estados Unidos en el campo de procesamiento de datos.

Características:

  • Usaban tubos al vacío para procesar información.
  • Usaban cilindros magnéticos para almacenar información e instrucciones internas.
  • Eran sumamente grandes, utilizaban gran cantidad de electricidad, generaban gran cantidad de calor y eran sumamente lentas.
  • Se comenzó a utilizar el sistema binario para representar los datos.
  • En esta generación las máquinas son grandes y costosas (de un costo aproximado de 10,000 dólares).

 

La computadora más exitosa de la primera generación fue la IBM 650, de la cual se produjeron varios cientos. Esta computadora que usaba un esquema de memoria secundaria llamado tambor magnético, que es el antecesor de los discos actuales.

También podemos destacar de gran manera a al ENIAC (Electronic Numeric Integrator And Calculator).

ENIAC

Acrónimo para “Electronic Numerical Integrator And Calculator”, El ENIAC fue la primera computadora electrónica (aunque no usaba aun transistores ni chips integrados) utilizado para fines generales, como resolver problemas numéricos.

Fue inventado en la Universidad de Pensilvania en un esfuerzo para cálculos de artillería para el Laboratorio de Investigación Balística del Ejército de los Estados Unidos.
Su construcción comenzó en 1943. El ENIAC utilizó 17.468 tubos de vacío, 15.000 releays y pesó casi 50 toneladas, utiliza 200,000 Volts  y costó alrededor de $ 500,000.

Aunque no fue terminado hasta el final de la Segunda Guerra Mundial, el ENIAC fue creado para ayudar con el esfuerzo de la guerra contra las fuerzas alemanas. (Eso se llama llegar muy tarde).

eniac.jpg

Lo que distinguía a ENIAC de los demás era que una máquina de trabajo que realizaba miles de cálculos por segundo y sobretodo que podía ser reprogramada fácilmente para diferentes tareas. Fue un impresionante.

El 14 de febrero de 1946, el gobierno dio a conocer a ENIAC al dejarla de hacer un secreto, fue dado a conocer con frases como: “Una nueva máquina que se espera que revolucione las matemáticas y la ingeniería y cambie muchos de nuestros métodos de diseño industrial”. Los primeros comunicados describían a un “robot matemático” que trabajaba a una velocidad “fenomenal” que “libera el pensamiento a los científicos , ya que evitaba la pesadez de un largo trabajo de puros cálculos”.

El ENIAC se exhibe ahora en la Institución Smithsonian en Washington D.C.


Segunda Generación (1958-1964)

computer.png

 

Transistores. Eso lo cambio TODO.
En esta generación las computadoras se reducen de tamaño y son de menor costo. Aparecen muchas compañías y las computadoras eran bastante avanzadas para su época. Algunas computadoras se programaban con cinta perforadas y otras por medio de cableado en un tablero.

Características:

  • Usaban transistores para procesar información. Los transistores eran más rápidos, pequeños y más confiables que los tubos al vacío.
    200 transistores podían acomodarse en la misma cantidad de espacio que un tubo al vacío.
  • Usaban pequeños anillos magnéticos para almacenar información e instrucciones. cantidad de calor y eran sumamente lentas.
  • Se mejoraron los programas de computadoras que fueron desarrollados durante la primera generación. Usaban ahora algo conocido como Ensamblador,además se desarrollaron nuevos lenguajes de programación como COBOL y FORTRAN, los cuales eran comercialmente accesibles.
  • Se comenzó a disminuir el tamaño de las computadoras.

 

 

 


Tercera Generación (1964-1971)

4_4.jpg

La tercera generación de computadoras emergió con el desarrollo de circuitos integrados (pastillas de silicio) en las que se colocan miles de componentes electrónicos en una integración en miniatura.

Las computadoras nuevamente se hicieron más pequeñas, más rápidas, desprendían menos calor y eran energéticamente más eficientes. El ordenador IBM-360 dominó las ventas de la tercera generación de ordenadores desde su presentación en 1965. El PDP-8 de la Digital Equipment Corporation fue el primer miniordenador.

Características:

  • Se desarrollaron circuitos integrados para procesar información.
  • Se desarrollaron los “chips” para almacenar y procesar la información. Un “chip” es una pieza de silicio que contiene los componentes electrónicos en miniatura llamados semiconductores.
  • Los circuitos integrados recuerdan los datos, ya que almacenan la información como cargas eléctricas.
  • Surge la multiprogramación.
  • Emerge la industria del “software“.
  • Otra vez las computadoras se tornan más pequeñas, más ligeras y más eficientes.
  • Consumían menos electricidad, por lo tanto, generaban menos calor.

 

 

 


Cuarta Generación (1971-?)

fourthgen.PNG

Aparecen los microprocesadores que es un gran adelanto de la microelectrónica, son circuitos integrados de alta densidad y con una velocidad impresionante. Las micro computadoras con base en estos circuitos son extremadamente pequeñas y baratas, por lo que su uso se extiende al mercado industrial y comercial.

Aquí nacen las computadoras personales que han adquirido proporciones enormes y que han influido en la sociedad en general sobre la llamada “revolución informática”.

Características:

  • Se desarrolló el microprocesador.
  • Se colocan más circuitos dentro de un “chip”.
    LSI – Large Scale Integration circuit”.
    VLSI – Very Large Scale Integration circuit”.
  • Cada “chip” puede hacer diferentes tareas.
  • Un “chip” sencillo actualmente contiene la unidad de control y la unidad de aritmética/lógica. El tercer componente, la memoria primaria, es operado por otros “chips”.
  • Se reemplaza la memoria de anillos magnéticos por la memoria de “chips” de silicio.
  • Se desarrollan las microcomputadoras, o sea, computadoras personales o PC.
  • Se desarrollan las supercomputadoras.

 

 

 


¿Quinta Generación?

Hasta aquí parece que todo mas o menos un acuerdo común pero… ¿Es un computadora de 1971 de la misma generación que una MacBook de 2016? Pues yo..YO diría que sí, que correr bajo una misma arquitectura y que en esencia son lo mismo, pero veamos otras posturas.

En vista de la acelerada marcha de la microelectrónica, la sociedad industrial se ha dado a la tarea de poner también a esa altura el desarrollo del software y los sistemas con que se manejan las computadoras.

apple-macbook-2016-nw-g05

Surge la competencia internacional por el dominio del mercado de la computación, en la que se perfilan dos líderes que, sin embargo, no han podido alcanzar el nivel que se desea: la capacidad de comunicarse con la computadora en un lenguaje más cotidiano y no a través de códigos o lenguajes de control especializados.

Japón lanzó en 1983 el llamado “programa de la quinta generación de computadoras”, con los objetivos explícitos de producir máquinas con innovaciones reales en los criterios mencionados. Y en los Estados Unidos ya está en actividad un programa en desarrollo que persigue objetivos semejantes, que pueden resumirse de la siguiente manera:

  • Se desarrollan las micro computadoras, o sea, computadoras personales o PC.
  • Se desarrollan las supercomputadoras.

 

 

 

btn1 btn
btn