Funció computable

Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilitat i consisteixen en les funcions que poden ser calculades per una màquina de Turing.

Introducció

Les funcions computables són una formalització de la noció intuïtiva d'algorisme i segons la Tesi de Church-Turing són exactament les funcions que poden ser calculades amb una màquina de càlcul. La noció de la computabilitat d'una funció pot ser relativitzada a un conjunt arbitrari de nombres naturals A , o equivalent a una funció arbitrària f dels naturals als naturals, per mitjà de màquines de Turing esteses per un oracle per A o f . Aquestes funcions pot ser anomenats A-computable o f-computable respectivament. Abans la definició precís d'una funció computable els matemàtics usaven el terme informal efectivament computable .

Les funcions computables són usades per discutir computabilitat sense referir-se a cap model de computació concret, com màquina de Turing o màquina de registres. Els axiomes de Blum poden ser usats per a definir una teoria de complexitat computacional abstracta sobre el conjunt de funcions computables.

Segons la Tesi de Church-Turing, la classe de funcions computables és equivalent a la classe de funcions definides per funcions recursives, càlcul lambda, o algorismes de Markov.

Alternativament es poden definir com els algoritmes que poden ser calculats per una màquina de Turing, una màquina de Post, o una màquina de registres.

A teoria de la complexitat computacional, el problema de determinar la complexitat d'una funció computable aquesta conegut com un problema de funcions.

Definició

Una funció parcial

F:\subseteq \mathbb {N} \to \mathbb {N}

es diu computable si la gràfica de $f$ és un conjunt recursivament enumerable. El conjunt de funcions parcialment computables amb un paràmetre és normalment escrit $\mathbf {P} ^{(1)}$ o $\mathbf {P}$ si el nombre de paràmetres és clar del context.

Una funció total

F:\mathbb {N} \to \mathbb {N}

es diu computable si el gràfic de $f$ és un conjunt recursiu. El conjunt de funcions totalment computables amb un paràmetre normalment s'escriu $\mathbf {R} ^{(1)}$ o $\mathbf {R}$ .

Una funció computable $f$ s'anomena predicat computable si és una funció amb valor booleà, és a dir

F:\subseteq \mathbb {N} \to \{0,1\}

Comentaris

De vegades, per raons de claredat, s'escriu una funció computable com a

G:\subseteq \mathbb {N} ^{k}\to \mathbb {N}

Podem fàcilment codificar g en una nova funció

F:\subseteq \mathbb {N} \to \mathbb {N}

utilitzant una funció de parells.

Exemples

Funció constant f : N ^k? N , f ( n ₁,... n _k): = n

Afegir f : N ²? N , f ( n ₁, n ₂): = n ₁+ n ₂

Màxim comú divisor
Identitat de Bézout, una equació diofàntica linear

Propietats

El conjunt de les funcions computables és numerable.

Donats dues funcions computables f i g llavors f + g , fg i f o g són funcions computables.

Les funcions computables són definibles aritmèticament.

Una funció amb valor booleà f és un predicat computable si i només si el llenguatge $\{x\in \Sigma ^{*}:f(x)=1\}$ és recursiu.

Read other articles:

Ervinna

ErvinnaLahirTheodora Monica Ervin4 Mei 1956 (umur 67)Surabaya, Jawa Timur, IndonesiaPekerjaanpenyanyiSuami/istriRobert SoesantoKarier musikGenrepop, disco, keroncong, folk, reggae, dangdut, gospel, mandopopTahun aktif1977 - sekarangLabelCipto Records Indra Records Platinum Records (2014-sekarang)Artis terkaitA. Riyanto, Tetty Kadi Theodora Monica Ervin, atau dikenal dengan nama panggung Ervinna (lahir di Surabaya, Jawa Timur, 4 Mei 1956) adalah penyanyi berkebangsaan Indonesia yang sang...

Bienvenido Marañón

Dalam artikel ini, pertama atau paternal nama keluarganya adalah Marañón dan nama keluarga maternal atau keduanya adalah Morejón. Bienvenido Marañón Bienve with United City, at a press conference in 2018Informasi pribadiNama lengkap Bienvenido Marañón MorejónTanggal lahir 15 Mei 1986 (umur 37)Tempat lahir El Puerto de Santa María, SpanyolTinggi 173 cm (5 ft 8 in)Posisi bermain StrikerInformasi klubKlub saat ini ChanthaburiNomor 10Karier junior La Salle Bet...

Kanon Alkitab Tewahedo Ortodoks

