Funció recursiva

En lògica matemàtica i computació, les funcions recursives o també conegudes com a funcions recursives-μ són una classe de funcions dels nombres naturals en els nombres naturals que són "computables" en un sentit intuïtiu. De fet, en teoria de la computabilitat es demostra que les funcions recursives són precisament les funcions que poden ser calculades amb el formalisme de còmput més general conegut com són les màquines de Turing. Les funcions recursives estan relacionades amb les funcions primitives recursives i la seva definició inductiva es construeix basant-se en les funcions primitives recursives. No tota funció recursiva és primitiva recursiva. L'exemple més conegut és la funció d'Ackermann.

Existeixen altres sistemes formals equivalents quant a poder d'expressió, per exemple, el càlcul lambda i les cadenes de Markov.

Definició

Per definir les funcions recursives es pren la definició de les funcions primitives recursives, per permetre funcions parcials, agregant l'operador de cerca o minimització no acotada com segueix:

f(x,z_{1},z_{2},...,z_{n})

és una funció parcial sobre els naturals amb

n+1

arguments

x,z_{1},z_{2},...z_{n}

, la funció μx f és la funció parcial amb arguments

z_{1},...,z_{n}

que retorna el més petit

x

tal que

f(0,z_{1},z_{2},...,z_{n}),f(1,z_{1},z_{2},...,z_{n}),...,f(x,z_{1},z_{2},...,z_{n})

estan totes definidies i

f(x,z_{1},z_{2},...,z_{n})=0

, si un tal

x

existeix, en cas contrari μx f no està definida pels valors particulars dels arguments

z_{1},z_{2},...,z_{n}

Es pot verificar que l'especificació del mínim valor de x, junt amb la resta de la definició idèntica a les funcions primitives recursives, impliquen l'axioma de cerca acotada de les funcions primitives recursives.

El conjunt de les funcions recursives parcials està definit com el més petit conjunt de funcions parcials amb qualsevol nombre d'arguments dels naturals en els naturals que contenen el zero, el successor i les funcions de projecció, tals que la composició, la recursió primitiva i la cerca no acotada són operacions tancades d'aquest conjunt.

El conjunt de les funcions recursives totals és el subconjunt de les funcions recursives parcials que a més són funcions totals.

En la tesi de Church-Turing s'estableix el paral·lelisme entre màquina de Turing que no s'atura per certes entrades i el resultat indefinit d'una funció recursiva parcial. L'operador de cerca no acotada no pot ser definit usant les regles de definició de les funcions primitives recursives, ja que no es disposa en elles d'un mecanisme d'iteració no acotada pel qual podria no trobar-se el resultat d'una funció.

Read other articles:

Nine (TV series)

This article is about the South Korean TV show. For other uses, see 9 (disambiguation). South Korean TV series or program NinePromotional posterAlso known as9 Nine: Time Traveling Nine TimesGenreRomance Time travel MysteryWritten bySong Jae-jung Kim Yoon-jooDirected byKim Byung-sooStarringLee Jin-wookJo Yoon-heeComposerNam Hye-seungCountry of originSouth KoreaOriginal languageKoreanNo. of episodes20ProductionExecutive producersKim Young-gyuLee Jin-suk [ko]Choi Young-gunProducersL...

Keuskupan Agung Gitega

Keuskupan Agung GitegaArchidioecesis Kitegaensis[1]Katolik Katedral Kristus RajaLokasiNegara BurundiProvinsi gerejawiProvinsi gerejawi Gitega, BurundiInformasiDenominasiKatolik RomaRitusRitus RomaKatedralKatedral Kristus Raja[2]Kepemimpinan kiniPausFransiskusUskup AgungSimon Ntamwana[3] Keuskupan Agung Gitega adalah tahta Metropolitan untuk provinsi gerejawi Gitega di Burundi. Keuskupan Suffragan Keuskupan Muyinga Keuskupan Ngozi Keuskupan Rutana Keuskupan Ru...

Agrilus trepanatus

