Zbiór rekurencyjny

Zbiór rekurencyjny – podzbiór $X\subseteq \mathbb {N}$ (zbioru liczb naturalnych), dla którego można skonstruować algorytm, który w skończonym czasie rozstrzyga, czy dana liczba należy do zbioru, czy też nie. Inne nazwy tego pojęcia to zbiór obliczalny oraz zbiór rozstrzygalny.

Własność ogólniejsza (słabsza) to bycie zbiorem rekurencyjnie przeliczalnym.

Definicje

Zbiór $X\subseteq \mathbb {N}$ jest zbiorem rekurencyjnym, jeśli istnieje funkcja rekurencyjna $f\colon \mathbb {N} \longrightarrow \mathbb {N}$ taka, że dla każdego $n\in \mathbb {N}$

f(n)=0

wtedy i tylko wtedy, gdy

n\in X

Zbiór $X\subseteq \mathbb {N}$ jest zbiorem rekurencyjnie przeliczalnym, jeśli istnieje funkcja rekurencyjna $f\colon \mathbb {N} \longrightarrow \mathbb {N}$ taka, że $X=\{f(n)\colon n\in \mathbb {N} \}.$

Przykłady

Następujące zbiory są rekurencyjne:

zbiór pusty
zbiór liczb naturalnych $\mathbb {N}$
każdy skończony podzbiór $\mathbb {N}$
zbiór liczb pierwszych

Podstawowe własności

Każdy zbiór rekurencyjny jest też zbiorem rekurencyjnie przeliczalnym.
Nieskończony zbiór rekurencyjnie przeliczalny musi zawierać nieskończony podzbiór rekurencyjny.
Istnieją zbiory rekurencyjnie przeliczalne, które nie są rekurencyjne.
Zbiór $X\subseteq {\mathbb {N} }$ jest rekurencyjny wtedy i tylko wtedy, gdy zarówno $X,$ jak i $\mathbb {N} \setminus X$ są rekurencyjnie przeliczalne.
Jeśli zbiory $X,Y\subseteq \mathbb {N}$ są rekurencyjne, to także zbiory $X\cap Y,X\cup Y$ oraz $\mathbb {N} \setminus X$ są rekurencyjne.

Read other articles:

Odense Boldklub

Odense BoldklubNama lengkapOdense BoldklubJulukanDe StribedeNama singkatOBBerdiri1887StadionFionia Park, Odense(Kapasitas: 15,761)KetuaNiels ThorborgManajer Lars OlsenLigaSuperliga Denmark2022–23ke-8 Kostum kandang Kostum tandang Odense Boldklub merupakan sebuah tim sepak bola Denmark yang bermai di divisi utama Superliga Denmark. Didirikan pada tahun 1887. Berbasis di Odense. Klub ini memainkan pertandingan kandangnya di Fionia Park yang berkapasitas 15.761 kursi. Seragam mereka berwarna b...

Night Bus

Night BusSutradaraEmil HeradiProduser Darius Sinathrya Teuku Rifnu Wikana Teuku Ryan Ditulis oleh Rahabi Mandra Teuku Rifnu Wikana BerdasarkanSelamat oleh Teuku Rifnu WikanaPemeran Rahael Ketsia Meijer Teuku Rifnu Wikana Yayu Unru Edward Akbar Hana Malasan Tio Pakusadewo Abdurrahman Arif Penata musikYovial Tri Purnomo VirgiSinematograferAnggi FriscaPenyunting Kelvin Nugroho Sentot Sahid Perusahaanproduksi Nightbus Pictures Kaninga Pictures Tanggal rilis6 April 2017Durasi139 menitNegara&...

Dieudonné

Pour les articles homonymes, voir Dieudonné (homonymie) et Mbala. Dieudonné Dieudonné en 2009. Données clés Nom de naissance Dieudonné M'Bala M'Bala Surnom Dieudo Naissance 11 février 1966 (58 ans)Fontenay-aux-Roses (Seine, France) Nationalité Française Profession HumoristeActeurMetteur en scèneProducteur de spectaclesGérant de théâtre Autres activités Militant politique Auteur de théâtre Réalisateur Scénariste Chanteur Écrivain Homme d'affaires modifier Dieudonné M'...

Saronen