Bagian dari Alkitab KristenPerjanjian LamaYosua 1:1 pada Kodeks Aleppo Taurat Kejadian Keluaran Imamat Bilangan Ulangan Sejarah Yosua Hakim-hakim Rut 1 Samuel 2 Samuel 1 Raja-raja 2 Raja-raja 1 Tawarikh 2 Tawarikh Ezra Nehemia Ester Puisi Ayub Mazmur Amsal Pengkhotbah Kidung Agung Kenabian Besar Yesaya Yeremia Ratapan Yehezkiel Daniel Kecil Hosea Yoël Amos Obaja Yunus Mikha Nahum Habakuk Zefanya Hagai Zakharia Maleakhi Deuterokanonika Tobit Yudit Tambahan Ester 1 Makabe 2 Makabe Kebijaksanaa...

KSPF

Radio station in Dallas, Texas, US For the airport in Spearfish, South Dakota, assigned ICAO code KSPF, see Black Hills Airport. KLUV redirects here. For the contemporary Christian radio network, see K-Love. For information on KLUV in Huron, South Dakota, see List of K-Love stations. KSPFDallas, TexasUnited StatesBroadcast areaDallas/Fort Worth MetroplexFrequency98.7 MHz (HD Radio)Branding98.7 The SpotProgrammingLanguage(s)EnglishFormatClassic hitsSubchannelsHD2: News/talk (KRLD simulcast)Own...

Ellie Reeves

Reeves pada 2017 Eleanor Claire Reeves[1] (lahir 11 Desember 1980) adalah seorang politikus Partai Buruh Britania Raya.[2] Ia adalah saudari dari Rachel Reeves, dan menikahi John Cryer. Referensi ^ No. 61961. The London Gazette. 19 June 2017. hlm. 11776. ^ Former Labour official Ellie Reeves selected for safe seat in London. LabourList. Diakses tanggal 8 June 2017. Pranala luar Profil di Parlemen Britania Raya Kontribusi di Parlemen di Hansard Catatan suara di...

Turkish Cypriot nationalism

Turkish Cypriot nationalism is an ethnic nationalism supporting the independence of the Turkish Republic of Northern Cyprus (TRNC) and mostly desires that the TRNC stay independent from Turkey while opposing the idea of a united Cyprus with the Greek-dominated Republic of Cyprus. The objective of taksim, that is, the partition of the island of Cyprus into Turkish and Greek portions, is widespread among Turkish Cypriot nationalists. Nevertheless, a considerable number of them wish for Turkey t...

Miguel de Cervantes