Agrilus trepanatus Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Buprestidae Genus: Agrilus Spesies: Agrilus trepanatus Nama binomial Agrilus trepanatusJendek, 2013 Agrilus trepanatus adalah spesies kumbang yang tergolong ke dalam famili Buprestidae. Spesies ini juga merupakan bagian dari ordo Coleoptera. Spesies Agrilus trepanatus sendiri merupakan bagian dari genus Agrilus yang mencakup sekitar 3.000 spesies.[1] Nama ilmiah dari spe...

Abraham J. Williams

American politician (1781–1839) Abraham J. Williams3rd Governor of MissouriIn officeAugust 4, 1825 – January 20, 1826LieutenantVacantPreceded byFrederick BatesSucceeded byJohn MillerMember of the Missouri SenateIn office1822 Personal detailsBorn(1781-02-26)February 26, 1781Hardy County, VirginiaDiedDecember 30, 1839(1839-12-30) (aged 58)Boone County, MissouriPolitical partyDemocratic-Republican,OccupationMerchant, farmer Abraham Jude[citation needed] Williams (Februa...

Коэффициент теплового расширения

Коэффициент теплового расширения β = 1 V ( d V d T ) p {\displaystyle \beta ={\frac {1}{V}}\left({\frac {dV}{dT}}\right)_{p}} Размерность Θ−1 Единицы измерения СИ К−1 СГС К−1 Коэффицие́нт теплово́го расшире́ния — физическая величина, характеризующая относительное изменение объёма или линейных размер�...

العلاقات اليابانية الجنوب سودانية

العلاقات اليابانية الجنوب سودانية اليابان جنوب السودان اليابان جنوب السودان تعديل مصدري - تعديل العلاقات اليابانية الجنوب سودانية هي العلاقات الثنائية التي تجمع بين اليابان وجنوب السودان.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة...

Tiamat (Dungeons & Dragons)

Dragon deity from Dungeons & Dragons This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may contain an excessive amount of intricate detail that may interest only a particular audience. Please help by spinning off or relocating any relevant information, and removing excessive detail that may be against Wikipedia's inclusion policy. (December 2022) (Learn how and when to remo...

Iisaku

Borough in Estonia Place in Ida-Viru County, EstoniaIisakuView of IisakuIisakuCoordinates: 59°06′02″N 27°18′37″E / 59.10056°N 27.31028°E / 59.10056; 27.31028CountryEstoniaCountyIda-Viru CountyPopulation (2011 Census[1]) • Total761Time zoneUTC+2 (EET) Iisaku is a small borough (alevik) in northeastern Estonia. It is located in Ida-Viru county in Alutaguse Parish, around 30 km south from the town of Jõhvi. Iisaku was the adminis...

Contea di Richland (Wisconsin)

Questa voce sull'argomento contee del Wisconsin è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Contea di RichlandconteaLocalizzazioneStato Stati Uniti Stato federato Wisconsin AmministrazioneCapoluogoRichland Center Data di istituzione1842 TerritorioCoordinatedel capoluogo43°20′05″N 90°23′12″W / 43.334722°N 90.386667°W43.334722; -90.386667 (Contea di Richland)Coordinate: 43°20′05″N 90°23′12″W ...

Auburn, California

City in California, United States City in California, United StatesAuburn, CaliforniaCityCity of AuburnAuburnLocation of Auburn in Placer County, CaliforniaAuburnLocation in CaliforniaShow map of CaliforniaAuburnAuburn (the United States)Show map of the United StatesAuburnAuburn (North America)Show map of North AmericaCoordinates: 38°53′55″N 121°4′28″W / 38.89861°N 121.07444°W / 38.89861; -121.07444CountryUnited StatesStateCaliforniaCountyPlacerIncorporated...

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日土库曼斯坦土库曼斯坦政府与政治国家政府土库曼斯坦宪法国旗国徽国歌立法機關（英语：National Council of Turkmenistan） ...

Larmier (architecture)

Cet article est une ébauche concernant l’architecture ou l’urbanisme. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir larmier. Larmier du pigeonnier de Richemont, XVIe siècle. Larmier du pigeonnier du château de Neuvicq. Bec de larmier. Le larmier, également appelé coupe-larme, est la partie saillante transversale basse de la charpente d'une corniche, d'un bandeau ...

Neville Hill TMD

Train Maintenance Depot in West Yorkshire, England Neville Hill TMDNeville Hill depotLocationLocationLeeds, EnglandCoordinates53°47′32″N 1°30′18″W / 53.7923°N 1.5051°W / 53.7923; -1.5051OS gridSE325330CharacteristicsOwnerNetwork RailOperatorNorthern TrainsDepot code50B (1948–1960)[1]55H (1960–1973)[1]NL (1973–present)[1]TypeDiesel, HST, DMU, EMUHistoryOpened1904OriginalNorth Eastern RailwayPost-groupingLNER Neville Hill is a ra...

لجنة التحقيق الأنجلو أمريكية

تقرير لجنة التحقيق الأنجلو أمريكية بشأن مشاكل يهود أوروبا وفلسطين التقرير، الورق الاعتمادي 6808 صياغة 20 نيسان (أبريل) 1946 الموقع لوزان الغرض تقديم توصيات لحل دائم لمشاكل الهجرة اليهودية في فلسطين تعديل مصدري - تعديل لجنة التحقيق الأنجلو أمريكية (بالإنجليزية: Anglo-American Committ...

بانثيون

تحتاج النصوص المترجمة في هذه المقالة إلى مراجعة لضمان معلوماتها وإسنادها وأسلوبها ومصطلحاتها ووضوحها للقارئ، لأنها تشمل ترجمة اقتراضية أو غير سليمة. فضلاً ساهم في تطوير هذه المقالة بمراجعة النصوص وإعادة صياغتها بما يتناسب مع دليل الأسلوب في ويكيبيديا.الدولة إيطاليا �...

Weitbruch

Weitbruch Vue de l'entrée sud de Weitbruch, rue de Brumath. Blason Administration Pays France Région Grand Est Collectivité territoriale Collectivité européenne d'Alsace Circonscription départementale Bas-Rhin Arrondissement Haguenau-Wissembourg Intercommunalité Communauté de communes de la Basse-Zorn Maire Mandat Damien Henrion 2020-2026 Code postal 67500 Code commune 67523 Démographie Gentilé Weitbruchois Populationmunicipale 2 719 hab. (2021 ) Densité 180 hab./km...

Love's Contagious

Not to be confused with Love Is Contagious. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Love's Contagious – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message) 1991 single by George LamondLove's ContagiousSingle by George Lamondfrom the album Bad of the...

Pesta riung

Tarian lima pasangan di Riungan Kolonial di Albert Hall Canberra (sekitar 2016) ( sepia ) Pesta riung atau tari riungan (bahasa Inggris: ballroom dance) adalah pesta dansa formal yang sering ditandai dengan perjamuan diikuti dengan tarian sosial yang mencakup dansa balai riung. Tarian riung muncul dari tarian formal selama Abad Pertengahan dan dilakukan melalui iterasi yang berbeda selama abad-abad berikutnya, seperti tarian Barok abad ke-17 dan cotillion abad ke-18. Ada beberapa variasi...

تجمع بدو الرحيبة (غيل باوزير)

' تجمع بدو الرحيبة - قرية - تقسيم إداري البلد اليمن المحافظة محافظة حضرموت المديرية مديرية غيل باوزير العزلة عزلة غيل باوزير السكان التعداد السكاني 2004 السكان 57 • الذكور 30 • الإناث 27 • عدد الأسر 8 • عدد المساكن 8 معلومات أخرى التوقيت توقيت اليمن...

List of conservation areas in Bournemouth, Christchurch and Poole

As of January 2023, there are 48 Conservation Areas in the Bournemouth, Christchurch and Poole, in Dorset, England.[1] Conservation areas Name Image Area Year Notes Refs Ashington Poole 2002 Historic hamlet in the green belt north of Poole [2] Ashley Cross Poole 1987, amended June 2012 Victorian suburb of Parkstone [3] Avon Buildings Christchurch 1991 Suburb of Christchurch Boscombe Manor Bournemouth 1993 Shelley Manor, Shelley Manor, St Andrew's Church [4] Bo...