Enumeracion de Goedel

50 %
50 %
Information about Enumeracion de Goedel

Published on September 19, 2007

Author: stefanosalvatori

Source: slideshare.net

Description

Teoria de Computacion

Teoría de la Computación Enumeraciones y Numeración de Gödel

Enumeraciones y conjuntos contables Conjuntos de cardinalidad menor o igual a  0 conjuntos finitos conjuntos cuyos elementos están en correspondencia uno-a-uno con los números naturales Conjuntos contables (o enumerables) dado S, un conjunto cualquiera S está en correspondencia uno-a-uno con    f tal que f:  S f(0)=s 0 , f(1)=s 1 , f(2)=s 2 , etc. f es biyectiva f enumera a S

Conjuntos de cardinalidad menor o igual a  0

conjuntos finitos

conjuntos cuyos elementos están en correspondencia uno-a-uno con los números naturales

Conjuntos contables (o enumerables)

dado S, un conjunto cualquiera

S está en correspondencia uno-a-uno con    f tal que f:  S

f(0)=s 0 , f(1)=s 1 , f(2)=s 2 , etc.

f es biyectiva

f enumera a S

Enumeraciones y conjuntos contables Sea  un alfabeto finito Sea S el conjunto de todas las palabras sobre  ¿Es S contable?  es finito por lo tanto puede ser ordenado de alguna forma S k , el conjunto de todas las palabras de longitud k es finito, para k=0, 1, 2, ... S k también puede ser ordenado de alguna forma Luego S k es contable

Sea  un alfabeto finito

Sea S el conjunto de todas las palabras sobre 

¿Es S contable?

 es finito por lo tanto puede ser ordenado de alguna forma

S k , el conjunto de todas las palabras de longitud k es finito, para k=0, 1, 2, ...

S k también puede ser ordenado de alguna forma

Luego S k es contable

Enumeraciones y conjuntos contables ¿Ahora, cómo ordenamos S? Se ordena cada S k lexicográficamente, usando el orden dado a  luego se alinean primero los elemento de  , luego los de S 2 , S 3 , etc. Así, los elementos de S están ordenados por longitud y por cada longitud por orden lexicográfico Al ordenar S, hemos mostrado que hay una correspondencia uno-a-uno con  Teorema : El conjunto de todas las k-tuplas sobre  con k=1, 2, ... es contable infinito.

¿Ahora, cómo ordenamos S?

Se ordena cada S k lexicográficamente, usando el orden dado a 

luego se alinean primero los elemento de  , luego los de S 2 , S 3 , etc.

Así, los elementos de S están ordenados por longitud y por cada longitud por orden lexicográfico

Al ordenar S, hemos mostrado que hay una correspondencia uno-a-uno con 

Teorema : El conjunto de todas las k-tuplas sobre  con k=1, 2, ... es contable infinito.

Enumeraciones y conjuntos contables  k   , S k conj. De todas las k-tuplas de  es contable infinito k=1, S 1 =  es contable k+1, suponemos S k contable , así s k,0 , s k,1 ... Es la enumeración de S k , (s k,i ,j), j   , es una k+1-tupla, entonces S k+1 ={(s k,i ,j)  i, j   } consideremos los elementos de S k+1 en el sgte arreglo (s k1 ,0) (s k,0 ,0) (s k0 ,2) (s k,0 ,1) ... (s k,1 ,2) (s k,1 ,1) (s k,2 ,0) (s k2 ,2) (s k,2 ,1) ... (s k,3 ,0) (s k,3 ,1) ... ... ... ... Método zig-zag

 k   , S k conj. De todas las k-tuplas de  es contable infinito

k=1, S 1 =  es contable

k+1, suponemos S k contable , así s k,0 , s k,1 ... Es la enumeración de S k , (s k,i ,j), j   , es una k+1-tupla, entonces S k+1 ={(s k,i ,j)  i, j   }

consideremos los elementos de S k+1 en el sgte arreglo

Numeraciones de Gödel Sea  un alfabeto finito Sea S el conjunto de todas las palabras sobre  Sea S* el conjunto de todas las k-tuplas, para todo k>0, de elementos de S Si  es el alfabeto inglés,  ={a, b, c, ..., z} S contiene todas las palabras posibles de formar con el alfabeto y S* puede entenderse como el conjunto de todas las frases posibles de formar con las palabras Como ya se mostró, para cualquier  finito S* es contable

Sea  un alfabeto finito

Sea S el conjunto de todas las palabras sobre 

Sea S* el conjunto de todas las k-tuplas, para todo k>0, de elementos de S

Si  es el alfabeto inglés,  ={a, b, c, ..., z}

S contiene todas las palabras posibles de formar con el alfabeto y

S* puede entenderse como el conjunto de todas las frases posibles de formar con las palabras

Como ya se mostró, para cualquier  finito S* es contable

Numeraciones de Gödel Si S* es enumerable tenemos f:  S* y f -1 : S*  ¿Son f y f -1 computables? Supongamos ahora  cualquier conjunto contable infinito de símbolos y S y S* son los correspondientes conjuntos de palabras y k-tuplas de palabras respectivamente Cualquier mapeamiento efectivo biyectivo de S a  (o de S* a  ) se llama numeración de Gödel de S (o de S*)