Spanish novelist, poet, and playwright (1547–1616) Cervantes redirects here. For other uses, see Cervantes (disambiguation). Miguel Cervantes redirects here. For the American actor and singer, see Miguel Cervantes (actor). Miguel de CervantesThis portrait, attributed to Juan de Jáuregui,[a] is unauthenticated. No authenticated image of Cervantes exists.[1][2]Born29 September 1547 (assumed)Alcalá de Henares, Crown of CastileDied22 April 1616(1616-04-22) (aged 6...

Unione Sportiva Catanzaro 1929 2019-2020

Questa voce o sezione deve essere rivista e aggiornata appena possibile. Sembra infatti che questa voce contenga informazioni superate e/o obsolete. Se puoi, contribuisci ad aggiornarla. Voce principale: Unione Sportiva Catanzaro 1929. Unione Sportiva Catanzaro 1929Stagione 2019-2020Lo Stadio Nicola Ceravolo Sport calcio Squadra Catanzaro Allenatore Gaetano Auteri, poi Gianluca Grassadonia, poi Gaetano Auteri All. in seconda Loreno Cassia, poi Pierluca Cincione, poi Loreno Cassia Presid...

Madras Talkies

Indian entertainment company (founded 1995) Madras TalkiesCompany typePrivateIndustryEntertainmentFounded1995 in Chennai, Tamil NaduFoundersMani RatnamG. SrinivasanHeadquartersChennai, IndiaKey peopleMani RatnamSuhasiniProductsFilmsOwnerMani RatnamWebsitemadrastalkies.com Madras Talkies is an Indian entertainment company, which was established by director Mani Ratnam and his brother G. Srinivasan as partners in 1995. Madras Talkies has actively involved in production of films and television s...

Северный морской котик

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

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。美國眾議院 United States House of Representatives第118届美国国会众议院徽章众议院旗...

世界政區索引

此條目可能包含不适用或被曲解的引用资料，部分内容的准确性无法被证實。 (2023年1月5日)请协助校核其中的错误以改善这篇条目。详情请参见条目的讨论页。各国相关主題列表索引国内生产总值石油储量国防预算武装部队（军事）官方语言人口統計人口密度生育率出生率死亡率自杀率谋杀率失业率储蓄率识字率出口额进口额煤产量发电量监禁率死刑国债 ...

Volano (Italia)

Questa voce o sezione sull'argomento centri abitati del Trentino-Alto Adige 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. Volanocomune Volano – VedutaL'abitato visto da sud-est LocalizzazioneStato Italia Regione Trentino-Alto Adige Provincia Trento AmministrazioneSindacoMaria Alessandra Furlini (Liste civiche) dall'11-5-2015 ...

Piercarlo Beretta

Piercarlo Beretta (in piedi, a sinistra) nel 1952, in veste di commissario tecnico della nazionale italiana. Piercarlo Beretta detto Carlino (Gardone Val Trompia, 1908 – Gardone Val Trompia, 5 marzo 1984) è stato un imprenditore e dirigente sportivo italiano. Fu personaggio poliedrico, erede della più antica casa industriale del mondo, posseduta da 480 anni dalla sua famiglia, la Beretta. Biografia Carlino Beretta era un industriale di stampo antico, riservato e schivo di pubblicità, uno...

Athletics at the 1974 British Commonwealth Games – Men's 1500 metres

Athletics at the 1974 BritishCommonwealth GamesTrack events100 mmenwomen200 mmenwomen400 mmenwomen800 mmenwomen1500 mmenwomen5000 mmen10,000 mmen100 m hurdleswomen110 m hurdlesmen400 m hurdlesmen3000 msteeplechasemen4×100 m relaymenwomen4×400 m relaymenwomenRoad eventsMarathonmen20 mile walkmenField eventsHigh jumpmenwomenPole vaultmenLong jumpmenwomenTriple jumpmenShot putmenwomenDiscus throwmenwomenHammer throwmenJavelin throwmenwomenCombined eventsPentathlonwomenDecathlonmenvte The men'...

Sustainable flooring

The examples and perspective in this article deal primarily with the United States and do not represent a worldwide view of the subject. You may improve this article, discuss the issue on the talk page, or create a new article, as appropriate. (September 2017) (Learn how and when to remove this message) Bamboo flooring Sustainable flooring is produced from sustainable materials (and by a sustainable process) that reduces demands on ecosystems during its life-cycle.[according to whom?]...

Il Romanista

Il RomanistaLogoStato Italia Linguaitaliano Periodicitàquotidiano Generestampa sportiva FormatoBroadsheet FondatoreRiccardo Luna Fondazione10 settembre 2004 SedeVia Angelo Bargoni, 8 Roma[1] EditoreIl Romanista Srl[1] Tiratura6 500[2] (dicembre 2019) Diffusione digitale37 000[2] (dicembre 2019) DirettoreTonino Cagnucci[1] VicedirettoreDaniele Lo Monaco[1] ISSN1824-503X (WC · ACNP) DistribuzionecartaceaEdizione cartaceasingo...

Ministry of Foreign Affairs (Ukraine)

Ukrainian government ministry Ministry of Foreign AffairsМіністерство закордонних справMinistry overviewFormedNovember 12, 1917; 106 years ago (1917-11-12)JurisdictionGovernment of UkraineHeadquarters1, Mykhailivska Sq, Kyiv[1]Employees2,000+[2]Minister responsibleDmytro Kuleba, Minister of Foreign Affairs[3]Websitemfa.gov.ua The Ministry of Foreign Affairs of Ukraine (Ukrainian: Міністерство закордонн�...

Julius Chan

The Right HonourableSir Julius ChanGCL GCMG KBEChan in 2021 Perdana Menteri Papua Nugini ke-2Masa jabatan2 Juni 1997 – 22 Juli 1997Penguasa monarkiElizabeth IIPendahuluJohn GihenoPenggantiBill SkateMasa jabatan30 Agustus 1994 – 27 Maret 1997Penguasa monarkiElizabeth IIPendahuluPaias WingtiPenggantiJohn GihenoMasa jabatan11 Maret 1980 – 2 Agustus 1982Penguasa monarkiElizabeth IIPendahuluMichael SomarePenggantiMichael SomareGubernur New IrelandPetahanaMu...

FripSide

Japanese pop and trance duo Not to be confused with Flipside (disambiguation). fripSideOfficial logoBackground informationOriginJapanGenresJ-pop, trance, synth-pop, pop rockYears active2002–presentLabelselseena-music entertainment (2006–2008)Visual Arts (2008–2009)MAGES. (2008)Pony Canyon Inc. (2008)NBCUniversal Entertainment Japan (2009–present)Avex Pictures Inc. (2016)MembersSatoshi YaginumaMao UesugiHisayo AbePast membersNao (2002–2009)Yoshino Nanjō (2009–2022)Websitewww.frips...

/profillengkap.com/index.php/article/Fox Crossing, Wisconsin

Maïeutique (philosophie)

Begonia listada

Dialogus de Scaccario

2012–13 Memphis Tigers men's basketball team

1990 in sports

1985–86 Mansfield Town F.C. season

Jack Harkness (footballer, born 2004)

Fatsa

Tony Pulis

Nouveau roman

Mémorial de la France combattante