About: Rice's theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Rice's theorem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Theorem106752293, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/c/8prPeZJntX

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.

Attributes	Values
rdf:type	yago:WikicatMathematicalTheorems yago:WikicatMathematicalTheoremsInTheoreticalComputerScience yago:WikicatTheorems yago:WikicatTheoremsInTheFoundationsOfMathematics yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293
rdfs:label	Satz von Rice (de) Teorema de Rice (es) Théorème de Rice (fr) Teorema di Rice (it) Stelling van Rice (nl) ライスの定理 (ja) Twierdzenie Rice’a (pl) Rice's theorem (en) Teorema de Rice (pt) Теорема Райса (ru) 莱斯定理 (zh)
rdfs:comment	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. (es) 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. (fr) 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. (it) ライスの定理（ライスのていり、英: Rice's theorem）は、計算機科学における計算可能関数の理論に関する定理で、定められた性質Fを満たすかどうかを任意の部分計算可能関数について判定する方法は(Fが自明な場合を除いて)存在しない、というもの。名称の由来は Henry Gordon Rice から。 (ja) 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. (nl) Twierdzenie Rice’a – każda nietrywialna własność języków rekurencyjnie przeliczalnych jest nierozstrzygalna.Twierdzenie zawdzięcza swoją nazwę . (pl) 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 . (pt) 莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 (zh) Теорема Райса — утверждение теории алгоритмов, согласно которому для любого нетривиального свойства вычислимых функций определение того, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им. Названа по имени американского математика , доказавшего её в 1951 году в докторской диссертации. Изначально доказана для частично-рекурсивных функций, существует аналог теоремы для рекурсивных множеств. (ru) 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. (de) 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. (en)
foaf:depiction
dcterms:subject	Articles containing proofs Undecidable problems Theorems in theory of computation Theorems in the foundations of mathematics
Wikipage page ID	25852 (xsd:integer)
Wikipage revision ID	1116507398 (xsd:integer)
Link from a Wikipage to another Wikipage	Hartley Rogers, Jr Algorithm Algorithmic game theory Unary operation Decision problem Introduction to Automata Theory, Languages, and Computation Reductio ad absurdum Articles containing proofs Computability theory Computable function McGraw-Hill Scott–Curry theorem Cooperative game theory Computational social choice Zero Henry Gordon Rice String (computer science) Admissible numbering Undecidable problems Turing's proof Theorems in theory of computation Recursively enumerable language Addison-Wesley Theorems in the foundations of mathematics Partial functions Formal language Social choice theory Quine (computing) Regular language Gödel's incompleteness theorems Halting problem Syracuse University Index set (recursion theory) Natural numbers Recursive set Recursively enumerable set Kleene's recursion theorem If-then-else Turing machine Semantics (computer science) Undecidable problem Programming language Wittgenstein on Rules and Private Language Nakamura number Rice–Shapiro theorem Roger's equivalence theorem Transactions of the American Mathematical Society Finite automaton Partial computable function Recursion theory Gödel number
sameAs	Rice's theorem Rice's theorem Rice's theorem Rice's theorem Rice's theorem Rice's theorem Rice's theorem Rice's theorem Rice's theorem

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3332 as of Dec 5 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 71 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software