Vikipedio:Projekto matematiko/Orakola maŝino

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Orakola maŝino
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komplikteorio kaj komputebleca teorio, orakola maŝino estas abstrakta maŝino kutima studi decido (problemoj, problemas). Ĝi povas esti bildigita kiel Maŝino de Turing kun nigra skatolo, (nomita, vokis) orakolo, kiu estas pova decidi certa decido (problemoj, problemas) en sola (ŝtupo, paŝi). La problemo povas esti de (ĉiu, iu) komplekseca klaso. (Eĉ, Ebena, Para) nedecidebla (problemoj, problemas), ŝati la problemo de haltado, povas esti uzita.

Enhavo

1 Difino
2 Kompleksecaj klasoj de orakolaj maŝinoj
3 Orakoloj kaj problemoj de haltado
4 Aplikoj al Ĉifriko
5 Naturo de la Orakolo
6 Bibliografio

[redaktu] Difino

orakola maŝino estas Maŝino de Turing koneksa al orakolo. La Maŝino de Turing povas skribi sur ĝia posedi bendo (enigo, enigi) por la orakolo, tiam diri la orakolo al (ekzekuti, plenumit). En sola (ŝtupo, paŝi), la orakolo komputas ĝia funkcio, gumas ĝia (enigo, enigi), kaj skribas ĝia (eligi, eligo) al la bendo. Iam la Maŝino de Turing estas priskribita kiel havanta du (kranoj, bendoj, bendas), unu kies estas rezervita por orakolo (enigoj, enigas) kaj unu por (eligas, eligoj).

[redaktu] Kompleksecaj klasoj de orakolaj maŝinoj

La komplekseca klaso de decido (problemoj, problemas) solvebla per algoritmo en klaso A kun orakolo por problemo en klaso B estas skribita A^B. Ekzemple, la klaso de (problemoj, problemas) solvebla en polinoma tempo per (determinisma, determina) Maŝino de Turing kun orakolo por problemo en (Np, NP) estas P^{(Np, NP)}. (Ĉi tiu estas ankaŭ la klaso de (problemoj, problemas) reduktebla per polinomo-tempa turing-a rabato al problemo en (Np, NP).)

Ĝi estas evidenta (tiu, ke, kiu) (Np, NP) ⊆ P^{(Np, NP)}, sed la demando de ĉu (Np, NP)^{(Np, NP)} ⊂ P^{(Np, NP)} restas (malfermi, malfermita). Vidi polinoma hierarkio por plui (vastigaĵoj, vastigaĵas).

La (notacio, skribmaniero) A^B ankaŭ (meznombroj, meznombras, signifas) la klaso de (problemoj, problemas) solvebla per algoritmo en klaso A kun orakolo por la lingvo B. Ekzemple, P^_SAT_ estas la klaso de (problemoj, problemas) solvebla en polinoma tempo per (determinisma, determina) Maŝino de Turing kun orakolo por la Bulea plenumebloproblemo. Kiam lingvo B estas plenumi por iu klaso C, tiam A^B=A^C. En aparta, ekde _SAT_ estas NP-pleneco, P^_SAT_=P^{(Np, NP)}.

Orakolaj maŝinoj estas utila por esploranta la interrilato inter kompleksecaj klasoj P kaj NP, per konsideranta la interrilato inter P^A kaj (Np, NP)^A por orakolo A. En aparta, ĝi havas estas montrita (tiu, ke, kiu) tie ekzisti lingvoj A kaj B tia (tiu, ke, kiu) P^A=(Np, NP)^A kaj P^B≠(Np, NP)^B (Bakisto, Branko, _Solovay_, 1975). Kiam demando kiel ĉi tiu havas malsama (respondoj, respondas) por malsamaj orakoloj, ĝi estas dirita al _relativize_ ambaŭ (vojoj, vojas). La fakto (tiu, ke, kiu) la P=NP-demando _relativizes_ ambaŭ (vojoj, vojas) estas prenita kiel indikaĵo (tiu, ke, kiu) respondanta ĉi tiu demando estos esti malfacila, ĉar (ĉiu, iu) pruva tekniko (tiu, ke, kiu) _relativizes_ (kio estas, estas naiva per la (aldono, adicio) de orakolo) estos ne (respondo, respondi) la P=NP-demando.

Ĝi estas (interezanta, interesanta) al konsideri la (kesto, okazo) kie orakolo estas elektita hazarde de inter ĉiuj eblaj orakoloj. Ĝi havas estas montrita (tiu, ke, kiu) se orakolo A estas elektita hazarde, tiam kun probablo 1, P^A≠(Np, NP)^A (_Bennett_, Branko, 1981). Kiam demando estas vera por preskaŭ ĉiuj orakoloj, ĝi estas dirita al esti vera por hazarda orakolo. Ĉi tiu estas iam prenita kiel indikaĵo (tiu, ke, kiu) P≠(Np, NP). Bedaŭrinde, (propozicio, frazo, ordono) (majo, povas) esti vera por hazarda orakolo kaj malvera por ordinaraj Turingaj aŭtomatoj samtempe.

[redaktu] Orakoloj kaj problemoj de haltado

Ĝi estas ebla al premisi la ekzisto de orakolo kiu komputas ne-komputebla funkcio, kiel la esti konforma al la problemo de haltado aŭ iu ekvivalento. Maŝino kun orakolo de ĉi tiu (speco, ordigo) estas _hypercomputer_.

