Ensemble récursif

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique.

En d'autres termes, un ensemble $E$ est récursif si, et seulement si, il existe une machine de Turing $T$ (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans $E$ ou pas^[1].

\forall n\in \mathbb {N}

T(n)=OUI\ {\mbox{si}}\ n\in E

T(n)=NON\ {\mbox{si}}\ n\notin E

Ce type d'ensemble correspond à un concept effectif de John R. Myhill, qui sont les concepts qui peuvent être définis extensivement et sans ambiguïté. La notion d'ensemble récursivement énumérable (non récursif) est plutôt un concept constructif, dont le contenu se précise et se comprend de mieux en mieux avec le temps, sans qu'il soit jamais possible de le cerner complètement^[1].

Définition en termes de système formel

Dans la terminologie des systèmes formels, la définition suivante est équivalente^[1] :

E

est récursif si et seulement si il existe un système formel correct et complet pour les énoncés de la forme « $n$ est dans $E$ » et de la forme « $n$ n'est pas dans $E$ ».

Propriétés

Un ensemble A est récursif si et seulement si A et son complémentaire sont récursivement énumérables.
Si A et B sont récursifs, alors A ∩ B et A ∪ B sont récursifs.

Exemples

Les ensembles suivants sont récursifs :

tout ensemble fini (l'ensemble vide ∅ étant un exemple trivial) ;
l'ensemble des multiples d'un entier $k$ (les nombres entiers, les nombres pairs, etc.) ;
l'ensemble des nombres premiers ;
l'ensemble des solutions d'une équation diophantienne donnée.

Les ensembles suivants sont récursivement énumérables mais pas récursifs :

l'ensemble des équations diophantiennes qui ont une solution entière ;
l'ensemble des programmes qui s'arrêtent (les programmes qui ne tournent pas indéfiniment) : voir « Problème de l'arrêt ».

On ne sait actuellement toujours pas si le multiensemble des termes de la suite de Syracuse de terme initial $u_{0}=k$ est récursif pour $k>0$ quelconque (sous-entendu : $k$ entier). La conjecture de Syracuse prétend le contraire, mais reste encore à ce jour indémontrée. En revanche, il est récursivement énumérable par définition.

Notes et références

↑ ^{a b et c} Jean-Paul Delahaye, Information, Complexité et Hasard, Hermes Science Publishing, 1999 (ISBN 2-7462-0026-0). p. 74.

Voir aussi

Lien externe

Cours sur la récursivité

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique

Portail de l'informatique théorique

Read other articles:

Direktorat Festival Film

Direktorat Festival FilmTanggal pendirian1973TipeBadan PemerintahanTujuanUntuk menyelenggarakan Festival Film Nasional dan Internasional di IndiaKantor pusatKompleks Auditorium Benteng Siri, New DelhiWilayah layanan IndiaSutradaraRajeev Kumar JainOrganisasi indukKementerian Informasi dan PenyiaranSitus webwww.dff.nic.in Direktorat Festival Film di India adalah sebuah organisasi yang menyelenggarakan dan mempersembahkan Festival Film Internasional India, Penghargaan Film Nasional dan Panorama ...

Daftar tokoh Cilacap

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 Desember 2022. Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber...

Холокост на Украине

Часть серии статей о Холокосте Идеология и политика Расовая гигиена · Расовый антисемитизм · Нацистская расовая политика · Нюрнбергские расовые законы Шоа Лагеря смерти Белжец · Дахау · Майданек · Малый Тростенец · Маутхаузен ·&...

Doc Savage: The Man of Bronze

1975 film by Michael Anderson Doc Savage: The Man of BronzeFilm poster by Roger KastelDirected byMichael AndersonWritten byJoe MorhaimGeorge PalBased onThe Man of Bronze1933 novelby Kenneth RobesonProduced byGeorge PalStarringRon ElyNarrated byPaul FreesCinematographyFred J. KoenekampEdited byThomas J. McCarthyMusic byDon BlackFrank De VolJohn Philip SousaDistributed byWarner Bros.Release date June 1975 (1975-06) Running time112 minutesCountryUnited StatesLanguageEnglish Doc Sa...

Scale model

Physical representation of an object 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: Scale model – news · newspapers · books · scholar · JSTOR (July 2022) (Learn how and when to remove this template message) A scale model of the Tower of London. This model can be found inside the tower. A scale model of a hy...

Politeknik Negeri Cilacap

Politeknik Negeri CilacapState Polytechnic of CilacapMotoBuilding Skill For The FutureJenisPerguruan Tinggi Negeri, PoliteknikDidirikan 8 Juli 2008 (sebagai Politeknik Cilacap) 6 Oktober 2014 (sebagai Politeknik Negeri Cilacap) Lembaga indukKementerian Pendidikan, Kebudayaan, Riset, dan TeknologiDirekturRiyadi Purwanto, S.T., M.Eng.Jumlah mahasiswa1306 (tahun 2022)[1]Alamat Jl. Dr. Soetomo No.1, Sidakaya, Kabupaten Cilacap, Jawa Tengah, 53212, IndonesiaWarna BiruNama julukanPNCS...

2014 United States House of Representatives elections in Washington

House elections for the 114th U.S. Congress 2014 United States House of Representatives elections in Washington ← 2012 November 4, 2014 (2014-11-04) 2016 → All 10 Washington seats to the United States House of Representatives Majority party Minority party Party Democratic Republican Last election 6 4 Seats won 6 4 Seat change Popular vote 1,047,747 981,853 Percentage 51.62% 48.38% Swing 2.82% 2.82% Democratic 5...

Handcrafts and folk art in Hidalgo

Handcraft vendors in El Arenal, Hidalgo Hidalgo (state) handcrafts and folk art are mostly made for local consumption rather than for collectors, although there have been efforts to promote this work to a wider market. Most are utilitarian and generally simply decorated, if decorated at all. The most important handcraft traditions are pottery, especially in the municipality of Huejutla and textiles, which can be found in diverse parts of the state. Most artisans are indigenous, with the Otomi...

Daftar episode Ben 10: Ultimate Alien

Berikut daftar episode serial Ben 10: Ultimate Alien, kelanjutan dari Ben 10 & Ben 10: Alien Force yang pertama kali ditayangkan di Amerika Serikat oleh Cartoon Network. Season 1 Fame Duped ( spesial episode ke - 100 dari Ben 10, & Ben 10: Alien Force ) Hit 'Em Where They Live Video Games Escape from Aggregor Too Hot to Handle Andreas' Fault Fused Hero Time Ultimate Aggregor Map of Infinity Reflected Glory Deep Where the Magic Happens Perplexahedron The Forge of Creation ...Nor Iron ...

Less than Zero (soundtrack)

1987 soundtrack album by various artistsLess Than Zero (Original Motion Picture Soundtrack)Soundtrack album by various artistsReleasedNovember 6, 1987Recorded1987GenreRockpop rockhip hopR&Bheavy metalLength41:28LabelDef JamColumbiaProducerChuck DEric Vietnam SadlerFrederick GordonHank ShockleeRick RubinRussell SimmonsVincent BellAerosmith (co.)Singles from Less Than Zero Rock and Roll All NiteReleased: October 12, 1987 Hazy Shade of WinterReleased: November 1987 Going Back to Cali...

Emergentism

Philosophical belief in emergence Emergentism is the belief in emergence, particularly as it involves consciousness and the philosophy of mind. A property of a system is said to be emergent if it is a new outcome of some other properties of the system and their interaction, while it is itself different from them.[1] Within the philosophy of science, emergentism is analyzed both as it contrasts with and parallels reductionism.[1][2] Forms Emergentism can be compatible w...

John Patitucci

American jazz bassist and composer John PatitucciJohn Patitucci at the 2018 Kongsberg JazzfestivalBackground informationBirth nameJohn James PatitucciBorn (1959-12-22) December 22, 1959 (age 64)Brooklyn, New York, U.S.GenresJazz, jazz fusionOccupation(s)Musician, composerInstrument(s)Double bass, bass guitarYears active1980–presentLabelsGRP, Stretch, Concord JazzWebsitejohnpatitucci.comMusical artist John Patitucci (born December 22, 1959) is an American jazz bassist and composer. Biog...

Marine marchande

Le terme marine marchande ou marine de commerce désigne tous les moyens de transport maritime de marchandises. On y inclut parfois le transport commercial de personnes. Au début du XXIe siècle, le commerce mondial de marchandises s'effectue à près de 95 % par la voie maritime et il se développe rapidement : il existait environ 50 000 navires de commerce en service dans le monde en 2009, près de 80 000 en 2019 et 99.800 au 1er janvier 2021[1]. Ces navires, en 20...

Азиатский барсук

Азиатский барсук Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКласс:Мле�...

1900年美國總統選舉

1900年美國總統選舉 ← 1896 1900年11月6日 1904 → 447張選舉人票獲勝需224張選舉人票投票率73.2%[1] ▼ 6.1 % 获提名人威廉·麥金利威廉·詹寧斯·布賴恩政党共和黨民主党家鄉州俄亥俄州內布拉斯加州竞选搭档西奧多·羅斯福阿德萊·史蒂文森一世选举人票 292 155 胜出州/省 28 17 民選得票 7,228,864 6,370,932 得票率 51.6% 45.5% 總統選舉結果地圖，紅色代表�...

Clinton Anderson

American politician (1895–1975) This article is about the American politician. For the horse trainer, see Clinton Anderson (horse trainer). Clinton AndersonOfficial portrait, c. 1945United States Senatorfrom New MexicoIn officeJanuary 3, 1949 – January 3, 1973Preceded byCarl HatchSucceeded byPete Domenici13th United States Secretary of AgricultureIn officeJune 30, 1945 – May 10, 1948PresidentHarry S. TrumanPreceded byClaude R. WickardSucceeded byCharles F. Br...

Senate of Liberia

Upper house of Liberian legislature 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: Senate of Liberia – news · newspapers · books · scholar · JSTOR (July 2019) (Learn how and when to remove this message) Senate55rd Liberian LegislatureTypeTypeUpper house Term limitsUnlimited 9-year termsLeadershipPresident o...

Donohudan, Ngemplak, Boyolali

DonohudanDesaKantor Desa DonohudanPeta lokasi Desa DonohudanNegara IndonesiaProvinsiJawa TengahKabupatenBoyolaliKecamatanNgemplakKode pos57375Kode Kemendagri33.09.11.2005 Luas2,45 km²Jumlah penduduk7.800 jiwaKepadatan3.160 jiwa/km² Donohudan adalah desa di kecamatan Ngemplak, Boyolali, Jawa Tengah, Indonesia. Di desa ini terdapat Asrama Haji Donohudan yang digunakan untuk para jamaah haji dari Embarkasi Surakarta. Pembagian wilayah Asrama Haji Donohudan Desa ini terdiri dari empat wila...

Europa (rocket)

Rocket family 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: Europa rocket – news · newspapers · books · scholar · JSTOR (December 2014) (Learn how and when to remove this message) EuropaEuropa II rocket at Euro Space CenterFunctionOrbital carrier rocketManufacturerELDOSizeHeight33 m (108 ft)...

Colonia romana

Una colonia romana (latino: colonia) era una comunità autonoma, situata in un territorio conquistato da Roma in cui si erano stanziati dei cittadini romani e/o latini, legata da vincoli di eterna alleanza con la madrepatria. Con la definizione di colonia romana si intende sia le sole colonie di diritto romano, sia in senso più ampio, ogni tipo di colonia. La locuzione deduzione di una colonia (in latino: deductio) indica la fondazione di una colonia romana e l'invio di coloni romani da inse...

PROFILPELAJAR.COM