| dbo:abstract
|
- 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. (de)
- 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)
- 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. (en)
- 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)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20525 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| 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)
|
| 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)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
