Princípio de Markov

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW • CAPES • Google (notícias • livros • acadêmico)). (Novembro de 2012)

"Se é impossível que um algoritmo não termine, então ele irá terminar". Uma máquina com uma corrente aparentemente interminável

O princípio de Markov, cujo nome advém do matemático Andrei Markov Júnior, filho do também renomado matemático Andrei Markov, é uma tautologia que não é válida por lógica intuicionista mas pode ser justificada por meio de construtivismo. Existem muitas formulações equivalentes ao princípio de Markov.

Definição

Na linguagem da teoria da computabilidade, o princípio de Markov é a expressão do argumento de que, se é impossível que um algoritmo não termine, então ele irá terminar. Isso é equivalente ao argumento de que, se um conjunto e o seu complementar são ambos recursivamente enumeráveis, então o conjunto é recursivo.

Na lógica de predicados, um predicado P sobre um domínio qualquer é chamado recursivo se, para cada x no domínio, ou P(x) é verdadeiro ou P(x) é falso, o que nem sempre é o caso do construtivismo.

Se P é um predicado recursivo sobre os números naturais, o princípio de Markov é expresso como:

$(\forall n(P(n)\vee \neg P(n)))\wedge (\neg \forall n\neg P(n))\rightarrow (\exists n\;P(n)).$

Isto é, se P não pode ser falso para todos os números naturais n, então é verdadeiro para algum n.

Na linguagem de aritmética de Heyting, o princípio é equivalente a:

\neg \neg \exists n\;f(n)=0\rightarrow \exists n\;f(n)=0,

$f$ sendo uma função computável sobre os números naturais.

Na linguagem da análise real, o princípio é equivalente aos seguintes:

Para cada número real x, se é contraditório que x é igual a 0, então existe um y ∈ Q tal que 0 < y < |x|, muitas vezes expresso por se dizer que x é separado (sugerido do inglês apartness relation ) ou construtivamente diferente de 0.
Para cada número real x, se é contraditório que x é igual a 0, então existe um y ∈ R tal que xy = 1.

Realizabilidade

A realizabilidade pode ser usada para justificar o princípio de Markov: um realizador é um operador μ que consecutivamente analisa se $P(0),P(1),P(2),\dots$ é verdade. Porque $P$ não é falso em todo lugar, a procura não pode durar para sempre. Usando lógica clássica podemos concluir que a procura termina, nomeadamente, no valor em que $P$ existe.

A realizabilidade modificada não justifica o princípio de Markov, mesmo se a lógica clássica for usada na metateoria: não existe um realizador na linguagem de cálculo lambda simplesmente tipado, haja vista que essa linguagem não é Turing-completa e que ciclos arbitrários não podem ser definidos nela.

Regra de Markov

A regra de Markov é a formulação do princípio de Markov como uma regra. Ela declara que $\exists n\;P(n)$ é derivável logo que $\neg \neg \exists n\;P(n)$ seja recursivo para $P$ . O lógico Harvey Friedman mostrou que a regra de Markov é uma regra admissível em lógica intuicionista, aritmética de Heyting e muitas outras teorias intuicionistas^[1], usando a Tradução de Friedman.

Princípio de Markov fraco

Uma forma fraca do princípio de Markov pode ser expressa em linguagem de análise como:

$\forall x\in \mathbb {R} \ (\forall y\in \mathbb {R} \ \neg \neg (0<y)\vee \neg \neg (y<x))\to 0<x.$

Essa forma pode ser justificada pelos princípios da continuidade de Luitzen Egbertus Jan Brouwer, ao passo que a forma mais forte os contradiz. Logo, pode ser derivado do intuicionismo, da realizabilidade e do racionalismo clássico, em cada caso por diferentes razões, mas esse princípio não é valido no sentido lato construtivista de Bishop.^[2]

Referências

↑ Harvey Friedman. Classically and Intuitionistically Provably Recursive Functions. In Scott, D. S. and Muller, G. H. Editors, Higher Set Theory, Volume 699 of Lecture Notes in Mathematics, Springer Verlag (1978), pp. 21–28.
↑ Ulrich Kohlenbach, "On weak Markov's principle". Mathematical Logic Quarterly (2002), vol 48, issue S1, pp. 59–65.

Ligações externas

Constructive Mathematics (Stanford Encyclopedia of Philosophy)

Read other articles:

Kusu-tanah raksasa

Kusu-tanah raksasa Peroryctes broadbenti Status konservasiGentingIUCN16710 TaksonomiKerajaanAnimaliaFilumChordataKelasMammaliaOrdoPeramelemorphiaFamiliPeramelidaeGenusPeroryctesSpesiesPeroryctes broadbenti Distribusi lbs Kusu-tanah raksasa ( Peroryctes broadbenti ) adalah spesies marsupial dalam keluarga Peramelidae yang endemik di Papua Nugini . Habitat aslinya adalah hutan kering subtropis atau tropis. [2] Lokalitas tipenya adalah Papua Nugini, Provinsi Tengah, tepian Sungai Goldie ...

Prva slovenska nogometna liga 2017-2018

