This HTML5 document contains 19 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
n17https://web.archive.org/web/20080515194944/http:/www.engr.uconn.edu/~dqg/papers/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n8https://youproof.hu/kriptografia/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n7http://lt.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://hu.dbpedia.org/resource/Sablon:
owlhttp://www.w3.org/2002/07/owl#
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n14http://hu.dbpedia.org/resource/Kategória:
n4http://www.engr.uconn.edu/~dqg/papers/

Statements

Subject Item
dbpedia-hu:Church-Turing-tézis
dbo:wikiPageRedirects
dbpedia-hu:Church–Turing-tézis
Subject Item
dbpedia-hu:Church–Turing-tézis
rdfs:label
Church–Turing-tézis
owl:sameAs
freebase:m.01_3k
dct:subject
n14:Számítógép-tudomány
dbo:wikiPageID
272981
dbo:wikiPageRevisionID
22939680
dbo:wikiPageExternalLink
n4:myth.pdf n8:8-karp-redukcio-np-teljes-np-nehez-cook-levin-tetel-logikai-halozatok-graf-izomorfizmus n8:6-turing-gep-formalis-nyelv-rekurzivan-felsorolhato-rekurziv-megallasi-problema n8:7-algoritmus-bonyolultsag-problemaosztalyok-polinomialis-exponencialis-p-np-sejtes-tanu-tetel n17:myth.pdf
prop-hu:wikiPageUsesTemplate
n10:Nemzetközi_katalógusok n10:Cite_journal
dbo:wikiPageInterLanguageLink
n7:Tiuringo_mašina
dbo:abstract
A számításelméletben a Church–Turing-tézis az 1930-as években megfogalmazott sejtés, mely szerint minden formalizálható probléma, ami megoldható algoritmussal, az megoldható Turing-géppel is, illetve bármilyen, a Turing-gép fogalmával azonos számítási teljesítményű absztrakt modellel, pl. lambda-kalkulussal is; azaz a Turing-gép (vagy ekvivalensei) a feladatmegoldó eljárások legáltalánosabb és a fenti értelemben legerősebb példája. A sejtést azért nem tételnek, hanem csak (hipo)tézisnek nevezik, mert nem matematikai tétel, ugyanis a „feladatmegoldó eljárás” nem mint definiált matematikai fogalom szerepel). A tézis inkább a számítógép-tudomány paradigmaszerű programja, semmint matematikai tétel. Ugyanakkor szintén a harmincas években a „feladatmegoldó eljárás” fogalmát számtalan alakban sikerült formálisan megfoghatóvá tenni, de kiderült, hogy ezek a megfogalmazások is ekvivalensek a Turing-gépre épülő eljárásfogalommal. Ez azt jelenti, hogy a Turing-gép egy univerzális algoritmikus modell. Maga a Turing-gép tekinthető az algoritmus egy definíciójának. A tézis összefügg az elvi létével illetve lehetetlenségével is. Nem ismerünk olyan algoritmikus rendszert, amelyről tudnánk, hogy erősebb a Turing-gépnél, és a legtöbb algoritmikus rendszerre bizonyított, hogy gyengébb, vagy ekvivalens.A bizonyítottan Turing-ekvivalens algoritmikus rendszerek a következők: * asszociatív kalkulusok * rekurzív függvények osztálya * a lambda-kalkulus függvény-osztálya * formális nyelvek legáltalánosabb, kötetlen osztálya * C, LISP, Java, Prolog, Pascal stb. nyelven írt nem interaktív programok
prov:wasDerivedFrom
wikipedia-hu:Church–Turing-tézis?oldid=22939680&ns=0
dbo:wikiPageLength
3059
foaf:isPrimaryTopicOf
wikipedia-hu:Church–Turing-tézis
Subject Item
wikipedia-hu:Church–Turing-tézis
foaf:primaryTopic
dbpedia-hu:Church–Turing-tézis