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

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

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n18http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n31http://lt.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
n25https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
n15http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbr:Proof_of_impossibility
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Rice-Myhill-Shapiro_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rice's_Theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rices_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Definite_assignment_analysis
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Index_set_(computability)
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:List_of_mathematical_logic_topics
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:List_of_mathematical_proofs
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Combinatory_logic
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Computability
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Computability_theory
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Generic-case_complexity
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Scott–Curry_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Function_(computer_programming)
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Complete_numbering
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Full-employment_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Henry_Gordon_Rice
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Static_program_analysis
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Theory_of_computation
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Turing's_proof
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Halting_problem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Subcountability
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Abstract_interpretation
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Abstraction_(computer_science)
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Cantor's_diagonal_argument
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Undecidable_problem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Universal_Turing_machine
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:List_of_theorems
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:List_of_undecidable_problems
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Rice–Shapiro_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Semantic_gap
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Rice's_theorem
rdf:type
yago:WikicatTheorems yago:Statement106722453 yago:WikicatTheoremsInTheFoundationsOfMathematics yago:Message106598915 yago:Communication100033020 yago:Abstraction100002137 yago:Theorem106752293 yago:WikicatMathematicalTheoremsInTheoreticalComputerScience yago:WikicatMathematicalTheorems yago:Proposition106750804
rdfs:label
ライスの定理 Stelling van Rice Teorema de Rice Теорема Райса Twierdzenie Rice’a Teorema de Rice 莱斯定理 Théorème de Rice Rice's theorem Teorema di Rice Satz von Rice
rdfs:comment
Теорема Райса — утверждение теории алгоритмов, согласно которому для любого нетривиального свойства вычислимых функций определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им. Названа по имени американского математика , доказавшего её в 1951 году в докторской диссертации. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств. In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function. Nella logica matematica, nella teoria della calcolabilità e nell'informatica teorica, il teorema di Rice costituisce un importante risultato nella teoria delle funzioni ricorsive e delle funzioni calcolabili (le due sono la stessa cosa, secondo la tesi di Church-Turing).Esso afferma che, per ogni proprietà non banale delle funzioni calcolabili, è non decidibile il problema di decidere quali funzioni soddisfino tale proprietà e quali no.Per proprietà banale in questo caso si intende una proprietà che non effettua alcuna discriminazione tra le funzioni calcolabili, cioè che vale o per tutte o per nessuna. Il teorema prende il nome da , il quale ne fornì la dimostrazione nel 1951 nella sua tesi di dottorato presso la Syracuse University. De stelling van Rice is een belangrijke stelling in de theoretische informatica, meer in het bijzonder in de berekenbaarheidstheorie. Informeel zegt de stelling dat het onmogelijk is een algoritme te schrijven dat als invoer een ander algoritme en een bepaalde niet-triviale eigenschap krijgt en in alle gevallen correct beslist of het algoritme die eigenschap bezit. Uit de stelling volgt dat automatische verificatie van software in het algemeen niet mogelijk is. De stelling is genoemd naar de Amerikaanse logicus en wiskundige , die hem in 1954 in zijn proefschrift voor het eerst bewees. ライスの定理（ライスのていり、英: Rice's theorem）は、計算機科学における計算可能関数の理論に関する定理で、定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。名称の由来は Henry Gordon Rice から。 En informatique théorique, plus précisément en théorie de la calculabilité, le théorème de Rice énonce que toute propriété sémantique non triviale d'un programme est indécidable. Le théorème de Rice généralise l'indécidabilité du problème de l'arrêt. Le théorème est classique et fait l'objet d'exercices dans certains ouvrages de théorie de la calculabilité. Il a une certaine portée philosophique vis-à-vis de la calculabilité et est dû au logicien Henry Gordon Rice. 莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 Twierdzenie Rice’a – każda nietrywialna własność języków rekurencyjnie przeliczalnych jest nierozstrzygalna.Twierdzenie zawdzięcza swoją nazwę . En teoría de la computación, el teorema de Rice es un teorema enunciado por y luego generalizado junto con y a lo que se conoce como el . Básicamente se puede enunciar el teorema de la siguiente manera: Dada una propiedad no trivial de las funciones parciales, no es computable determinar si una función arbitraria la posee o no.​ Es un típico problema de decisión que no se puede resolver, al igual que el problema de la parada. Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte.Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu entscheiden. Na teoria da computação, o teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade. Aqui, uma propriedade de funções parciais é chamada trivial se ela vale para todas as funções parciais computáveis ou nenhuma, e um método de decisão eficaz é chamado geral se este decide corretamente para cada algoritmo. O teorema tem o nome de , é também conhecido como Teorema de Rice-Myhill-Shapiro. No título do teorema, depois de Rice, temos os matemáticos John Myhill e .
foaf:depiction
n15:Rice_reduction.svg
dcterms:subject
dbc:Articles_containing_proofs dbc:Undecidable_problems dbc:Theorems_in_theory_of_computation dbc:Theorems_in_the_foundations_of_mathematics
dbo:wikiPageID
25852
dbo:wikiPageRevisionID
1116507398
dbo:wikiPageWikiLink
dbr:Index_set_(recursion_theory) dbc:Articles_containing_proofs dbr:Social_choice_theory dbr:Recursively_enumerable_set dbr:Recursive_set dbr:Halting_problem dbr:Nakamura_number dbr:If-then-else dbc:Undecidable_problems dbr:McGraw-Hill dbr:Admissible_numbering dbr:Unary_operation dbr:Semantics_(computer_science) dbr:Undecidable_problem dbr:Natural_numbers dbr:Introduction_to_Automata_Theory,_Languages,_and_Computation dbr:Partial_computable_function dbr:Gödel's_incompleteness_theorems dbr:Turing_machine dbr:Recursively_enumerable_language dbr:Reductio_ad_absurdum n18:Rice_reduction.svg dbr:Scott–Curry_theorem dbr:Quine_(computing) dbr:String_(computer_science) dbr:Hartley_Rogers,_Jr dbr:Turing's_proof dbr:Transactions_of_the_American_Mathematical_Society dbr:Syracuse_University dbr:Henry_Gordon_Rice dbr:Algorithm dbr:Partial_functions dbc:Theorems_in_theory_of_computation dbr:Cooperative_game_theory dbr:Regular_language dbr:Zero dbr:Gödel_number dbr:Algorithmic_game_theory dbr:Computable_function dbr:Computability_theory dbr:Recursion_theory dbr:Computational_social_choice dbr:Kleene's_recursion_theorem dbc:Theorems_in_the_foundations_of_mathematics dbr:Programming_language dbr:Wittgenstein_on_Rules_and_Private_Language dbr:Formal_language dbr:Roger's_equivalence_theorem dbr:Rice–Shapiro_theorem dbr:Addison-Wesley dbr:Decision_problem dbr:Finite_automaton
owl:sameAs
dbpedia-he:משפט_רייס dbpedia-pl:Twierdzenie_Rice’a yago-res:Rice's_theorem dbpedia-zh:莱斯定理 dbpedia-fr:Théorème_de_Rice freebase:m.06g1h dbpedia-es:Teorema_de_Rice dbpedia-it:Teorema_di_Rice dbpedia-pt:Teorema_de_Rice n25:pioE wikidata:Q1893717 dbpedia-nl:Stelling_van_Rice dbpedia-ja:ライスの定理 dbpedia-de:Satz_von_Rice dbpedia-ru:Теорема_Райса n31:Raiso_teorema
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Citation dbt:Math dbt:MathWorld dbt:Var
dbo:thumbnail
n15:Rice_reduction.svg?width=300
dbp:title
Rice's theorem
dbp:urlname
RicesTheorem
dbo:abstract
莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 De stelling van Rice is een belangrijke stelling in de theoretische informatica, meer in het bijzonder in de berekenbaarheidstheorie. Informeel zegt de stelling dat het onmogelijk is een algoritme te schrijven dat als invoer een ander algoritme en een bepaalde niet-triviale eigenschap krijgt en in alle gevallen correct beslist of het algoritme die eigenschap bezit. Uit de stelling volgt dat automatische verificatie van software in het algemeen niet mogelijk is. De stelling is genoemd naar de Amerikaanse logicus en wiskundige , die hem in 1954 in zijn proefschrift voor het eerst bewees. Теорема Райса — утверждение теории алгоритмов, согласно которому для любого нетривиального свойства вычислимых функций определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им. Названа по имени американского математика , доказавшего её в 1951 году в докторской диссертации. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств. ライスの定理（ライスのていり、英: Rice's theorem）は、計算機科学における計算可能関数の理論に関する定理で、定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。名称の由来は Henry Gordon Rice から。 In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function. Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University. Twierdzenie Rice’a – każda nietrywialna własność języków rekurencyjnie przeliczalnych jest nierozstrzygalna.Twierdzenie zawdzięcza swoją nazwę . Der Satz von Rice ist ein Ergebnis der Theoretischen Informatik. Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte.Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu entscheiden. Für spezielle Klassen von Algorithmen ist es zwar möglich – auch automatisiert – einzelne Eigenschaften nachzuweisen.Es gibt jedoch kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion ein gewünschtes, in einer üblichen formalen Sprache gegebenes Verhalten zeigt. Nella logica matematica, nella teoria della calcolabilità e nell'informatica teorica, il teorema di Rice costituisce un importante risultato nella teoria delle funzioni ricorsive e delle funzioni calcolabili (le due sono la stessa cosa, secondo la tesi di Church-Turing).Esso afferma che, per ogni proprietà non banale delle funzioni calcolabili, è non decidibile il problema di decidere quali funzioni soddisfino tale proprietà e quali no.Per proprietà banale in questo caso si intende una proprietà che non effettua alcuna discriminazione tra le funzioni calcolabili, cioè che vale o per tutte o per nessuna. Il teorema prende il nome da , il quale ne fornì la dimostrazione nel 1951 nella sua tesi di dottorato presso la Syracuse University. En teoría de la computación, el teorema de Rice es un teorema enunciado por y luego generalizado junto con y a lo que se conoce como el . Básicamente se puede enunciar el teorema de la siguiente manera: Dada una propiedad no trivial de las funciones parciales, no es computable determinar si una función arbitraria la posee o no.​ Es un típico problema de decisión que no se puede resolver, al igual que el problema de la parada. Na teoria da computação, o teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade. Aqui, uma propriedade de funções parciais é chamada trivial se ela vale para todas as funções parciais computáveis ou nenhuma, e um método de decisão eficaz é chamado geral se este decide corretamente para cada algoritmo. O teorema tem o nome de , é também conhecido como Teorema de Rice-Myhill-Shapiro. No título do teorema, depois de Rice, temos os matemáticos John Myhill e . En informatique théorique, plus précisément en théorie de la calculabilité, le théorème de Rice énonce que toute propriété sémantique non triviale d'un programme est indécidable. Le théorème de Rice généralise l'indécidabilité du problème de l'arrêt. Le théorème est classique et fait l'objet d'exercices dans certains ouvrages de théorie de la calculabilité. Il a une certaine portée philosophique vis-à-vis de la calculabilité et est dû au logicien Henry Gordon Rice.
prov:wasDerivedFrom
wikipedia-en:Rice's_theorem?oldid=1116507398&ns=0
dbo:wikiPageLength
20525
foaf:isPrimaryTopicOf
wikipedia-en:Rice's_theorem
Subject Item
dbr:Turing_completeness
dbo:wikiPageWikiLink
dbr:Rice's_theorem
Subject Item
dbr:Rice–Myhill–Shapiro_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rice-Myhill-Shapiro_Theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rice_s_Theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rice_theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
dbr:Rices_Theorem
dbo:wikiPageWikiLink
dbr:Rice's_theorem
dbo:wikiPageRedirects
dbr:Rice's_theorem
Subject Item
wikipedia-en:Rice's_theorem
foaf:primaryTopic
dbr:Rice's_theorem