Částečně rekurzivní funkce

Částečně rekurzivní funkce (ČRF) je termín, kterým se v teorii vyčíslitelnosti označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce.

Definice

Axiomy a operátory jsou stejné jako u primitivně rekurzivních funkcí. Třída ČRF je pak definovaná jako nejmenší třída funkcí, která obsahuje axiomy a je uzavřená na všechny tři operátory, tedy primitivní rekurzi, substituci i minimalizaci. Právě operátorem minimalizace se ČRF liší od PRF – zavádí totiž do výpočtu funkce potenciálně nekonečný cyklus.

Vlastnosti

  • částečně rekurzivní funkce nejsou obecně definovány pro každý vstup – pokud je např. hodnota f(x) nedefinována, říkáme, že funkce f v bodě x diverguje a píšeme obvykle
  • podmnožina všude definovaných ČRF se nazývá třída obecně rekurzivních funkcí (ORF) , také třída totálních rekurzivních funkcí či jen rekurzivních funkcí
  • platí, že PRF je vlastní podmnožinou ORF, a ta je vlastní podmnožinou ČRF
  • existuje tzv. univerzální částečně rekurzivní funkce, která kromě vlastních argumentů dostává ještě index ČRF (tzv. Gödelovo číslo), jejíž hodnotu při daných argumentech vyčísluje. Tato univerzální funkce je ve smyslu výpočetní síly ekvivalentní s Turingovým strojem

Příklady

Tyto funkce jsou částečně, ale ne primitivně rekurzivní:

  • Ackermannova funkce
  • univerzální částečně rekurzivní funkce (vzpomenutá výše)
  • libovolná ČRF, která je někde nedefinována

Read other articles:

Eva-Maria Liimets

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Eva-Maria Liimets Menteri Urusan Luar NegeriPetahanaMulai menjabat 26 Januari 2021Perdana MenteriKaja Kallas PendahuluUrmas ReinsaluPenggantiPetahanaDuta Besar Estonia untuk Republik Ceko, Slovenia dan KroasiaMasa jabatan2017–2021 Informasi prib...

 

Institut Teknologi Keling Kumang

Institut Teknologi Keling KumangNama lainITKKJenisSwastaDidirikan2020 (2020)AfiliasiYayasan Pendidikan Keling KumangLokasiSekadau, Kalimantan Barat, IndonesiaKampusUrbanSitus webwww.itkk.ac.id Institut Teknologi Keling Kumang adalah sebuah perguruan tinggi swasta di Kabupaten Sekadau, Provinsi Kalimantan Barat, Indonesia. ITKK diresmikan oleh Bupati Sekadau, Rupinus dengan melakukan penandatanganan prasasti pada 9 Januari 2021.[1] Institut Teknologi Keling Kumang memiliki 3 progr...

 

Massie Wireless Station

United States historic placeMassie Wireless StationU.S. National Register of Historic Places The station at its current locationShow map of Rhode IslandShow map of the United StatesLocation1300 Frenchtown RoadEast Greenwich, Rhode IslandCoordinates41°37′26.78″N 71°30′45.43″W / 41.6241056°N 71.5126194°W / 41.6241056; -71.5126194Built1907NRHP reference No.01001157 [1]Added to NRHPOctober 22, 2001 The Massie Wireless Station (PJ) was built i...

Hristo Yanev

Bulgarian footballer and manager Hristo Yanev Yanev in 2024 as Botev Vratsa managerPersonal informationFull name Hristo Angelov YanevDate of birth (1979-05-04) 4 May 1979 (age 44)Place of birth Kazanlak, BulgariaHeight 1.77 m (5 ft 9+1⁄2 in)Position(s) Midfielder, Second strikerTeam informationCurrent team Pirin Blagoevgrad (manager)Youth career Rozova DolinaSenior career*Years Team Apps (Gls)1997–1999 Olimpik Teteven 13 (1)1999–2000 Beroe Stara Zagora 27 (7)2000...

 

