これを原始再帰関数の形式的定義となるよう変換すると、次のようになる:限定された減算関数は、この前者関数を使って定義される。ちょうど後者関数を使って加算が定義されるのと似ている:整数および有理数の演算.ゲーデル数を使うと、原始再帰関数を整数や有理数に拡張することができる。整数を標準的な方法でゲーデル数に符号化した場合、その算術演算である加算、減算、乗算は全て原始再帰的である。同様に有理数をゲーデル数で表した場合、体の演算は全て原始再帰的である。再帰関数との関係.限界.原始再帰関数は、計算可能関数とはどのようなものである筈か、という直観と密接に関連する。出発点となる原始再帰関数は(非常に単純なので)直観的に計算可能であり、そこから新たな原始再帰関数を作るための二種類の操作に関しても、具体的に関数値を計算する手続きを与えている。しかし、原始再帰関数の集合に全ての計算可能(全域)関数が含まれるわけではない。(この節の最後に列挙してある具体例を反例として示すことでも証明にはなるが、)カントールの対角線論法を応用して、原始再帰的でない計算可能関数が存在することを証明できる。証明の概略は次の通り:この論法は枚挙可能な(全域)計算可能関数の任意のクラスに適用できる。別記事()を参照のこと。ただし、部分計算可能関数は、例えばチューリングマシンでの符号化を使って番号付けするなどの方法で、明確に枚挙可能である。全域再帰的だが原始再帰的でない関数として、他にも次のような例が知られている:原始再帰関数の例.長与又郎原始帰納的関数火車(妖怪)火車/化車(かしゃ)は、悪行を積み重ねた末に死んだ者の亡骸を奪うとされる日本の妖怪である。概要.葬式や墓場から死体を奪う妖怪とされ、伝承地は特定されておらず、全国に事例がある。正体は猫の妖怪とされることが多く、年老いた猫がこの妖怪に変化するとも言われ、猫又が正体だともいう。昔話「猫檀家」などでも火車の話があり、播磨国(現・兵庫県)でも山崎町(現・宍粟市)牧谷の「火車婆」に類話がある。火車に類するもの.火車と同種のもの、または火車の別名と考えられているものに、以下のものがある。