Maquina Turing Suma Binarios
Páginas: 10 (2417 palabras)
Publicado: 18 de junio de 2014
Suma de Números Binarios
Máquina de Turing
Sistema Binario - Bits
El sistema binario, como su nombre lo indica, es un sistema numérico compuesto por dos dígitos: el "0" y el "1". El sistema usual es el decimal, que tiene como base los diez dígitos habituales: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a partir de los cuales se combinan todos los otros números. Comparativamente, tenemosla tabla:
Decimal
Binario
Decimal
Binario
Decimal
Binario
0
0
7
111
14
1110
1
1
8
1000
15
1111
2
10
9
1001
16
10000
3
11
10
1010
.
4
100
11
1011
.
5
101
12
1100
.
6
110
13
1101
167
10100111
Esta notación presenta un particular interés, en lo que se refiere a la ciencia de los computadores, basada en el almacenamiento de información en bitsUn "bit" es la mínima unidad de información. Abreviatura de "dígito binario", un bit puede representar cualquier estado o su negación. Sí o no. Verdadero o falso:
¡Los famosos 0s y 1s!
Las leyes de la lógica binaria están en la base de la computación tal cual la conocemos hoy. Para representar un bit de información en los microprocesadores se utiliza la ausencia o presencia de miles demillones de electrones en un diminuto transistor.
Luego 1 byte = 8 bits
1 kB = 1 kilo byte = 1.000 bytes
1 MB = 1 mega byte = 1.000.000 bytes
1 GB = 1 guiga byte = 1.000.000.000 bytes
1 TB = 1 tera byte = 1.000.000.000.000 bytes
De esta manera, la secuencia de un dispositivo como el de Turing, se presenta de la manera siguiente:
1 La máquina se encuentra en cierto estado interno.
2 Llegael input por la derecha, la máquina lee en la cinta un "0" o un "1".
3 Esto le indica conservar o pasar a un nuevo estado interno, rescribir y desplazarse de un solo cuadrado a la izquierda o la derecha.
4 La máquina se encuentra entonces en el mismo o un nuevo estado interno.
5 La máquina lee en la cinta otro "0" o otro "1".
6 Esto le indica un nuevo estado interno, reescritura ydesplazamiento, a la izquierda o la derecha.
7 Continua así, hasta que reconoce (en caso que sea posible) una orden de detención que significaría que terminó el cálculo, que se leería en este caso a la izquierda.
Los estados internos de una máquina de Turing, si bien pueden ser grandes, no dejan de ser finitos, por lo tanto numerables y para efectos de simplificación dichos estados internos seránrepresentados (o enumerados) por secuencias de 0s y 1s, según el famoso esquema binario. El input igualmente, cual sea su tamaño, será finito y por lo tanto numerable y entonces codificable a su vez en notación binaria. No obstante, la codificación presenta algunas complicaciones, por lo cual se utiliza una variación del sistema binario simple a uno llamado extendido que presenta la ventaja deinsertar en el input, no sólo números, sino también operaciones u otros símbolos, pero esto no presenta ninguna complicación en el concepto.
Por ejemplo, la secuencia:
"5,13,0,1,1,4,"
equivale a la secuencia binaria simple:
"101,1101,0,1,1,100,"
que equivale a su vez a la secuencia binaria extendida:
"...000010010110101001011001101011010110100011000..."
que es aquella que nos importará acontinuación y donde:
"0" es representado por 0
"1" es representado por 10
"," es representado por 110
Ejemplo: programa que multiplica por dos un número entero cualquiera:
Máquina de Turing: " x 2 "
Si el estado interno es:
Y si lee en el cuadrado:
entonces debe pasar al estado interno:
reescribir en el mismo cuadrado:
luego moverse a la izquierda o laderecha:
0
0
0
0
D
0
1
1
0
D
1
0
0
1
D
1
1
10
0
D
10
0
11
1
D
11
0
0
1
D (Stop)
Si le damos a la máquina el número "3," por ejemplo ("11,") en binario simple, es decir: "...0000101011000..." en binario expandido y donde 110 indica la "," o fin de la codificación del número "3"·- los ceros adelante y atrás dan cuenta de la "infinitud" de la cinta simplemente -...
Máquina de Turing
Sistema Binario - Bits
El sistema binario, como su nombre lo indica, es un sistema numérico compuesto por dos dígitos: el "0" y el "1". El sistema usual es el decimal, que tiene como base los diez dígitos habituales: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a partir de los cuales se combinan todos los otros números. Comparativamente, tenemosla tabla:
Decimal
Binario
Decimal
Binario
Decimal
Binario
0
0
7
111
14
1110
1
1
8
1000
15
1111
2
10
9
1001
16
10000
3
11
10
1010
.
4
100
11
1011
.
5
101
12
1100
.
6
110
13
1101
167
10100111
Esta notación presenta un particular interés, en lo que se refiere a la ciencia de los computadores, basada en el almacenamiento de información en bitsUn "bit" es la mínima unidad de información. Abreviatura de "dígito binario", un bit puede representar cualquier estado o su negación. Sí o no. Verdadero o falso:
¡Los famosos 0s y 1s!
Las leyes de la lógica binaria están en la base de la computación tal cual la conocemos hoy. Para representar un bit de información en los microprocesadores se utiliza la ausencia o presencia de miles demillones de electrones en un diminuto transistor.
Luego 1 byte = 8 bits
1 kB = 1 kilo byte = 1.000 bytes
1 MB = 1 mega byte = 1.000.000 bytes
1 GB = 1 guiga byte = 1.000.000.000 bytes
1 TB = 1 tera byte = 1.000.000.000.000 bytes
De esta manera, la secuencia de un dispositivo como el de Turing, se presenta de la manera siguiente:
1 La máquina se encuentra en cierto estado interno.
2 Llegael input por la derecha, la máquina lee en la cinta un "0" o un "1".
3 Esto le indica conservar o pasar a un nuevo estado interno, rescribir y desplazarse de un solo cuadrado a la izquierda o la derecha.
4 La máquina se encuentra entonces en el mismo o un nuevo estado interno.
5 La máquina lee en la cinta otro "0" o otro "1".
6 Esto le indica un nuevo estado interno, reescritura ydesplazamiento, a la izquierda o la derecha.
7 Continua así, hasta que reconoce (en caso que sea posible) una orden de detención que significaría que terminó el cálculo, que se leería en este caso a la izquierda.
Los estados internos de una máquina de Turing, si bien pueden ser grandes, no dejan de ser finitos, por lo tanto numerables y para efectos de simplificación dichos estados internos seránrepresentados (o enumerados) por secuencias de 0s y 1s, según el famoso esquema binario. El input igualmente, cual sea su tamaño, será finito y por lo tanto numerable y entonces codificable a su vez en notación binaria. No obstante, la codificación presenta algunas complicaciones, por lo cual se utiliza una variación del sistema binario simple a uno llamado extendido que presenta la ventaja deinsertar en el input, no sólo números, sino también operaciones u otros símbolos, pero esto no presenta ninguna complicación en el concepto.
Por ejemplo, la secuencia:
"5,13,0,1,1,4,"
equivale a la secuencia binaria simple:
"101,1101,0,1,1,100,"
que equivale a su vez a la secuencia binaria extendida:
"...000010010110101001011001101011010110100011000..."
que es aquella que nos importará acontinuación y donde:
"0" es representado por 0
"1" es representado por 10
"," es representado por 110
Ejemplo: programa que multiplica por dos un número entero cualquiera:
Máquina de Turing: " x 2 "
Si el estado interno es:
Y si lee en el cuadrado:
entonces debe pasar al estado interno:
reescribir en el mismo cuadrado:
luego moverse a la izquierda o laderecha:
0
0
0
0
D
0
1
1
0
D
1
0
0
1
D
1
1
10
0
D
10
0
11
1
D
11
0
0
1
D (Stop)
Si le damos a la máquina el número "3," por ejemplo ("11,") en binario simple, es decir: "...0000101011000..." en binario expandido y donde 110 indica la "," o fin de la codificación del número "3"·- los ceros adelante y atrás dan cuenta de la "infinitud" de la cinta simplemente -...
Leer documento completo
Regístrate para leer el documento completo.