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
2^7 * 3^1 * 5^5 = 1200000 |
2^7 * 3^1 * 5^5 = 1200000
Definir las funciones
codificaG :: [Integer] -> Integer
decodificaG :: Integer -> [Integer] |
codificaG :: [Integer] -> Integer
decodificaG :: Integer -> [Integer]
tales que
(codificaG xs)
es la codificación de Gödel de xs
. Por ejemplo,
codificaG [6,0,4] == 1200000
codificaG [3,1,1] == 3600
codificaG [3,1,0,0,0,0,0,1] == 4423058640
codificaG [1..6] == 126111168580452537982500 |
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 es n
. Por ejemplo,
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] |
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,
decodificaG (codificaG xs) = xs
codificaG (decodificaG n) = n |
decodificaG (codificaG xs) = xs
codificaG (decodificaG n) = n