Interese, la haltanta paradokso ankoraŭ aplikas al tia (maŝinoj, maŝinas, aparatoj, aparatas); tio estas, kvankam ili povas difini ĉu apartaj Turingaj aŭtomatoj estos halti sur aparta (enigoj, enigas), ili ne povas difini ĉu (maŝinoj, maŝinas, aparatoj, aparatas) kun ekvivalentaj haltantaj orakoloj estos sin halti. Ĉi tiu fakto kreas hierarkio de (maŝinoj, maŝinas, aparatoj, aparatas), (nomita, vokis) la aritmetika hierarkio, ĉiu kun pli pova haltanta orakolo kaj (eĉ, ebena, para) (pli peza, pli peza) problemo de haltado.

[redaktu] Aplikoj al Ĉifriko

Unu de la komuna uzas de orakoloj en moderna komputiko estas en ĉifrika (protokoloj, protokolas). Se ni supozi la ekzisto de hazarda orakolo (tiu, ke, kiu) donas hazarda (sed konsekvenca) linio en respondo al (ĉiu, iu) demando, tiam ĉi tiu donas (speco, ordigo) de super-fiksi unusenca funkcio. Tio estas, donita (eligi, eligo) de la orakolo, ĝi estas neebla por (ĉiu, iu) programo al trovi (enigo, enigi) produktanta (tiu, ke, kiu) (eligi, eligo), escepti per (penanta, provanta, penante) parceloj de (enigoj, enigas). Ĉi tiu (plumboj, plumbas, kondukas) al tre forta (protokoloj, protokolas), sed al realigi la (protokoloj, protokolas) en praktiko la hazardaj orakoloj estas kutime (anstataŭigita, anstataŭigis) per pseŭdohazarda generilo. Bedaŭrinde, ĉi tiu estas en ĝenerala ne kiel fiksi. Vidi hazarda orakolo por pli (detaloj, detalas).

[redaktu] Naturo de la Orakolo

Turing-a farita ĝi sufiĉe klara (tiu, ke, kiu) orakoloj estas ne (maŝinoj, maŝinas, aparatoj, aparatas):

Estu ni supozi (tiu, ke, kiu) ni estas liverita kun iu _unspecified_ (meznombroj, meznombras, signifas) de solvanta nombro-teoria (problemoj, problemas); speco de orakolo kiel ĝi estis. Ni estos ne iri (ĉiu, iu) plui enen la naturo de ĉi tiu orakolo krom (diranta, dirante) (tiu, ke, kiu) ĝi ne povas esti maŝino" (Nedecidebla p. 167, represi de Turing-a's papero Sistemoj de Logiko Bazita Sur Ordaj numeraloj).

"maŝino", aŭ "maŝinaro" estas difinita kiel "(1) kunveno de (partoj, partas) (tiu, ke, kiu) elsendi (fortoj, fortas), moviĝo, kaj energio unu al alia en _predetermined_ maniero" (_Webster_'s (Naŭto, Naŭno) Nova _Collegiate_ Vortaro). Ankaŭ "maŝinaro" (majo, povas) esti: "loĝanta organismo aŭ unu de ĝia (funkcionalo, funkcia) sistemoj" (_Webster_'s, _ibid_, kaj tiel plu por pli (difinoj, difinas)). Tial maŝino, aŭ maŝinaro, havas (partoj, partas) (tiu, ke, kiu) movi. (Arkaika, Arĥaika) difino estas "konstruita aĵo ĉu materialo aŭ indiferenta".

Orakolo ne povas esti kunveno de movanta (partoj, partas), nek povas ĝi esti "loĝanta organismo aŭ ĝia (funkcionalo, funkcia) sistemoj". Ĉi tiu devus aspekti al bildigi ĝi "indiferenta" kaj ĝia naturo al troviĝi en metafiziko.

[redaktu] Bibliografio

Alan Turing, Sistemoj de logiko bazita sur ordaj numeraloj, _Proc_. Londono math. _soc_., 45, 1939
C. _Papadimitriou_. Komputa Komplekseco. Addison-a-_Wesley_, 1994. Sekcio 14.3: Orakoloj, _pp_. 339–343.
T. P. Bakisto, J. Branko, R. _Solovay_. _Relativizations_ de la P =? (Np, NP) Demando. _SIAM_ Ĵurnalo sur Komputanta, 4(4): 431-442 (1975)
C. H. _Bennett_, J. Branko. Relativa al Hazarda Orakolo A, P^A != (Np, NP)^A != co-NP^A kun Probablo 1. _SIAM_ Ĵurnalo sur Komputanta, 10(1): 96-113 (1981)
Sekcio 9.2: _Relativization_, _pp_.318–321.
_Martin_ _Davis_, redaktilo: La Nedecidebla, Baza (Paperoj, Paperas) sur Nedecidebla (Propozicioj, Propozicias), _Unsolvable_ (Problemoj, Problemas) Kaj Komputeblaj Funkcioj, Korvo Premi, (Nov-Jorkio, Novjorko), 1965. Turing-a's papero estas en ĉi tiu volumeno. (Paperoj, Paperas) inkluzivi tiuj per _Godel_, Preĝejo, _Rosser_, Kleene-a, kaj (Afiŝo, Posteno).