Peniup saronen tampil dalam kelompok musik ul daul di Pamekasan Saronen adalah musik rakyat yang tumbuh berkembang di Madura. Harmonisasi yang dinamis, rancak, dan bertema keriangan dari bunyi yang dihasilkannya memang dipadukan dg karakteristik dan identitas masyarakat Madura yang tegas, polos, dan sangat terbuka mengilhami penciptanya. Nama Saronen meminjam nama alat musik tiup sejenis Serunai di kebudayaan Melayu, yang di kebudayaan Batak disebut Serune dan di Lombok disebut Sarone . Awal ...

List of Tolkien's alliterative verse

J. R. R. Tolkien (1892–1973), a scholar of Old English, Middle English, and Old Norse, used alliterative verse extensively in both translations and his own poetry. Most of his alliterative verse is in modern English, in a variety of styles, but he also composed some in Old English. Middle-earth mythos The Lord of the Rings Further information: Poetry in The Lord of the Rings § Alliterative verse There are numerous short alliterative verses in The Lord of the Rings (1954-1955). Most a...

Paul Leidy

American politician Paul LeidyMember of the U.S. House of Representativesfrom Pennsylvania's 12th districtIn officeDecember 7, 1857 – March 3, 1859Preceded byJohn G. MontgomerySucceeded byGeorge W. Scranton Personal detailsBorn(1813-11-13)November 13, 1813Hemlock Township, PennsylvaniaDiedSeptember 11, 1877(1877-09-11) (aged 63)Danville, PennsylvaniaPolitical partyDemocratic Paul Leidy (November 13, 1813 – September 11, 1877) was a Democratic member of the U.S. H...

Single Album

For the type of musical recording available in South Korea, see single album. 2021 studio album by NOFXSingle AlbumStudio album by NOFXReleasedFebruary 26, 2021Recorded2020StudioMotor, San Francisco, California[1]GenrePunk rock[2]Length36:19LabelFat Wreck ChordsProducer Bill Stevenson Jason Livermore NOFX chronology West Coast vs. Wessex(2020) Single Album(2021) Double Album(2022) Singles from Single Album LinewleumReleased: January 12, 2021[3] Single Album is ...

National Basketball Association 1960-1961

Questa voce o sezione sull'argomento competizioni cestistiche non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. National Basketball Association 1960-1961Dettagli della competizioneSport Pallacanestro OrganizzatoreNBA Periodo19 ottobre 1960 —11 aprile 1961 Squadre8 (in 2 gironi) VerdettiTitolo East Boston Celtics Titolo West St. Louis Hawk...

Ira Rodgers

American athlete and coach (1895–1963) Ira RodgersBiographical detailsBorn(1895-05-26)May 26, 1895Bethany, West Virginia, U.S.DiedFebruary 15, 1963(1963-02-15) (aged 67)Morgantown, West Virginia, U.S.Playing careerFootball1915–1917West Virginia1919West VirginiaBasketball1915–1919West VirginiaBaseball1916–1919West Virginia Position(s)Fullback, quarterback (football)Shortstop (baseball)Coaching career (HC unless noted)Football1920–1924West Virginia (assistant)1925–1930West Virg...

Shield (Archie Comics)

Character in Archie Comics Comics character The ShieldPep Comics #1 (January 1940) by Irv Novick.Publication informationPublisherMLJ/ArchieFirst appearanceHigginsPep Comics #1 (January 1940)BarnesLegend of Shield #13 (July 1992)AdamsThe Shield (vol. 5) #1 (October 2015)Created byHigginsHarry ShortenIrv NovickAdamsAdam Christopher (script)Chuck Wendig (script)David WilliamsIn-story informationAlter ego– Joe Higgins- Lt. Michael Barnes- Victoria AdamsTeam affiliationsMighty CrusadersAbilities...

Lambang Papua Selatan

Lambang Papua SelatanDetailDigunakan sejak2023Mottomaju negerikuVersi awalDesain pemenang sayembara oleh Ramdan Lambang Papua Selatan berbentuk perisai berwarna biru dengan tepi merah putih bertuliskan Papua Selatan. Unsur-unsur pada lambang ini terdiri dari bintang kuning, empat ujung anak panah berwarna coklat, berlian abu-abu, ujung tombak berwarna merah putih, padi dan kapas, daun sagu berwarna hijau kekuningan, akar pohon, dan kandara (tifa) bertuliskan motto Maju Negeriku.[1] Ma...

Dzhevdet Chakarov

