Codificación de Gödel
Dada una lista de números naturales xs, codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es
|
1 |
2^7 * 3^1 * 5^5 = 1200000 |
Definir las funciones
|
1 2 |
codificaG :: [Integer] -> Integer decodificaG :: Integer -> [Integer] |
tales que
(codificaG xs)es la codificación de Gödel dexs. Por ejemplo,
|
1 2 3 4 |
codificaG [6,0,4] == 1200000 codificaG [3,1,1] == 3600 codificaG [3,1,0,0,0,0,0,1] == 4423058640 codificaG [1..6] == 126111168580452537982500 |
(decodificaG n)es la lista xs cuya codificación esn. Por ejemplo,
|
1 2 3 4 |
decodificaG 1200000 == [6,0,4] decodificaG 3600 == [3,1,1] decodificaG 4423058640 == [3,1,0,0,0,0,0,1] decodificaG 126111168580452537982500 == [1,2,3,4,5,6] |
Comprobar con QuickCheck que ambas funciones son inversas; es decir,
|
1 2 |
decodificaG (codificaG xs) = xs codificaG (decodificaG n) = n |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
import Data.List (genericLength, group) import Data.Numbers.Primes (primes, primeFactors) import Test.QuickCheck (NonNegative (getNonNegative), NonEmptyList (NonEmpty), Positive (Positive, getPositive), quickCheck) -- 1ª definición de codificaG -- ========================== codificaG1 :: [Integer] -> Integer codificaG1 = codificaG1' . codificaAux codificaAux :: [Integer] -> [Integer] codificaAux = map succ codificaG1' :: [Integer] -> Integer codificaG1' = aux primes where aux _ [] = 1 aux (p:ps) (x:xs) = p^x * aux ps xs -- 2ª definición de codificaG -- ========================== codificaG2 :: [Integer] -> Integer codificaG2 = codificaG2' . codificaAux codificaG2' :: [Integer] -> Integer codificaG2' xs = product [p^x | (p, x) <- zip primes xs] -- 3ª definición de codificaG -- ========================== codificaG3 :: [Integer] -> Integer codificaG3 = codificaG3' . codificaAux codificaG3' :: [Integer] -> Integer codificaG3' xs = product (zipWith (^) primes xs) -- 4ª definición de codificaG -- ========================== codificaG4 :: [Integer] -> Integer codificaG4 = codificaG4' . codificaAux codificaG4' :: [Integer] -> Integer codificaG4' = product . zipWith (^) primes -- Comprobación de equivalencia de codificaG -- ========================================= -- La propiedad es prop_codificaG :: [NonNegative Integer] -> Bool prop_codificaG xs = all (== codificaG1 ys) [codificaG2 ys, codificaG3 ys, codificaG4 ys] where ys = map getNonNegative xs -- La comprobación es -- λ> quickCheck prop_codificaG -- +++ OK, passed 100 tests. -- Comparación de eficiencia de codificaG -- ====================================== -- La comparación es -- λ> length (show (codificaG1 (replicate (4*10^4) 1))) -- 208100 -- (1.73 secs, 2,312,100,136 bytes) -- λ> length (show (codificaG2 (replicate (4*10^4) 1))) -- 208100 -- (1.63 secs, 2,327,676,832 bytes) -- λ> length (show (codificaG3 (replicate (4*10^4) 1))) -- 208100 -- (1.62 secs, 2,323,836,832 bytes) -- λ> length (show (codificaG4 (replicate (4*10^4) 1))) -- 208100 -- (1.54 secs, 2,147,635,680 bytes) -- Definición de codificaG -- ======================= -- Usaremos la 4ª codificaG :: [Integer] -> Integer codificaG = codificaG4 -- Definición de decodificaG -- ========================= decodificaG :: Integer -> [Integer] decodificaG = decodificaAux . decodificaG' decodificaAux :: [Integer] -> [Integer] decodificaAux = map pred decodificaG' :: Integer -> [Integer] decodificaG' 1 = [0] decodificaG' n = aux primes (group (primeFactors n)) where aux _ [] = [] aux (x:xs) ((y:ys):yss) | x == y = 1 + genericLength ys : aux xs yss | otherwise = 0 : aux xs ((y:ys):yss) -- Comprobación de propiedades -- =========================== -- La primera propiedad es prop_decodificaG_codificaG :: NonEmptyList (NonNegative Integer) -> Bool prop_decodificaG_codificaG (NonEmpty xs) = decodificaG (codificaG ys) == ys where ys = map getNonNegative xs -- La comprobación es -- λ> quickCheck prop_decodificaG_codificaG -- +++ OK, passed 100 tests. -- La 2ª propiedad es prop_codificaG_decodificaG :: Positive Integer -> Bool prop_codificaG_decodificaG (Positive n) = codificaG (decodificaG n) == n -- la comprobación es -- λ> quickCheck prop_codificaG_decodificaG -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.