Fernbank Museum of Natural History

Natural history museum in Atlanta, Georgia, USA 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: Fernbank Museum of Natural History – news · newspapers · books · scholar · JSTOR (April 2018) (Learn how and when to remove this template message) Fernbank Museum of Natural HistoryEstablishedOctober 5, 1992Locati...

 

Resistenza ceca

Questa voce o sezione sull'argomento seconda guerra mondiale è ritenuta da controllare. Motivo: Valutare l'opportunità di ricomprendere nella trattazione anche le vicende slovacche e rinominare la voce in Resistenza cecoslovacca, come le corrispondenti voci di cs.wiki e de.wiki Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento. Una targa all'angolo del Palazzo Petschek commemora le vittime dell'Heydrichiáda La resistenza ceca è il movi...

The Pope's Toilet

2007 Uruguayan filmThe Pope's ToiletDirected byCésar Charlone Enrique FernandezWritten byCésar Charlone Enrique FernandezProduced byBel Berlinck Claudia Büschel Serge Catoire Fernando Meirelles Elena Roux Sandino Saravia VinayStarringCésar Troncoso Virginia Méndez Mario SilvaCinematographyCésar CharloneEdited byGustavo GianiMusic byLucianno SupervielleRelease date2007Running time90 minutesCountriesUruguay Brazil FranceLanguageSpanish The Pope's Toilet (Spanish: El Baño del Papa) is a ...

 

Martyrs de Belfiore

Lithographie : Giuseppe Boldrini, le peintre Boldrini, Angelo Giacomelli, Antonio Lazzati, et Francesco Montanari en prison à Mantoue en 1853 (Musée du Risorgimento à Milan) Les martyrs de Belfiore (la vallée de Belfiore est située au sud de la ville de Mantoue) est un épisode douloureux du Risorgimento italien connu pour sa série de condamnations à mort par pendaison exigées par le maréchal (Field-marshall) autrichien Joseph Radetzky, gouverneur général de Lombardie et de V�...

 

5th Cavalry Regiment

For other uses, see 5th Cavalry. 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: 5th Cavalry Regiment – news · newspapers · books · scholar · JSTOR (December 2012) (Learn how and when to remove this message) 5th Cavalry Regiment5th Cavalry Regiment coat of armsActive1861–CountryUnited States of AmericaBran...

Sulayman ibn Qutulmish

Sulayman ibn QutulmishMonumento dedicato a Sulayman ibn Qutulmish a Tarso, in Turchiasultano di RumIn carica1077 - 1086 PredecessoreQutulmish SuccessoreQilij Arslan I Altri titolisciàghazi Mortepressi di Antiochia, 1086 DinastiaSelgiuchidi PadreQutulmish ConsorteSeljuka Khatun Religionesunnismo Sulayman ibn Qutulmish, o Süleyman I (in arabo سليمان بن قتلمش‎?, Sulaymān ibn Qutulmish, o Qutalmish; ... – pressi di Antiochia, 1086), fondò uno Stato indipendente...

 

Harlequin cabbage bug

Species of true bug Not to be confused with harlequin beetle. Harlequin cabbage bug Adult (left) and nymph (right) Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Arthropoda Class: Insecta Order: Hemiptera Suborder: Heteroptera Family: Pentatomidae Genus: Murgantia Species: M. histrionica Binomial name Murgantia histrionica(Hahn, 1834) Aggregated nymphs The harlequin cabbage bug (Murgantia histrionica), also known as calico bug, fire bug or harlequin bug, is a black...

 

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

Clotilde Mollet

