Takeuchi-funksjon

Den funksjonen Takeuchi , forkortet tak eller noen ganger Tarai presenterer rekursivt en funksjon som heter Ikuo Takeuchi (竹内郁雄). Presentasjonen av funksjonen, som dessuten innrømmer en ganske enkel ikke-rekursiv definisjon, kan kreve veldig lange beregninger hvis kompilatoren som implementerer den ikke er effektiv. Av denne grunn brukes det ofte til å teste ytelsen til implementeringen av rekursive funksjoner av kompilatoren av et programmeringsspråk .

Definisjon

Definisjonen av funksjonen tak gjøres rekursivt:

{\ displaystyle \ tau (x, y, z) = {\ begin {cases} \ tau (\ tau (x-1, y, z), \ tau (y-1, z, x), \ tau (z -1, x, y)) & {\ text {si}} y <x \\ y & {\ text {ellers}} \ end {cases}}}

Det kan defineres enklere og spesielt ikke rekursivt:

{\ displaystyle \ tau (x, y, z) = {\ begin {cases} y & {\ text {si}} x \ leq y \\ {\ begin {cases} z & {\ text {si}} y \ leq z \\ x & {\ text {ellers}} \ end {cases}} og {\ text {si}} x> y \ end {cases}}}

De første skrivene av funksjonen, nå referert til som tarai-funksjonen, ble skrevet og ga z tilbake i stedet for y , men vil bli endret i senere skrifter.

Se også

McCarthy-funksjon 91

Eksterne linker

(no) Wolfram
(no) TAK-funksjon