Diferència entre revisions de la pàgina «Decisió, problema de la»
De Wikisofia
m (bot: - no ho hi ha, + no n'hi ha,) |
m (bot: - ordre. Veure: + ordre. Vegeu:) |
||
| (Hi ha una revisió intermèdia del mateix usuari que no es mostren) | |||
| Línia 2: | Línia 2: | ||
|Titulo=Problema de la decisió | |Titulo=Problema de la decisió | ||
}} | }} | ||
| − | (L'anomenat ''Entscheidungsproblem'') El de si es disposa o no, per a un enunciat o fórmula qualsevol d'un [[sistema formal|sistema formal]], d'un [[procediment de decisió|procediment de decisió]] efectiu, o d'un [[algorisme|algorisme]], per determinar si la fórmula o l'enunciat en qüestió constitueixen una [[fórmula universalment vàlida|veritat universalment vàlida]] (o un teorema) del sistema. Hi ha procediment de decisió per a la lògica d'enunciats i la lògica de predicats (monàdics) però, no n'hi ha, segons el [[teorema de Church|teorema de Church]], de 1936, per la [[lògica]] de predicats de primer ordre. | + | (L'anomenat ''Entscheidungsproblem'') El de si es disposa o no, per a un enunciat o fórmula qualsevol d'un [[sistema formal|sistema formal]], d'un [[procediment de decisió|procediment de decisió]] efectiu, o d'un [[algorisme|algorisme]], per a determinar si la fórmula o l'enunciat en qüestió constitueixen una [[fórmula universalment vàlida|veritat universalment vàlida]] (o un teorema) del sistema. Hi ha procediment de decisió per a la lògica d'enunciats i la lògica de predicats (monàdics) però, no n'hi ha, segons el [[teorema de Church|teorema de Church]], de 1936, per la [[lògica]] de predicats de primer ordre. |
| − | + | Vegeu: [[decidibilitat|decidibilitat]], [[indecibilitat|indecidibilitat]]. | |
{{Etiqueta | {{Etiqueta | ||
Revisió de 22:34, 17 maig 2018
(L'anomenat Entscheidungsproblem) El de si es disposa o no, per a un enunciat o fórmula qualsevol d'un sistema formal, d'un procediment de decisió efectiu, o d'un algorisme, per a determinar si la fórmula o l'enunciat en qüestió constitueixen una veritat universalment vàlida (o un teorema) del sistema. Hi ha procediment de decisió per a la lògica d'enunciats i la lògica de predicats (monàdics) però, no n'hi ha, segons el teorema de Church, de 1936, per la lògica de predicats de primer ordre.
Vegeu: decidibilitat, indecidibilitat.