재귀 열거 언어

재귀적 열거 가능 언어(再歸的列擧可能言語, 영어: Recursively enumerable language, 귀납적 가산 언어(歸納的可算言語)), 부분 결정성 언어 또는 튜링 수리성 언어는 계산 이론과 수리논리학에서 다루는 형식 언어의 종류로, 문자열의 집합의 재귀 열거인 부분집합이다. 촘스키 위계의 type-0 언어이기도 하다. 재귀 열거 언어의 모임을 RE라고 한다.

정의

재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다.

  1. 재귀 열거 언어는 언어의 문자로 만들 수 있는 재귀 열거 집합의 부분집합이다.
  2. 재귀 열거 언어는 언어의 모든 옳은 문자열을 세는 튜링 기계 (또는 다른 계산 가능 함수)가 존재하는 형식언어이다. 주목할 것은 만약 언어가 무한하다면 제공된 가산알고리듬을 고를 수 있어 반복을 피할 수 있는데 우리가 숫자 n으로 산출된 문자열이 이미 더 작은 숫자 n에서 산출됐는지 확인할 수 있기 때문이다. 만약 이미 산출된 결과라면, 출력을 입력 n+1으로 대신 (귀납적으로)사용하지만, 반복해서 새로운지 확인이 필요하다.
  3. 재귀 열거 언어는 어떤 언어의 문자열이 입력으로 주어질때 서고 승인하지만 언어에 속하지 않은 문자열이 주어질때 정지하고 거절하는 튜링 기계 (또는 다른 계산 가능 함수)이 존재하는 형식언어이다. 튜링머신이 정지하는 필요한 모든 경우에 이것을 재귀 언어와 대조한다.

모든 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 재귀 언어는 재귀 열거 언어이다.

RE, 그것의 보완물 co-RE는 산술적 위계의 기반이 되고 있다.

닫힘특성

재귀 열거 언어는 다음 과정에 대해 닫혀있다. 만약 L 과 P 가 재귀 열거 언어라면 다음의 언어는 재귀 열거 언어이다.

  • L의 클레이니 스타(Kleene star):
  • L과P의 연결:
  • L과P의 합집합:
  • L과P의 교집합:

주목할 것은 재귀 열거 언어는 차집합이나 여집합에서는 닫혀있지 않다는 것이다. 차집합 L\P는 재귀 열거 언어일 수도 아닐 수도 있다. 만약 L이 재귀 열거 언어라면, L의 여집합은 재귀 열거 언어인 경우에만 L이 또한 귀납적이다.

같이 보기

Read other articles:

Corby Town F.C.

Association football club in Corby, England Football clubCorby TownFull nameCorby Town Football ClubNickname(s)The SteelmenFounded1948GroundSteel Park, CorbyCapacity3,893 (577 seated)[1]ChairmanStevie NobleManagerGary SetchellLeagueNorthern Premier League Division One Midlands2022–23Northern Premier League Division One Midlands, 7th of 20WebsiteClub website Home colours Away colours Corby Town Football Club is a football club based in Corby, Northamptonshire, England. They are curre...

 

Engineering ethics

Moral principles within the field of engineering Engineering ethics is the field of system of moral principles that apply to the practice of engineering. The field examines and sets the obligations by engineers to society, to their clients, and to the profession. As a scholarly discipline, it is closely related to subjects such as the philosophy of science, the philosophy of engineering, and the ethics of technology. Background and origins Up to the 19th century and growing concerns The first...

 

Irang Arkad

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Irang ArkadLahirIrang Perdana Arkad3 Januari 1971 (umur 53)SurabayaPekerjaanVokalKarier musikGenreRockInstrumenVokalTahun aktif1996–sekaran...

وزارة التربية الوطنية (فرنسا)

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

 

Debbie Stabenow