Si S* es enumerable tenemos

f:  S* y

f -1 : S* 

¿Son f y f -1 computables?

Supongamos ahora  cualquier conjunto contable infinito de símbolos y S y S* son los correspondientes conjuntos de palabras y k-tuplas de palabras respectivamente

Cualquier mapeamiento efectivo biyectivo de S a  (o de S* a  ) se llama numeración de Gödel de S (o de S*)

Numeraciones de Gödel Consideremos una numeración particular de Gödel que se basa en el siguiente teorema conocido como teorema fundamental de la aritmética (o de factorización única) Teorema : cualquier entero positivo m>1 puede ser factorizado de una forma única como Ejemplo: 24 = 2 3  3 1 m=p 1 p 2 ...p n e 2 e 1 e n Donde p 1 < p 2 < ...< p n son primos y cada e i > 0

Consideremos una numeración particular de Gödel que se basa en el siguiente teorema conocido como teorema fundamental de la aritmética (o de factorización única)

Teorema : cualquier entero positivo m>1 puede ser factorizado de una forma única como

Ejemplo: 24 = 2 3  3 1

Numeraciones de Gödel Definamos el mapeamiento  : S*   inductivamente, de los elementos de  de la siguiente manera  a i = p i donde p i es el i-ésimo primo, tomando p o = 2 Si  S, entonces  es de la forma a i0 a i1 ...a ik , así definimos  = 2 ·3 ·... ·p k nótese que el mapeamiento  no es onto a  note también que en la numeración de Gödel a i  , por lo tanto  a i = p i a i  S, por lo tanto  a i = 2 pi a i  S*, por lo tanto  a i = ?  a i0  a i1  a ik

Definamos el mapeamiento  : S*   inductivamente, de los elementos de  de la siguiente manera  a i = p i donde p i es el i-ésimo primo, tomando p o = 2

Si  S, entonces  es de la forma a i0 a i1 ...a ik , así definimos

 = 2 ·3 ·... ·p k

nótese que el mapeamiento  no es onto a 

note también que en la numeración de Gödel

a i  , por lo tanto  a i = p i

a i  S, por lo tanto  a i = 2 pi

a i  S*, por lo tanto  a i = ?

Numeraciones de Gödel Ejemplo  = {a, b, c}  a = 2  b = 3  c = 5  = aab  aab = 2 2 ·3 2 ·5 3 La numeración de Gödel establece un procedimiento a través del cual , dado un elemento de S (o S*, o S  S*), se puede computar efectivamente un número n   Inversamente, dado cualquier n   se puede decidir efectivamente si comprende a algún elemento de S (o S*, o S  S*)

Ejemplo

 = {a, b, c}

 a = 2  b = 3  c = 5

 = aab  aab = 2 2 ·3 2 ·5 3

La numeración de Gödel establece un procedimiento a través del cual , dado un elemento de S (o S*, o S  S*), se puede computar efectivamente un número n  

Inversamente, dado cualquier n   se puede decidir efectivamente si comprende a algún elemento de S (o S*, o S  S*)

Conclusión Si podemos aplicar la numeración de Gödel a conjuntos de palabras que son de interés, por alguna razón, entonces podemos transportar nuestras investigaciones sobre estos conjuntos al marco del conjunto de los números naturales y funciones numérico-teóricas En particular, los problemas de decisión sobre conjuntos de palabras se transforman en problemas de decisión sobre conjuntos de números naturales

Si podemos aplicar la numeración de Gödel a conjuntos de palabras que son de interés, por alguna razón, entonces podemos transportar nuestras investigaciones sobre estos conjuntos al marco del conjunto de los números naturales y funciones numérico-teóricas

En particular, los problemas de decisión sobre conjuntos de palabras se transforman en problemas de decisión sobre conjuntos de números naturales

Add a comment

Related presentations

Related pages

About: Gödel numbering

dbpedia:Goedel-numbering; dbpedia:Goedel_code; dbpedia:Goedel_numbering; dbpedia:Goedel_numbers; is owl:sameAs of: dbpedia:Gödel numbering; is foaf ...
Read more

Enumeration - Wikipedia, the free encyclopedia

An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and theoretical computer science ...
Read more

La herencia de Gödel: revisitando la Lógica

RESUMEN: Se exponen algunas equivocaciones sobre temas fundamentales de Lógica frecuentemente difundidas: la interpretación de los dos Teoremas de ...
Read more

Bioética, incompletitud e inconmensurabilidad - ResearchGate

Bioética, incompletitud e inconmensurabilidad. Luis Álvaro Cadena Monroy. Revista Colombiana de Bioética . 01/2011; 6:26-40. ...
Read more

Función recurrente primitiva • es.knowledger.de

Las funciones recurrentes primitivas se definen usando la recursión primitiva (Recursión (ciencias informáticas)) y la composición (composición de ...
Read more

Numeración de Gödel - Wikipedia, la enciclopedia libre

La numeración de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN).
Read more

Las ciencias sociales y el problema de la complejidad ...

Page 1. DeclARAcIóN De oDIo 15 ARGUMeNToS • UAM-X • MÉXIco lAS cIeNcIAS SocIAleS y el pRoBleMA De lA coMpleJIDAD Myriam cardozo Brum la ciencia ...
Read more