![Page 1: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/1.jpg)
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 1
Reducción de los Esquemas de Recursión
⋆ Tesina de Grado ⋆
Daniel E. Severin
DirecciónGabriela Argiroffo
![Page 2: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/2.jpg)
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 2
Introducción
![Page 3: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/3.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 3
Objetivos de la Teoría de la Computación
Uno de los objetivos fundamentales es
buscar conjuntos minimales de
operaciones que encapsulen un cierto
poder de cómputo.
![Page 4: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/4.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 3
Objetivos de la Teoría de la Computación
Uno de los objetivos fundamentales es
buscar conjuntos minimales de
operaciones que encapsulen un cierto
poder de cómputo.
Formalismos con el mismo poder de
cómputo que cualquier lenguaje de
propósito general son:◆ Máquinas de Turing◆ Funciones Recursivas Generales◆ Máquinas de Registros◆ Lambda Cálculo
![Page 5: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/5.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4
Definición de Formalismo
Es un conjunto de funciones generadas
inductivamente por la aplicación de
ciertos operadores, y que trabajan sobre
un dominio común.
![Page 6: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/6.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4
Definición de Formalismo
Es un conjunto de funciones generadas
inductivamente por la aplicación de
ciertos operadores, y que trabajan sobre
un dominio común.
Las funciones recursivas generales
componen un formalismo, en donde los
operadores son cero, sucesor,
proyección, composición, recursión
primitiva y minimización, y el dominio
son los conjuntos Nn.
![Page 7: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/7.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 5
Representabilidad entre Formalismos
Un formalismo compuesto de funciones f : A→ A
puede ser representado por otro formalismocompuesto de funciones g : B → B cuando existenfunciones D y P tales que
Af
- A
B
D
?
g = P(f)- B
D
?
D debe ser inyectiva.
![Page 8: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/8.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 6
Representabilidad entre Formalismos
■ Sean X e Y dos formalismos. Denotamos elhecho de que X puede ser representado por Y
con X⊂̇Y . Por ejemplo:
AutómatasRegulares ⊂̇ AutómatasPila
![Page 9: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/9.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 6
Representabilidad entre Formalismos
■ Sean X e Y dos formalismos. Denotamos elhecho de que X puede ser representado por Y
con X⊂̇Y . Por ejemplo:
AutómatasRegulares ⊂̇ AutómatasPila
■ Si se cumple en ambos sentidos (Y ⊂̇X y X⊂̇Y )entonces diremos que X tiene el mismo poderde expresión que Y , y lo denotamos con X
.= Y .
Por ejemplo:
MáquinasTuring.= FuncRecGenerales
![Page 10: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/10.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 7
Motivación
■ Las funciones recursivas trabajan sobre Nn. La
idea de esta tesina será proponer formalismosque tengan el mismo poder de expresión que lasfunciones recursivas, pero que sean mássencillos (trabajarán sobre N únicamente). Porejemplo:
FuncUnariasGenerales.= FuncRecGenerales
![Page 11: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/11.jpg)
IntroducciónObjetivos de la Teoría de la
Computación
Definición de FormalismoRepresentabilidad entre
FormalismosRepresentabilidad entre
Formalismos
Motivación
Funciones Recursivas
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 7
Motivación
■ Las funciones recursivas trabajan sobre Nn. La
idea de esta tesina será proponer formalismosque tengan el mismo poder de expresión que lasfunciones recursivas, pero que sean mássencillos (trabajarán sobre N únicamente). Porejemplo:
FuncUnariasGenerales.= FuncRecGenerales
■ También se investigarán técnicas para simplificaresquemas de recursión. Por ejemplo, laminimización puede ser reemplazada por unesquema más básico llamado inversión.
![Page 12: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/12.jpg)
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 8
Funciones Recursivas
![Page 13: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/13.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
![Page 14: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/14.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
![Page 15: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/15.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
![Page 16: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/16.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
3) π : N× N→ FRP | πni (x) = xi
![Page 17: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/17.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
3) π : N× N→ FRP | πni (x) = xi
4) φ : FRPn+1 → FRP | φ[ϕ, ω1, ω2, . . . , ωn](x) =
ϕ(ω1(x), ω2(x), . . . , ωn(x))
![Page 18: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/18.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
3) π : N× N→ FRP | πni (x) = xi
4) φ : FRPn+1 → FRP | φ[ϕ, ω1, ω2, . . . , ωn](x) =
ϕ(ω1(x), ω2(x), . . . , ωn(x))
5) ρ : FRP2 → FRP | ρ[α, β](x, 0) = α(x)
| ρ[α, β](x, y + 1) = β(x, y, ρ[α, β](x, y))
![Page 19: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/19.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
3) π : N× N→ FRP | πni (x) = xi
4) φ : FRPn+1 → FRP | φ[ϕ, ω1, ω2, . . . , ωn](x) =
ϕ(ω1(x), ω2(x), . . . , ωn(x))
5) ρ : FRP2 → FRP | ρ[α, β](x, 0) = α(x)
| ρ[α, β](x, y + 1) = β(x, y, ρ[α, β](x, y))
■ Ejemplo: cero(x) = 0
Se escribe cero ≡ ρ[ζ, π22]
![Page 20: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/20.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 9
Funciones Recursivas Primitivas
■ Compuesta por los esquemas:
1) ζ : FRP | ζ() = 0
2) σ : FRP | σ(x) = x + 1
3) π : N× N→ FRP | πni (x) = xi
4) φ : FRPn+1 → FRP | φ[ϕ, ω1, ω2, . . . , ωn](x) =
ϕ(ω1(x), ω2(x), . . . , ωn(x))
5) ρ : FRP2 → FRP | ρ[α, β](x, 0) = α(x)
| ρ[α, β](x, y + 1) = β(x, y, ρ[α, β](x, y))
■ Ejemplo: cero(x) = 0
Se escribe cero ≡ ρ[ζ, π22]
■ La mayoría de las funciones a valores naturalesconocidas son recursivas primitivas.
![Page 21: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/21.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 10
Funciones de Parificación de Cantor
N �π2
1N× N
π22 - N
N
〈
?
_, _〉
τ2
2
-
�
τ 21
y↓x→ 0 1 2 3 4 5
0 0 2 5 9 14 20
1 1 4 8 13 19 26
2 3 7 12 18 25 33
3 6 11 17 24 32 41
4 10 16 23 31 40 50
5 15 22 30 39 49 60
![Page 22: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/22.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 11
Funciones de Parificación de Cantor
■ Correspondencia biunívoca entre N y N2:
τ 21 (〈x, y〉) = x
τ 22 (〈x, y〉) = y
〈τ 21 (z), τ 2
2 (z)〉 = z
![Page 23: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/23.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 11
Funciones de Parificación de Cantor
■ Correspondencia biunívoca entre N y N2:
τ 21 (〈x, y〉) = x
τ 22 (〈x, y〉) = y
〈τ 21 (z), τ 2
2 (z)〉 = z
■ Propiedades de Monotonía:〈x + 1, y〉 > 〈x, y〉〈x, y + 1〉 > 〈x, y〉
![Page 24: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/24.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 11
Funciones de Parificación de Cantor
■ Correspondencia biunívoca entre N y N2:
τ 21 (〈x, y〉) = x
τ 22 (〈x, y〉) = y
〈τ 21 (z), τ 2
2 (z)〉 = z
■ Propiedades de Monotonía:〈x + 1, y〉 > 〈x, y〉〈x, y + 1〉 > 〈x, y〉
■ Se puede extender para Nn:
〈x, y, z〉 = 〈x, 〈y, z〉〉τ 31 (x) = τ 2
1 (x)
τ 32 (x) = τ 2
1 (τ 22 (x))
τ 33 (x) = τ 2
2 (τ 22 (x))
![Page 25: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/25.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 12
Estructuras de Datos
■ Listas de naturales:[ ] →→ 0
x : xs →→ 〈x, xs〉 + 1
Ej: [3, 5, 8] →→ 〈3, 〈5, 〈8, 0〉 + 1〉+ 1〉+ 1
foldr ∈ FRP
![Page 26: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/26.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 12
Estructuras de Datos
■ Listas de naturales:[ ] →→ 0
x : xs →→ 〈x, xs〉 + 1
Ej: [3, 5, 8] →→ 〈3, 〈5, 〈8, 0〉 + 1〉+ 1〉+ 1
foldr ∈ FRP
■ Conjuntos finitos:C →→ 2χC
(0) + 2χC(1) + 2χC
(2) + . . .
Ej: {3, 5, 8} →→ 23 + 25 + 28
![Page 27: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/27.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 12
Estructuras de Datos
■ Listas de naturales:[ ] →→ 0
x : xs →→ 〈x, xs〉 + 1
Ej: [3, 5, 8] →→ 〈3, 〈5, 〈8, 0〉 + 1〉+ 1〉+ 1
foldr ∈ FRP
■ Conjuntos finitos:C →→ 2χC
(0) + 2χC(1) + 2χC
(2) + . . .
Ej: {3, 5, 8} →→ 23 + 25 + 28
■ Híbridos:Listas de listas, conjuntos de pares, etc
![Page 28: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/28.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 12
Estructuras de Datos
■ Listas de naturales:[ ] →→ 0
x : xs →→ 〈x, xs〉 + 1
Ej: [3, 5, 8] →→ 〈3, 〈5, 〈8, 0〉 + 1〉+ 1〉+ 1
foldr ∈ FRP
■ Conjuntos finitos:C →→ 2χC
(0) + 2χC(1) + 2χC
(2) + . . .
Ej: {3, 5, 8} →→ 23 + 25 + 28
■ Híbridos:Listas de listas, conjuntos de pares, etc
■ Propiedad de correspondencia:Dos estructuras son iguales si los números quelas representan lo son también
![Page 29: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/29.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
![Page 30: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/30.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
2) δ : FDR5 → FDR | δ[α, . . .](x, 0, z) = α(x, z)
| δ[α, . . .](x, y + 1, 0) = . . .
| δ[α, . . .](x, y + 1, z + 1) = . . .
![Page 31: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/31.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
2) δ : FDR5 → FDR | δ[α, . . .](x, 0, z) = α(x, z)
| δ[α, . . .](x, y + 1, 0) = . . .
| δ[α, . . .](x, y + 1, z + 1) = . . .
■ Ej: A(x, y) =
y + 1 x = 0
A(x− 1, 1) x > 0, y = 0
A(x− 1,A(x, y − 1)) x > 0, y > 0
Se escribe A ≡ δ[σ, π22, φ[σ, cero], π4
4 , π33]]
![Page 32: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/32.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
2) δ : FDR5 → FDR | δ[α, . . .](x, 0, z) = α(x, z)
| δ[α, . . .](x, y + 1, 0) = . . .
| δ[α, . . .](x, y + 1, z + 1) = . . .
■ Ej: A(x, y) =
y + 1 x = 0
A(x− 1, 1) x > 0, y = 0
A(x− 1,A(x, y − 1)) x > 0, y > 0
Se escribe A ≡ δ[σ, π22, φ[σ, cero], π4
4 , π33]]
■ FRP⊂̇FDR (trivial)
![Page 33: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/33.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
2) δ : FDR5 → FDR | δ[α, . . .](x, 0, z) = α(x, z)
| δ[α, . . .](x, y + 1, 0) = . . .
| δ[α, . . .](x, y + 1, z + 1) = . . .
■ Ej: A(x, y) =
y + 1 x = 0
A(x− 1, 1) x > 0, y = 0
A(x− 1,A(x, y − 1)) x > 0, y > 0
Se escribe A ≡ δ[σ, π22, φ[σ, cero], π4
4 , π33]]
■ FRP⊂̇FDR (trivial)
■ FRP 6= FDR (pues A /∈ FRP)No se puede reducir la doble recursión a recursión primitiva!
![Page 34: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/34.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 13
Funciones Doblemente Recursivas
1) ϕ ∈ FRP =⇒ ϕ ∈ FDR
2) δ : FDR5 → FDR | δ[α, . . .](x, 0, z) = α(x, z)
| δ[α, . . .](x, y + 1, 0) = . . .
| δ[α, . . .](x, y + 1, z + 1) = . . .
■ Ej: A(x, y) =
y + 1 x = 0
A(x− 1, 1) x > 0, y = 0
A(x− 1,A(x, y − 1)) x > 0, y > 0
Se escribe A ≡ δ[σ, π22, φ[σ, cero], π4
4 , π33]]
■ FRP⊂̇FDR (trivial)
■ FRP 6= FDR (pues A /∈ FRP)No se puede reducir la doble recursión a recursión primitiva!
■ Existen funciones triplemente recursivas, etc
![Page 35: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/35.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
![Page 36: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/36.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
2) µ : FRG→ FRG | µϕ(x) = mı́ny∈N
{
ϕ(x, y) = 0}
![Page 37: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/37.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
2) µ : FRG→ FRG | µϕ(x) = mı́ny∈N
{
ϕ(x, y) = 0}
■ Estilo de evaluación estricto.Se extienden los naturales: N ∪ {⊥}
![Page 38: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/38.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
2) µ : FRG→ FRG | µϕ(x) = mı́ny∈N
{
ϕ(x, y) = 0}
■ Estilo de evaluación estricto.Se extienden los naturales: N ∪ {⊥}
■ Ejemplo: Undef() = mı́ny∈N
{
y + 1 = 0}
= ⊥Se escribe Undef ≡ µσ
![Page 39: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/39.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
2) µ : FRG→ FRG | µϕ(x) = mı́ny∈N
{
ϕ(x, y) = 0}
■ Estilo de evaluación estricto.Se extienden los naturales: N ∪ {⊥}
■ Ejemplo: Undef() = mı́ny∈N
{
y + 1 = 0}
= ⊥Se escribe Undef ≡ µσ
■ Kleene: Cualquier función recursiva a valoresnaturales puede ser escrita comoφ[α, µβ] donde α, β ∈ FRP
![Page 40: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/40.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 14
Funciones Recursivas Generales
1) ϕ ∈ FRP =⇒ ϕ ∈ FRG
2) µ : FRG→ FRG | µϕ(x) = mı́ny∈N
{
ϕ(x, y) = 0}
■ Estilo de evaluación estricto.Se extienden los naturales: N ∪ {⊥}
■ Ejemplo: Undef() = mı́ny∈N
{
y + 1 = 0}
= ⊥Se escribe Undef ≡ µσ
■ Kleene: Cualquier función recursiva a valoresnaturales puede ser escrita comoφ[α, µβ] donde α, β ∈ FRP
■ En particular, FDR⊂̇FRG
![Page 41: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/41.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 15
A ∈ FRG
■ Cálculo de A(1, 2):A(0, 1) = 2, A(0, 2) = 3,
A(0, 3) = 4, A(1, 0) = A(0, 1) = 2,
A(1, 1) = A(0,A(1, 0)) = A(0, 2) = 3,
A(1, 2) = A(0,A(1, 1)) = A(0, 3) = 4.
![Page 42: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/42.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 15
A ∈ FRG
■ Cálculo de A(1, 2):A(0, 1) = 2, A(0, 2) = 3,
A(0, 3) = 4, A(1, 0) = A(0, 1) = 2,
A(1, 1) = A(0,A(1, 0)) = A(0, 2) = 3,
A(1, 2) = A(0,A(1, 1)) = A(0, 3) = 4.
■ ℓ = [〈〈0, 1〉, 2〉, 〈〈0, 2〉, 3〉, 〈〈0, 3〉, 4〉,〈〈1, 0〉, 2〉, 〈〈1, 1〉, 3〉, 〈〈1, 2〉, 4〉] =72213613394442659972078783858050041504580975271804
Cómputo de A(1, 2) se representa con z = 〈〈1, 2〉, ℓ〉.
![Page 43: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/43.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 15
A ∈ FRG
■ Cálculo de A(1, 2):A(0, 1) = 2, A(0, 2) = 3,
A(0, 3) = 4, A(1, 0) = A(0, 1) = 2,
A(1, 1) = A(0,A(1, 0)) = A(0, 2) = 3,
A(1, 2) = A(0,A(1, 1)) = A(0, 3) = 4.
■ ℓ = [〈〈0, 1〉, 2〉, 〈〈0, 2〉, 3〉, 〈〈0, 3〉, 4〉,〈〈1, 0〉, 2〉, 〈〈1, 1〉, 3〉, 〈〈1, 2〉, 4〉] =72213613394442659972078783858050041504580975271804
Cómputo de A(1, 2) se representa con z = 〈〈1, 2〉, ℓ〉.■ α(z) = 4 ← extrae la solución del cómputo z
![Page 44: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/44.jpg)
Introducción
Funciones RecursivasFunciones Recursivas
PrimitivasFunciones de Parificación de
CantorFunciones de Parificación de
Cantor
Estructuras de DatosFunciones Doblemente
RecursivasFunciones Recursivas
Generales
A ∈ FRG
Funciones Unarias
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 15
A ∈ FRG
■ Cálculo de A(1, 2):A(0, 1) = 2, A(0, 2) = 3,
A(0, 3) = 4, A(1, 0) = A(0, 1) = 2,
A(1, 1) = A(0,A(1, 0)) = A(0, 2) = 3,
A(1, 2) = A(0,A(1, 1)) = A(0, 3) = 4.
■ ℓ = [〈〈0, 1〉, 2〉, 〈〈0, 2〉, 3〉, 〈〈0, 3〉, 4〉,〈〈1, 0〉, 2〉, 〈〈1, 1〉, 3〉, 〈〈1, 2〉, 4〉] =72213613394442659972078783858050041504580975271804
Cómputo de A(1, 2) se representa con z = 〈〈1, 2〉, ℓ〉.■ α(z) = 4 ← extrae la solución del cómputo z
■ A(x, y) = α(mı́nz∈N
{
β(x, y, z) = 0}
)
β(x, y, z) verifica que el cómputo z sea de A(x, y)
![Page 45: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/45.jpg)
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 16
Funciones Unarias
![Page 46: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/46.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 17
Funciones Unarias Primitivas
1) S : FUP
S(x) = x + 1
![Page 47: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/47.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 17
Funciones Unarias Primitivas
1) S : FUP
S(x) = x + 1
2) _−• _ : FUP× FUP→ FUP
(F −• G)(x) =
{
0 si F (x) < G(x)
F (x)−G(x) si no
![Page 48: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/48.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 17
Funciones Unarias Primitivas
1) S : FUP
S(x) = x + 1
2) _−• _ : FUP× FUP→ FUP
(F −• G)(x) =
{
0 si F (x) < G(x)
F (x)−G(x) si no
3) _ ◦ _ : FUP× FUP→ FUP
(F ◦G)(x) = F (G(x))
![Page 49: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/49.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 17
Funciones Unarias Primitivas
1) S : FUP
S(x) = x + 1
2) _−• _ : FUP× FUP→ FUP
(F −• G)(x) =
{
0 si F (x) < G(x)
F (x)−G(x) si no
3) _ ◦ _ : FUP× FUP→ FUP
(F ◦G)(x) = F (G(x))
4) _� : FUP→ FUP
F�(x) =
{
0 si x = 0
F (F�(x− 1)) si x > 0
Es decir, F�(0) = 0, F�(1) = F (0),F�(2) = F (F (0)), . . ., F�(x) = F x(0), . . .
![Page 50: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/50.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 18
Algunas FUPs
■ Identidad: S�(x) = Sx(0) = x
![Page 51: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/51.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 18
Algunas FUPs
■ Identidad: S�(x) = Sx(0) = x
■ F. ariméticas: n, 2x, ⌊x/2⌋, x2, ⌊√x⌋, τni (x), etc
![Page 52: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/52.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 18
Algunas FUPs
■ Identidad: S�(x) = Sx(0) = x
■ F. ariméticas: n, 2x, ⌊x/2⌋, x2, ⌊√x⌋, τni (x), etc
■ Suma de FUPs:_ + _ : FUP× FUP→ FUP
(F + G)(x) = M(x)−• ((M(x)−• F (x))−• G(x))
donde M(x) ≥ F (x) + G(x)
![Page 53: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/53.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 18
Algunas FUPs
■ Identidad: S�(x) = Sx(0) = x
■ F. ariméticas: n, 2x, ⌊x/2⌋, x2, ⌊√x⌋, τni (x), etc
■ Suma de FUPs:_ + _ : FUP× FUP→ FUP
(F + G)(x) = M(x)−• ((M(x)−• F (x))−• G(x))
donde M(x) ≥ F (x) + G(x)
■ Producto de FUPs:_._ : FUP× FUP→ FUP
(F.G)(x) =(F (x) + G(x))2−• F (x)2−• G(x)2
2
![Page 54: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/54.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 18
Algunas FUPs
■ Identidad: S�(x) = Sx(0) = x
■ F. ariméticas: n, 2x, ⌊x/2⌋, x2, ⌊√x⌋, τni (x), etc
■ Suma de FUPs:_ + _ : FUP× FUP→ FUP
(F + G)(x) = M(x)−• ((M(x)−• F (x))−• G(x))
donde M(x) ≥ F (x) + G(x)
■ Producto de FUPs:_._ : FUP× FUP→ FUP
(F.G)(x) =(F (x) + G(x))2−• F (x)2−• G(x)2
2■ Parificación de FUPs:
< _, _, . . . , _ >: FUPn → FUP
< F1, F2, . . . , Fn > (x) = 〈F1(x), F2(x), . . . , Fn(x)〉
![Page 55: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/55.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 19
Representabilidad de FUPs con FRPs
FUP⊂̇FRP es trivial
NF
- N
N
D
?
P(F )- N
D
?
D(x) = x
P : FUP→ FRP
P S = σ
P (F −• G) = φ[Mon,P F,P G]
P (F ◦G) = φ[P F,P G]
P F� = ρ[ζ, φ[P F, π22]]
![Page 56: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/56.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 20
Representabilidad de FRPs con FUPs
Nn
ϕ- N
N
D
?
P(ϕ)- N
D
?
D(x1, x2, . . . , xn) = 〈x1, x2, . . . , xn〉P : FRP→ FUP
P ζ = S−• S
P σ = S
P πni = τn
i
P φ[ϕ, ω1, ω2, . . . , ωn]
= (P ϕ) ◦ < P ω1,P ω2, . . . ,P ωn >
![Page 57: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/57.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 21
Reducción de la Recursión Primitiva
P ρ[α, β] = · · · V � · · ·
R
8
<
:
F (x1, . . . , xn, 0) = α(x1, . . . , xn),
F (x1, . . . , xn, y + 1) = β(x1, . . . , xn, y, F (x1, . . . , xn, y)),
R1
8
<
:
F1(x, 0) = A(x),
F1(x, y + 1) = B(x, y, F1(x, y)),
R2
8
<
:
F2(x, 0) = C(x),
F2(x, y + 1) = D(y, F2(x, y)),
R3
8
<
:
F3(x, 0) = x,
F3(x, y + 1) = E(y, F3(x, y)),
R4
8
<
:
F4(0) = 0,
F4(y + 1) = U(y, F4(y)),R5
8
<
:
F5(0) = 0,
F5(y + 1) = V (F5(y)),
![Page 58: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/58.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 21
Reducción de la Recursión Primitiva
P ρ[α, β] = · · · V � · · ·
R
8
<
:
F (x1, . . . , xn, 0) = α(x1, . . . , xn),
F (x1, . . . , xn, y + 1) = β(x1, . . . , xn, y, F (x1, . . . , xn, y)),
R1
8
<
:
F1(x, 0) = A(x),
F1(x, y + 1) = B(x, y, F1(x, y)),
R2
8
<
:
F2(x, 0) = C(x),
F2(x, y + 1) = D(y, F2(x, y)),
R3
8
<
:
F3(x, 0) = x,
F3(x, y + 1) = E(y, F3(x, y)),
R4
8
<
:
F4(0) = 0,
F4(y + 1) = U(y, F4(y)),R5
8
<
:
F5(0) = 0,
F5(y + 1) = V (F5(y)),
FUP.= FRP
![Page 59: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/59.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 22
Funciones Unarias Generales
1) F ∈ FUP =⇒ F ∈ FUG
![Page 60: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/60.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 22
Funciones Unarias Generales
1) F ∈ FUP =⇒ F ∈ FUG
2) _− : FUG→ FUG
F−(x) = mı́nz∈N
{
F (z) = x}
Si F es biyectiva, F− es su inversa
![Page 61: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/61.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 22
Funciones Unarias Generales
1) F ∈ FUP =⇒ F ∈ FUG
2) _− : FUG→ FUG
F−(x) = mı́nz∈N
{
F (z) = x}
Si F es biyectiva, F− es su inversa
■ FUG.= FRG
P F− = µφ[Dist, φ[P F, π22], π
21]
![Page 62: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/62.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 22
Funciones Unarias Generales
1) F ∈ FUP =⇒ F ∈ FUG
2) _− : FUG→ FUG
F−(x) = mı́nz∈N
{
F (z) = x}
Si F es biyectiva, F− es su inversa
■ FUG.= FRG
P F− = µφ[Dist, φ[P F, π22], π
21]
■ Cualquier función recursiva con un argumentonatural puede ser escrita comoA ◦B− donde A,B ∈ FUP
![Page 63: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/63.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 23
Reducción de la minimización
P µϕ = · · ·H− · · ·M : F (x1, . . . , xn) = mı́n
y∈N
˘
ϕ(x1, . . . , xn, y) = 0¯
M̂ : F̂ (x) = mı́ny∈N
˘
G(x, y) = 0¯
ˆ̂M :
ˆ̂F (x) = mı́n
z∈N
˘
H(z) = x¯
![Page 64: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/64.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 23
Reducción de la minimización
P µϕ = · · ·H− · · ·M : F (x1, . . . , xn) = mı́n
y∈N
˘
ϕ(x1, . . . , xn, y) = 0¯
M̂ : F̂ (x) = mı́ny∈N
˘
G(x, y) = 0¯
ˆ̂M :
ˆ̂F (x) = mı́n
z∈N
˘
H(z) = x¯
■ M̂ → ˆ̂M : Dada G hay que hallar F̂ .
F̂ (x) = τ 22 (
ˆ̂F (x + 1))
ˆ̂F (x + 1) = mı́n
z∈N
{
(τ2
1(z) + 1).(1−• G(τ2
1(z), τ2
2(z))) = x + 1
}
![Page 65: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/65.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 23
Reducción de la minimización
P µϕ = · · ·H− · · ·M : F (x1, . . . , xn) = mı́n
y∈N
˘
ϕ(x1, . . . , xn, y) = 0¯
M̂ : F̂ (x) = mı́ny∈N
˘
G(x, y) = 0¯
ˆ̂M :
ˆ̂F (x) = mı́n
z∈N
˘
H(z) = x¯
■ M̂ → ˆ̂M : Dada G hay que hallar F̂ .
F̂ (x) = τ 22 (
ˆ̂F (x + 1))
ˆ̂F (x + 1) = mı́n
z∈N
{
(τ2
1(z) + 1).(1−• G(τ2
1(z), τ2
2(z))) = x + 1
}
■ Si z = 〈x, y〉 entonces x = τ 21 (z), y = τ 2
2 (z)
G(x, y) 6= 0 =⇒ (x + 1).(1−• G(x, y)) = 0
G(x, y) = 0 =⇒ (x + 1).(1−• G(x, y)) = x + 1
![Page 66: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/66.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 23
Reducción de la minimización
P µϕ = · · ·H− · · ·M : F (x1, . . . , xn) = mı́n
y∈N
˘
ϕ(x1, . . . , xn, y) = 0¯
M̂ : F̂ (x) = mı́ny∈N
˘
G(x, y) = 0¯
ˆ̂M :
ˆ̂F (x) = mı́n
z∈N
˘
H(z) = x¯
■ M̂ → ˆ̂M : Dada G hay que hallar F̂ .
F̂ (x) = τ 22 (
ˆ̂F (x + 1))
ˆ̂F (x + 1) = mı́n
z∈N
{
(τ2
1(z) + 1).(1−• G(τ2
1(z), τ2
2(z))) = x + 1
}
■ Si z = 〈x, y〉 entonces x = τ 21 (z), y = τ 2
2 (z)
G(x, y) 6= 0 =⇒ (x + 1).(1−• G(x, y)) = 0
G(x, y) = 0 =⇒ (x + 1).(1−• G(x, y)) = x + 1
■ y mínima le corresponde z mínima por lapropiedad de monotonía: 〈x, y〉 < 〈x, y + 1〉
![Page 67: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/67.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 24
Bibliografía
■ Libros:◆ S. C. Kleene. Introduction to Metamathematics.◆ R. L. Goodstein. Recursive Number Theory.
![Page 68: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/68.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 24
Bibliografía
■ Libros:◆ S. C. Kleene. Introduction to Metamathematics.◆ R. L. Goodstein. Recursive Number Theory.
■ Artículos:◆ R. M. Robinson. Primitive Recursive Functions.◆ J. Robinson. General Recursive Functions.◆ M. D. Gladstone. Simplifications of the
Recursion Scheme.◆ N. Georgieva. Another Simplification of the
Recursion Scheme.
![Page 69: Reducción de los Esquemas de Recursión Tesina de Grado ...daniel/Slides.pdf · Funciones Unarias Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 4 Definición](https://reader033.vdocumento.com/reader033/viewer/2022042710/5f59bd8cd5084718d41a59d2/html5/thumbnails/69.jpg)
Introducción
Funciones Recursivas
Funciones Unarias
Funciones Unarias Primitivas
Algunas FUPsRepresentabilidad de FUPs con
FRPsRepresentabilidad de FRPs con
FUPsReducción de la Recursión
Primitiva
Funciones Unarias Generales
Reducción de la minimización
Bibliografía
Daniel E. Severin Reducción de los Esquemas de Recursión sn - p. 24
Bibliografía
■ Libros:◆ S. C. Kleene. Introduction to Metamathematics.◆ R. L. Goodstein. Recursive Number Theory.
■ Artículos:◆ R. M. Robinson. Primitive Recursive Functions.◆ J. Robinson. General Recursive Functions.◆ M. D. Gladstone. Simplifications of the
Recursion Scheme.◆ N. Georgieva. Another Simplification of the
Recursion Scheme.
■ Posteriormente:◆ D. E. Severin. Unary Primitive Recursive
Functions.