1. SNL 2017-2018Prva liga Telekom Slovenije 2017./18. Competizione Campionato sloveno Sport Calcio Edizione 27ª Organizzatore NZS Date dal 15 luglio 2017al 27 maggio 2018 Luogo Slovenia Partecipanti 10 Sito web http://www.prvaliga.si/ Risultati Vincitore Olimpia Lubiana(2º titolo) Retrocessioni Ankaran Hrvatini Statistiche Miglior giocatore Senijad Ibričić[1] Miglior marcatore Luka Zahovič (18 reti) Incontri disputati 180 Gol segnati 500 (2,78 per in...

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

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

PET bottle recycling

Recycling of bottles made of polyethylene terephthalate This article is about the recycling of PET bottles. For the recycling of plastics more generally, see Plastic recycling. PET bottle recyclingClockwise from top left: Sorting at a material recovery facilityBales of colour-sorted PET bottlesA reprocessing facility where used bottles are converted into clean flakes or pellets suitable for remoulding into new itemsRecycled PET flakesA water bottle made from recycled PET (bottle-to-bottle rec...

فولتا سان خوان 2023

فولتا سان خوان 2023 تفاصيل السباقسلسلة39. فولتا سان خوانمنافسةسلسلة سباقات الاتحاد الدولي للدراجات للمحترفين 2023 2.Pro‏مراحل7التواريخ22 – 29 يناير 2023المسافات1٬143 كمالبلد الأرجنتيننقطة البدايةسان خوان، الأرجنتيننقطة النهايةسان خوان، الأرجنتينالفرق26عدد المتسابقين في البداي...

Félix Miéli Venerando

Disambiguazione – Félix rimanda qui. Se stai cercando altri significati, vedi Felix. Félix Félix Miéli Venerando (2008) Nazionalità Brasile Altezza 176[1] cm Peso 72[1] kg Calcio Ruolo Portiere Termine carriera 1977 CarrieraSquadre di club1 1951-1954 Juventus-SP? (-?)1956 Portuguesa? (-?)1957-1960 Nacional-SP? (-?)1960-1968 Portuguesa? (-?)1968-1977 Fluminense64 (-?)[2]Nazionale 1965-1972 Brasile39 (-37)Palmarès Mon...

Associazione Calcio Femminile Trani 80

A.C.F. Trani 80Calcio Segni distintiviUniformi di gara Casa Trasferta Terza divisa Colori sociali Bianco, azzurro Dati societariCittàTrani Nazione Italia ConfederazioneUEFA Federazione F.I.G.C.F. e F.I.G.C. Fondazione1979 Scioglimento1988StadioComunale di Trani(10 700 posti) Palmarès Trofei nazionali1 Coppe Italia Si invita a seguire il modello di voce L'Associazione Calcio Femminile Trani 80 era una società calcistica femminile con sede a Trani attiva tra il 1979 e il 1988. ...

ヨハネス12世 (ローマ教皇)

ヨハネス12世第130代ローマ教皇教皇就任 955年12月16日教皇離任 964年5月14日先代アガペトゥス2世次代レオ8世個人情報出生 937年スポレート公国（中部イタリア）スポレート死去 964年5月14日教皇領、ローマ原国籍スポレート公国親父アルベリーコ2世（スポレート公）、母アルダその他のヨハネステンプレートを表示ヨハネス12世（Ioannes XII、937年 - 964年5月14日）は、ロ...

Temporal fenestra

Opening in the skull behind the orbit in some animals Skull of an idealised diapsid, with upper and lower temporal fenestrae behind the eye socket Temporal fenestrae are openings in the temporal region of the skull of some amniotes, behind the orbit (eye socket). These openings have historically been used to track the evolution and affinities of reptiles. Temporal fenestrae are commonly (although not universally) seen in the fossilized skulls of dinosaurs and other sauropsids (the total group...

Paul LaCamera

Paul Joseph LaCamera (lahir 4 September 1963) adalah seorang jenderal bintang empat dan perwira infanteri Angkatan Darat Amerika Serikat yang menjabat sebagai komandan Komando Perserikatan Bangsa-Bangsa, Komando Pasukan Gabungan ROK/AS, dan Pasukan Amerika Serikat di Korea sejak 2 Juli 2021. LaCamera terakhir menjabat sebagai panglima Angkatan Darat Amerika Serikat Pasifik dari 18 November 2019 hingga 3 Juni 2021. Sebelumnya ia menjabat sebagai panglima Korps Lintas Udara XVIII. Penugas...

Connecticut College

College in New London, Connecticut, US Connecticut CollegeFormer namesThames College (1911)[1]Connecticut College for Women (1911–1969)[2]MottoTanquam lignum quod plantatum est secus decursus aquarumMotto in EnglishLike a tree planted by rivers of water that bringeth forth its fruit in its season.TypePrivate liberal arts collegeEstablishedApril 1911; 113 years ago (1911-04)Academic affiliationOberlin GroupAnnapolis GroupCLACEndowment$435 million (...

Abu-Zaid al Kuwaiti

Kuwaiti al-Qaeda member Not to be confused with Abu Omar al-Kuwaiti. Abu-Zaid al KuwaitiKhalid Bin Abdul Rehman Al-Hussainan (خالد بن عبد الرحمن الحسينان)Born1965 or 1966KuwaitDied(2012-12-06)December 6, 2012 (aged 46)North Waziristan, PakistanCause of deathDrone strikeOrganizationAl-QaedaKnown forPossible heir to Ayman al-Zawahiri Abu-Zaid al Kuwaiti (born Khalid Bin Abdul Rehman Al-Hussainan (Arabic: خالد بن عبد الرحمن الحسينان...

Cabramatta, New South Wales

Not to be confused with Cabramurra, New South Wales. Suburb of Sydney, New South Wales, AustraliaCabramattaSydney, New South WalesFriendship Arch, Freedom PlazaMapPopulation21,142 (2021 census)[1] • Density4,700/km2 (12,170/sq mi)Established1850sPostcode(s)2166Elevation22 m (72 ft)Area4.5 km2 (1.7 sq mi)Location30 km (19 mi) south-west of Sydney CBDLGA(s)City of FairfieldState electorate(s)CabramattaFederal division(s)Fowler Sub...

أبو عمر البغدادي

أبو عمر البغدادي معلومات شخصية اسم الولادة حامد داود محمد خليل الزاوي الميلاد سنة 1959 محافظة الأنبار الوفاة 18 أبريل 2010 (50–51 سنة)[1] تكريت سبب الوفاة ضربة جوية مواطنة العراق الديانة الإسلام عضو في قاعدة الجهاد في بلاد الرافدين، ومجلس شورى المجاه...

Hotel Transylvania

American animated media franchise This article is about the American media franchise. For the film, see Hotel Transylvania (film). Hotel TransylvaniaCreated byTodd Durham[1]OwnerSony Pictures AnimationYears2012–presentPrint publicationsGraphic novel(s) Kakieland Katastrophe (2017) My Little Monster-Sitter (2018) Motel Transylvania (2018) Films and televisionFilm(s) Hotel Transylvania (2012) Hotel Transylvania 2 (2015) Hotel Transylvania 3: Summer Vacation (2018) Hotel Transylvania: ...

Finding Mr. Destiny

Finding Mr. DestinySutradaraJang Yoo-jeongProduserMin Jin-sooMin Kyu-dongDitulis olehLee Kyung-uiBerdasarkanFinding Kim Jong-wook (musikal)PemeranIm Soo-jungGong YooPenata musikPark Ji-woongSinematograferLee Hyung-dukPenyuntingKim Hyeong-juDistributorCJ EntertainmentTanggal rilis 9 Desember 2010 (2010-12-09) Durasi112 menitNegaraKorea SelatanBahasaKoreaPendapatankotor$7,444,073[1] Finding Mr. Destiny (Hangul: 김종욱 찾기; RR: Kim Jong-uk chat-gi&#...

Lonja de los Paños (Cracovia)

Lonja de los Paños Sukiennice w Krakowie Patrimonio de la Humanidad (incluido en el ámbito de «Centro histórico de Cracovia», n.º ref. 29) (1978) Vista del Sukiennice desde la basílica de Santa María.UbicaciónPaís PoloniaSubdivisión Pequeña PoloniaMunicipio CracoviaCoordenadas 50°03′42″N 19°56′15″E / 50.061678, 19.937384CaracterísticasTipo LonjaArquitecto Giovanni Maria Mosca, Tomasz PrylińskiEstilo Renacentista y neogóticoHistoriaCon...

Side effect

Outcome that is secondary to the one intended This article is about side effects in the context of medicine. For side effects in the context of computer science, see Side effect (computer science). For other uses, see Side effect (disambiguation). In medicine, a side effect is an effect, whether therapeutic or adverse, that is unintended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequences of the use of a drug...

Thieuloy-Saint-Antoine

Thieuloy-Saint-AntoinecomuneThieuloy-Saint-Antoine – Veduta LocalizzazioneStato Francia RegioneAlta Francia Dipartimento Oise ArrondissementBeauvais CantoneGrandvilliers TerritorioCoordinate49°38′N 1°57′E49°38′N, 1°57′E (Thieuloy-Saint-Antoine) Altitudine165 e 196 m s.l.m. Superficie2,49 km² Abitanti343[1] (2009) Densità137,75 ab./km² Altre informazioniCod. postale60210 Fuso orarioUTC+1 Codice INSEE60633 CartografiaThieuloy-Saint-Antoine Modi...

Theodas of Laodicea

Part of a series onPyrrhonism Pyrrhonists Pyrrho Timon of Phlius Aenesidemus Agrippa the Skeptic Sextus Empiricus Concepts Ataraxia Acatalepsy Adiaphora Aporia Dogma Epoché Similar philosophies Empiric school Epilogism Academic skepticism Modern influence Münchhausen trilemma Benson Mates Robert Fogelin Philosophy portalvte Theudas of Laodicea (Greek: Θευδάς ό Λαοδικεύς) was a Pyrrhonist philosopher[1] and physician of the Empiric school,[2] in the 2nd ce...