{{TIN064 Skripta}}
Tato kapitola se věnuje zavedení a základním vlastnostem následujících tříd funkcí: částečně rekurzivní funkce (ČRF), obecně rekurzivní funkce (ORF) a primitivně rekurzivní funkce (PRF). Pokud tyto termíny slyšíte poprvé, doporučuji přečíst si nejprve <TIN064%20Úvod>.

## Induktivní výstavba funkcí ##

Funkce budeme konstruovat induktivně: zavedeme si tři základní funkce (nulová, následník, <#vydělení%20j-té%20složky>) a pak tři operátory (substituce, primitivní rekurze, minimalizace). Operátor je taková "metafunkce" — na vstupu dostane jednu či více funkcí a na výstupu vrátí nějakou novou funkci.

Ke každé funkci, kterou takto zkonstruujeme, pak bude existovat její **odvození**, což je posloupnost funkcí, z nichž každá je buď základní funkcí nebo vznikla z předchozích funkcí pomocí nějakého operátoru.

Pokud vám to připomíná induktivní výstavbu důkazů v logice, tak si můžete připsat malé nevýznamné plus. Ano, základní funkce jsou paralelou k axiomům, operátory jsou paralelou k odvozovacím pravidlům (modus ponens,...) a odvození funkce je paralelou k odvození důkazu.

* 
* 

### Základní funkce ###

#### nulová funkce ####

#### následník ####

#### vydělení j-té složky ####

### Operátory ###

#### substituce ####

* 

#### primitivní rekurze ####

* 
* 
* 

#### minimalizace ####

* 
* 
* 
* 
* 

## Definice ČRF, ORF, PRF ##

* 
* 
* 

* 
* 
* 

### Poznámky ###

* 
* 
* 

### Příklady ###

#### sčítání ####

#### odčítání ####

#### násobení ####

## Ostré inkluze ČRF, ORF, PRF ##

### neostré inkluze ###

### ČRF, která není ORF ###

### ORF, která není PRF ###

## Výpočetní síla TS a ČRF je ekvivalentní ##

### ČRF => TS (každá ČRF je turingovsky vyčíslitelná) ###

* 
* 
    * 
    * 
    * 

### TS => ČRF ###

## Numerace ČRF ##

* 
* 
* 
* 

### Standardní numerace ###

### Gödelova numerace ###

### Každé číslo odpovídá programu? ###

## Kleeneova věta ##

### Znění věty (Kleene, o normální formě, o univerzální funkci) ###

* 

* 

* 

* 

### Náznak důkazu ###

### Co znamená univerzální funkce? ###

### Co znamená predikát T? ###

* 
* 

### Co znamená $\mu_y$? ###

### Co znamená funkce $U$? ###

### Co říká s-m-n věta? ###

### Co mám říkat já? ###

## Univerzální PRF a ORF ##

### Neexistuje univerzální PRF pro třídu PRF ###

### Neexistuje univerzální ORF pro třídu ORF ###

* 
* 
* 
*