Bővebb ismertető
Részlet:Egyváltozós rekurzív függvényekAz egyváltozós rekurzív függvények egy jellemzését adjuk meg. Az érdekes, és a Church-tézissel - mármint hogy minden egyáltalán kiszámítható függvény rekurzív - összevetve különösen meglepő tétel Julia Robinsontól származik. Mivel kizárólag természetes számokon értelmezett függvényekkel foglalkozunk, ezt külön nem fogjuk hangsúlyozni.