French actress Clotilde MolletMollet in 2009BornParis, FranceOccupationActressYears active1980–present Clotilde Mollet is a French actress.[1] Theatre Year Title Author Director Notes 1980 Deburau Sacha Guitry Jacques Rosny Théâtre Édouard VII 1983 Œil pour œil Jacques Audiard & Louis-Charles Sirjacq Louis-Charles Sirjacq Théâtre Gérard Philipe Cervantes intermèdes Miguel de Cervantes Jean Jourdheuil & Jean-François Peyret Festival d'Avignon 1984 Exquise Banqu...

 

Rathaus (U-Bahn Wina)

RathausLokasiInnere Stadt, WinaAustriaKoordinat48°12′37″N 16°21′19″E / 48.2104°N 16.3554°E / 48.2104; 16.3554Koordinat: 48°12′37″N 16°21′19″E / 48.2104°N 16.3554°E / 48.2104; 16.3554JalurSejarahDibuka1980Operasi layanan Stasiun sebelumnya   U-Bahn Wina   Stasiun berikutnya Volkstheatermenuju Karlsplatz Jalur U2Schottentormenuju Seestadt Sunting kotak info • L • BBantuan penggunaan templat ini Ratha...

 

أنثى

أنثىالشعارمعلومات عامةصنف فرعي من حقيقيات النوىكائن حي جزء من تكاثر جنسي ممثلة بـ أنثىالصبغي Yبويضة النقيض كائن ذكر تعديل - تعديل مصدري - تعديل ويكي بيانات الإناث (رمزه: ♀) (بالإنجليزية: Female)‏ هن جنس من كائن حي، أو جزء من الكائن الحي، التي تنتج البويضة غير المتنقلة (خلايا الب...

سفراء الولايات المتحدة لدى الكويت

سفير الولايات المتحدة لدى الكويت سفارة الولايات المتحدة الأمريكية في دولة الكويت سفراء الولايات المتحدة لدى الكويتشعار وزارة خارجية الولايات المتحدة شاغل المنصب ألينا رومانوسكي منذ 11 فبراير 2020 البلد الكويت الولايات المتحدة  عن المنصب المرشح رئيس الولايات المتحدة ال�...

 

قائمة البعثات الدبلوماسية في سلطنة عمان

خريطة البعثات الدبلوماسية في سلطنة عمان هذه قائمة بالبعثات الدبلوماسية في سلطنة عمان. توجد حاليًا 54 سفارة في مسقط، والعديد من الدول لها قنصليات في مدن عمانية أخرى (لا تشمل القنصليات الفخرية). السفارات في مسقط  أفغانستان  الجزائر  البحرين  بنغلاديش  البرازيل  ...

 

Samuel Bellamy

English pirate (1689–1717) For the English footballer, see Samuel Bellamy (footballer). Samuel BellamyBornc. (1689-02-23)23 February 1689Hittisleigh, Devon, Kingdom of EnglandDied26 April 1717 (1717-04-27) (aged 28)Wellfleet, Province of Massachusetts Bay, Thirteen ColoniesPiratical careerNicknameBlack Sam Bellamy,Prince of Pirates,Black Bellamy,Robin Hood of the SeaTypeGolden Age PirateYears active1716 – 26 April 1717RankElected Commodore of pirate fleetBase of operationsBlanco...

Pull-off

Stringed instrument playing technique G run in G major variation[1] Playⓘ contains both hammer-ons and a pull-off. A pull-off is a stringed instrument playing and articulation technique performed by plucking or pulling the finger that is grasping the sounding part of a string off the fingerboard of either a fretted or unfretted instrument. This intermediate- to advanced playing technique is done using the tip of a finger or fingernail on the fretting hand. Pull-offs are done to faci...

 

Greenhouse effect

Atmospheric phenomenon causing planetary warming This article is about the atmospheric phenomenon causing planetary warming. For the general heating or cooling of Earth's surface, see Earth's energy budget. For other uses, see Greenhouse (disambiguation). Energy flows down from the sun and up from the Earth and its atmosphere. When greenhouse gases absorb radiation emitted by Earth's surface, they prevent that radiation from escaping into space, causing surface temperatures to rise by about 3...