Debbie Stabenow Portrait officiel de Debbie Stabenow (2019). Fonctions Sénatrice des États-Unis En fonction depuis le 3 janvier 2001(23 ans, 3 mois et 10 jours) Élection 7 novembre 2000 Réélection 7 novembre 20066 novembre 20126 novembre 2018 Circonscription Michigan Législature 107e, 108e, 109e, 110e, 111e, 112e, 113e, 114e, 115e, 116e, 117e et 118e Groupe politique Démocrate Prédécesseur Spencer Abraham Représentante des États-Unis 3 janvier 1997 – 3 janvier 200...

 

Синелобый амазон

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

Kumail Nanjiani

Pakistani-American comedian and actor (born 1978) Kumail NanjianiNanjiani at the 2019 San Diego Comic-ConBornKumail Ali Nanjiani (1978-05-02) May 2, 1978 (age 46)Karachi, Sindh, PakistanCitizenshipPakistanUnited StatesEducationGrinnell College (BA)OccupationsComedianactorYears active2007–presentSpouse Emily V. Gordon ​(m. 2007)​RelativesShereen Nanjiani (second cousin) Kumail Ali Nanjiani[1] (/kʊˈmeɪl ˌnɑːndʒiˈɑːni/;[2] Sindhi...

 

Mowad

Mowadbandar kota (kerajaan tempatan)Peta India. BenderaNegaraIndiaNegara bagianMaharashtraDistrikNagpurbandar kota (kerajaan tempatan)MowadPopulasi (2001) • Total8.732 • Melek huruf6.431 (3.528 lelaki 2.903 perempuan) • Jenis kelamin55% lelaki dan 45% perempuanZona waktuGMT • Musim panas (DST)GMTbawah 6 tahun1078 (2001) Mowad adalah sebuah bandar kota (kerajaan tempatan) yang terletak di Distrik Nagpur di negara bagian Maharashtra, India. D...

 

1980 United States Senate election in South Dakota

1980 United States Senate election in South Dakota ← 1974 November 4, 1980 1986 →   Nominee James Abdnor George McGovern Party Republican Democratic Popular vote 190,594 129,018 Percentage 58.20% 39.40% County results Abdnor:      40-50%      50-60%      60-70%      70-80%      80-90% McGovern:      50–60% ...

MBS International Airport

Airport in Freeland, Michigan MBS International AirportIATA: MBSICAO: KMBSFAA LID: MBSSummaryAirport typePublicOwnerBay County, Michigan,Midland, Michigan,Saginaw, MichiganServesSaginaw, MichiganMidland, MichiganBay City, MichiganLocationFreeland, MI, United StatesElevation AMSL668 ft / 204 mCoordinates43°31′58″N 084°04′47″W / 43.53278°N 84.07972°W / 43.53278; -84.07972Websitewww.mbsairport.orgMapMBSLocation of airport in MichiganShow map of ...

 

Belgian Pro League

Football league in Belgium Football leagueBelgian Pro LeagueFounded1895; 129 years ago (1895)CountryBelgiumConfederationUEFANumber of teams16Level on pyramid1Relegation toChallenger Pro LeagueDomestic cup(s)Belgian Cup Belgian Super CupInternational cup(s)UEFA Champions LeagueUEFA Europa LeagueUEFA Conference LeagueCurrent championsClub Brugge (19th title) (2023–24)Most championshipsAnderlecht (34 titles)Most appearancesJan Ceulemans (517)Top goalscorerAlbert De Cleyn (377...

 

Tushpa

Ruined capital city of Urartu For the modern district in the Van Province, see Tuşba. TushpaThe citadel of Van and the ruins of Tushpa belowShown within TurkeyLocationTurkeyRegionVan ProvinceCoordinates38°30′00″N 43°20′33″E / 38.50000°N 43.34250°E / 38.50000; 43.34250 Tushpa (Armenian: Տոսպ, Տուշպա֊Վան Tosp, Tushpa-Van, Akkadian: Turuspa, from Urartian tur-, to destroy i.e. victorious) was the 9th-century BC capital of Urartu, later becoming ...

Google LLC v Defteros

Defamation case in Australia against Google Google LLC v DefterosCourtHigh Court of AustraliaDecided17 August 2022 (appeal) 30 April 2020 (initial)Citation(s)[2022] HCA (appeal) [2020] VSC 219 (initial)Case historyAppealed fromSupreme Court of VictoriaKeywordsDefamationHyperlinkSearch engineGoogle Google LLC v Defteros was a defamation case in Australia brought by a lawyer against Google. George Defteros is a lawyer, with much of his work being representing defendant gang memb...

 

Rocketdyne J-2

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

Kendall, New York

Town in New York, United StatesKendall, New YorkTownView of Lake Ontario from the Lake Ontario State Parkway in KendallLocation in Orleans County and the state of New York.Location of New York in the United StatesCoordinates: 43°20′9″N 78°2′55″W / 43.33583°N 78.04861°W / 43.33583; -78.04861CountryUnited StatesStateNew YorkCountyOrleansArea[1] • Total32.92 sq mi (85.26 km2) • Land32.86 sq mi (85.11...

Biblioteche di Milano

La Biblioteca comunale centrale di Milano. La tradizione bibliotecaria di Milano si rispecchia nelle sue tre storiche biblioteche, la veneranda Ambrosiana, la nazionale braidense e la Biblioteca Trivulziana, che conserva il Codice Trivulziano di Leonardo da Vinci. Nel corso dei secoli se ne sono aggiunte altre, come la Biblioteca comunale centrale di Milano, che è la principale sede del sistema bibliotecario comunale del capoluogo meneghino. Indice 1 Storia 2 Note 3 Voci correlate 4 Altri pr...

 

Owl and Weasel

Game newsletter Owl and WeaselEditorSteve Jackson and Ian LivingstoneCategoriesRoleplaying, Wargames, Board GamesFrequencyMonthly (with a two-month gap for Gen Con IX)First issueFebruary 1975Final issueNumberApril 197725CompanyGames WorkshopCountryUnited KingdomWebsiteGames-Workshop.com Owl and Weasel was a newsletter for board gamers, role-playing gamers and wargamers, published in London, England, by Games Workshop. A total of 25 issues were published from February 1975 until April 1977; it...

 

希腊原始神

希腊神话 神明 原始神 提坦 奧林匹斯 宁芙 海神 克托尼俄斯 英雄 赫拉克勒斯 海格力斯的苦役（英语：Labours of Hercules） 阿喀琉斯 赫克托耳 特洛伊战争 奥德修斯 《奥德赛》 伊阿宋 阿爾戈英雄 金羊毛 珀耳修斯 美杜莎 戈耳工 俄狄浦斯 斯芬克斯 俄耳甫斯 俄耳甫斯教 忒修斯 弥诺陶洛斯 柏勒洛丰 珀伽索斯 喀邁拉 代达洛斯 迷宮 阿塔兰忒 希波墨涅斯 金苹果（英语：Golden appl...

Warner Music Indonesia

Warner Music IndonesiaPerusahaan indukWarner Music GroupDidirikan1 Januari 1991 (sebagai Hemagita Tama Records)1 Januari 1996 (sebagai Warner Music Indonesia)StatusBeroperasiGenreBervariasiAsal negara IndonesiaLokasiGambir, Jakarta Pusat, JakartaSitus webwww.warnermusic.co.id Warner Music Indonesia (sebelumnya bernama Hemagita Tama Records) merupakan perusahaan rekaman yang berasal dari Jakarta, Indonesia. Perusahaan ini didirikan sejak 1 Januari 1991 di Jakarta dan dimiliki oleh Warner ...

 

FS Class E.464

Italian railways electric locomotive class 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: FS Class E.464 – news · newspapers · books · scholar · JSTOR (July 2016) (Learn how and when to remove this message) FS class E.464An E.464 with the new liveryType and originPower typeElectricBuilderBombardierBuild dat...