Bulgarian politician (born 1960) Dzhevdet ChakarovДжевдет ЧакъровOfficial portrait, 2021Leader of the Movement for Rights and FreedomsIncumbentAssumed office 24 February 2024Serving with Delyan PeevskiPreceded byMustafa KaradayiMinister of Environment and WatersIn office17 August 2005 – 27 July 2009Prime MinisterSergey StanishevPreceded byDolores ArsenovaSucceeded byNona KaradzhovaMember of the National AssemblyIncumbentAssumed office 14 July 2009Const...

Golden Globe Award for Best Actress – Television Series Drama

Award presented annually by the Hollywood Foreign Press Association Golden Globe Award for Best Actress – Television Series DramaThe 2023 recipient: Sarah SnookAwarded forBest Performance by an Actress in a Television Series – DramaCountryUnited StatesPresented byHollywood Foreign Press AssociationFirst awardedMarch 5, 1962Currently held bySarah Snook, Succession (2023)Most awardsAngela Lansbury (4)Most nominationsAngela Lansbury (10)Websitegoldenglobes.org The Golden Globe Award for Best...

美輪明宏

画像提供依頼：現在の本人近影の画像提供をお願いします。（2021年4月）美輪明宏撮影時期不明（原典では1950年代とされる）基本情報出生名丸山臣吾（まるやましんご）（幼名）別名丸山明宏（まるやまあきひろ）（本名及び旧芸名）生誕 (1935-05-15) 1935年5月15日（89歳）出身地日本・長崎県長崎市学歴海星中学校ジャンルシャンソン職業シンガーソングライタ�...

Giessbach

Giessbach Les chutes de Giessbach. Caractéristiques Longueur 9,4 km Bassin 25,3 km2 Bassin collecteur Bassin du Rhin Cours · Localisation Chessel entre le Gärstenhorn et le Wildgärst · Altitude environ 2 505 m Confluence Aar · Localisation Lac de Brienz · Altitude 564 m · Coordonnées 46° 44′ 07″ N, 8° 01′ 14″ E Géographie Principaux affluents · Rive gauche Hagelseewlibach Pays traversés Suisse Cantons Berne modifier...

La Balme's Defeat

1780 battle between Canadien settlers and British-allied Miami warriors La Balme's DefeatPart of the American Revolutionary WarHistorical marker commemorating the battleDate5 November 1780LocationOhio CountryResult Miami victoryBelligerents Miami FranceCommanders and leaders Little Turtle La Balme †Strength Unknown 104 irregularsCasualties and losses 5 killed[1] 30-40 killedvteWestern theater Island Flats 1st Fort Henry Boonesborough Illinois Vincennes Fort Pitt Fort ...

Philip Latham

British actor (1929–2020) For the American science fiction writer, see Robert S. Richardson. Philip LathamBornCharles Philip Latham(1929-01-17)17 January 1929Essex, England[1][2]Died20 June 2020(2020-06-20) (aged 91)OccupationActorYears active1955–1990 Charles Philip Latham (17 January 1929 – 20 June 2020)[3][4][5][6] was a British actor. He was best known for playing Willy Izard in The Troubleshooters (1965-1972) and Plantagenet...

维基共享资源

若要了解如何在維基百科條目中插入維基共享資源的内容，可參見Wikipedia:維基共享資源。维基共享资源Wikimedia Commons网站类型媒体库持有者维基媒体基金会创始人维基媒体社群网址commons.wikimedia.org 商业性质否注册可选（上传文件时需要）推出时间2004年9月7日，19年前（2004-09-07）现状線上內容許可自由維基共享資源（英語：Wikimedia Commons，又称Commons）是...

Romance (genre littéraire)

Pour les articles homonymes, voir romance. The Black Moth, la première romance historique de Georgette Heyer Une romance est un type de roman d'amour développé dans certains pays anglophones, tels que les États-Unis, le Canada, le Royaume-Uni et l'Australie. Le terme est un anglicisme inspiré de « romance novel ». Considéré en France comme un genre mineur, peu étudié par les universitaires, ce type de roman se confond dans l'esprit du public et des médias francophones a...

Казахстан на летних Олимпийских играх 2008

Казахстан на Олимпийских играх Код МОК KAZ НОК Национальный олимпийский комитет Республики Казахстан Олимпийские игры в Пекине Спортсмены 132 в 18 видах спорта Знаменосец Бахыт Ахметов МедалиМесто 29 Золото Серебро Бронза Всего 2 3 4 9 Участие в летних Олимпийских �...