| dbo:abstract
|
- El Entscheidungsproblem (en català: problema de decisió) fou el repte en lògica simbòlica de trobar un algorisme que decidís si una fórmula de és un teorema. El 1936, de manera independent, Alonzo Church i Alan Turing demostraren que és impossible escriure tal algorisme. Com a conseqüència, és també impossible decidir amb un algorisme si una frase qualsevol de l'aritmètica és certa o falsa. La pregunta es remunta a Gottfried Leibniz, qui en el segle xvii, després de construir amb èxit una màquina mecànica de càlcul, somiava construir una màquina que pogués manipular símbols per a determinar si una frase en matemàtiques és un teorema. El primer que seria necessari és un llenguatge formal clar i precís, i molt del seu treball posterior es dirigí cap aquest objectiu. El 1928, David Hilbert i Wilhelm Ackermann proposaren la pregunta en la seva formulació anteriorment mencionada. Una fórmula lògica de primer ordre és anomenada universalment vàlida o lògicament vàlida si es dedueix dels axiomes del . El teorema de completitut de Gödel estableix que una fórmula lògica és universalment vàlida en aquest sentit si i només si és certa en tota la interpretació de la fórmula en un model. Abans de poder respondre a aquesta pregunta, es va haver de definir formalment la noció d'algorisme. Això fou realitzat per Alonzo Church el 1936 amb el concepte de "calculabilitat efectiva" basada en el seu càlcul lambda i per Alan Turing basant-se en la seva màquina de Turing. Els dos enfocaments són equivalents en el sentit que poden resoldre exactament els mateixos problemes amb ambdós enfocaments. La resposta negativa al Entscheidungsproblem fou donada per Alonzo Church el 1936 i independentment, molt poc després per Alan Turing, també el 1936. Church va demostrar que no existeix algorisme (definit basant-se en ) que decideixi per dos expressions de càlcul lambda si són equivalents o no. Church per això es va basar en el trebal previ de Stephen Kleene. Per altra part, Turing va reduir aquest problema al problema de la parada per les màquines de Turing. Generalment es considera que la prova de Turing ha tingut més influència que la de Church. Ambdós treballs es veieren influïts pels treballs anteriors de Kurt Gödel sobre el teorema d'incompletitut, especialment pel mètode d'assignar nombres a les fórmules lògiques per a poder reduir la lògica a l'aritmètica. L'argument de Turing és com segueix: Suposem que es té un algorisme general de decisió per la lògica de primer ordre. Es pot traduir la pregunta si una màquina de Turing acaba com una fórmula de primer ordre, que llavors podria ser sotmesa a l'algorisme de decisió. Però Turing ja havia demostrat que no existeix algorisme general que pugui decidir si una màquina de Turing es para. És important notar que si es restringeix el problema a una teoria de primer ordre específica amb constants, predicats constants i axiomes, és possible que existeixin algorismes de decisions per la teoria. Alguns exemples de teories decidibles són: l' i els dels Llenguatges de programació. En canvi, la teoria general de primer ordre per als nombres naturals coneguda com l'aritmètica de Peano no pot ser decidida amb aquest tipus d'algorisme. Això es dedueix de l'argument de Turing resumit més amunt. (ca)
- Entscheidungsproblem (německý výraz pro „rozhodovací problém“) je úloha, kterou poprvé předložil německý matematik David Hilbert roku 1928. Ptá se, existuje-li postup (algoritmus), který by uměl rozhodnout, jestli je dané matematické tvrzení v daném formálním jazyce nebo . Alonzo Church (1936) a Alan Turing (1937) nezávisle na sobě dokázali, že takový algoritmus neexistuje. (cs)
- في الرياضيات تعد Entscheidungsproblem (تنطق [ɛntˈʃaɪdʊŋspʁoˌble:m], في الألمانية وتعني «مشكلة القرار») هو التحدي الذي يطرحه ديفيد هيلبرت عام 1928. Entscheidungsproblem تسأل عن خوارزمية التي ستتخذ وصفا للغة الرسمية وبيانا رياضيا في اللغة كمدخل وتقدم إما «صواب» أو «خطأ» كمخرج وفقا لصحة أو خطا البيان. الحاجة للخوارزمية لا تبرر لا إجابتها ولا تقدم دليلا ما دام صحيحا دائما. مثل هذه الخوارزمية تستطيع أن تقرر، على سبيل المثال، ما إذا كانت البيانات مثل حدسية غولدباخ أو فرضية ريمانصحيحة حتى لو لم يوجد دليل أو نقض معروف عن هذه البيانات. وكثيرا ما تم تحديد Entscheidungsproblem خاصة بأنها مشكلة قرار منطق الرتبة الأولى (وهذا يعني أن مشكلة تحديد، من الناحية الحسابية، ما إذا كان البيان من المرتبة الأولى صحيحا عالميا).في عامي 1936 و 1937 نشر ألونزو تشرتش وآلان تورنغ على الترتيب صحفا مستقلة تبين أنه من المستحيل تقرير حسابيا ما إذا كانت البيانات في حسابيات صحيحة أم خاطئة وبالتالي فالحل العام ل Entscheidungsproblem أمرا مستحيلا. هذه النتيجة معروفة الآن بنظرية تشرتش أو نظرية تشرتش تورنغ (ينبغي عدم الخلط بينها وبين رسالة تشرتش تورنغ). (ar)
- En ciencias de la computación y matemáticas, el Entscheidungsproblem (en español: problema de decisión) fue el reto en lógica simbólica de encontrar un algoritmo general que decidiese si una fórmula del cálculo de primer orden es un teorema. En 1936, de manera independiente, Alonzo Church y Alan Turing demostraron ambos que es imposible escribir tal algoritmo. Como consecuencia, es también imposible decidir con un algoritmo si ciertas frases concretas de la aritmética son ciertas o falsas. La pregunta se remonta a Gottfried Leibniz, quien en el siglo XVII, después de construir exitosamente una máquina mecánica de cálculo, soñaba con construir una máquina que pudiera manipular símbolos para determinar si una frase en matemáticas es un teorema. Lo primero que sería necesario es un lenguaje formal claro y preciso, y mucho de su trabajo posterior se dirigió hacia ese objetivo. En 1928, David Hilbert y Wilhelm Ackermann propusieron la pregunta en su formulación anteriormente mencionada. Una fórmula lógica de primer orden es llamada universalmente válida o lógicamente válida si se deduce de los axiomas del cálculo de primer orden. El teorema de completitud de Gödel establece que una fórmula lógica es universalmente válida en este sentido si y sólo si es cierta en toda interpretación de la fórmula en un modelo. Antes de poder responder a esta pregunta, hubo que definir formalmente la noción de algoritmo. Esto fue realizado por Alonzo Church en 1936 con el concepto de "calculabilidad efectiva" basada en su cálculo lambda y por Alan Turing basándose en la máquina de Turing. Los dos enfoques son equivalentes, en el sentido en que se pueden resolver exactamente los mismos problemas con ambos enfoques. La respuesta negativa al Entscheidungsproblem fue dada por Alonzo Church en 1936 e independientemente, muy poco tiempo después por Alan Turing, también en 1936. Church demostró que no existe algoritmo (definido según las funciones recursivas) que decida para dos expresiones del cálculo lambda si son equivalentes o no. Church para esto se basó en trabajo previo de Stephen Kleene. Por otra parte, Turing redujo este problema al problema de la parada para las máquinas de Turing. Generalmente se considera que la prueba de Turing ha tenido más influencia que la de Church. Ambos trabajos se vieron influidos por trabajos anteriores de Kurt Gödel sobre el teorema de incompletitud, especialmente por el método de asignar números a las fórmulas lógicas para poder reducir la lógica a la aritmética. El argumento de Turing es como sigue: Supóngase que se tiene un algoritmo general de decisión para la lógica de primer orden. Se puede traducir la pregunta sobre si una máquina de Turing termina como una fórmula de primer orden, que entonces podría ser sometida al algoritmo de decisión. Pero Turing ya había demostrado que no existe algoritmo general que pueda decidir si una máquina de Turing se para. Es importante notar que si se restringe el problema a una teoría de primer orden específica con constantes, predicados constantes y axiomas, es posible que exista un algoritmo de decisión para la teoría. Algunos ejemplos de teorías decidibles son: la y los sistemas estáticos de tipos de los Lenguajes de programación. Sin embargo, la teoría general de primer orden para los números naturales conocida como la aritmética de Peano no puede ser decidida con ese tipo de algoritmo. Esto se deduce del argumento de Turing resumido más arriba. (es)
- In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. (en)
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). Le problème de la décision est un exemple de problème de décision : une question de décidabilité au sens algorithmique. Ici la question est celle de la décidabilité du calcul des prédicats égalitaire du premier ordre : l'ensemble des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ? Le problème de la décision dépend en fait du choix du langage du premier ordre : sa signature, les « briques » de base qui permettent la construction des énoncés, les symboles de constantes, de fonctions (ou opérations), et de prédicat (par exemple 0, +, ≤…). Dans un langage donné (exemple : dans l'arithmétique de Peano, c'est le langage arithmétique), une solution positive AU problème de la décision fournit une solution positive AUX problèmes de la décision pour toutes les théories finiment axiomatisables de ce langage. En effet, un énoncé C se déduit d'un système fini d'axiomes si et seulement si on peut dériver en logique pure que la conjonction de ces axiomes entraîne C. (fr)
- In de wiskunde en informatica is het zogeheten Entscheidungsproblem (Duits voor 'beslissingsprobleem') een uitdaging van David Hilbert in 1928. Het Entscheidungsproblem vraagt om een algoritme dat als invoer een uitspraak in een eerste-ordelogica (eventueel met een eindig aantal axioma's in plaats van de gebruikelijke axioma's van de eerste-ordelogica) krijgt en antwoordt met "ja" of "nee" al naargelang de uitspraak universeel geldig is of niet, dat wil zeggen, geldig in elke structuur die voldoet aan de axioma's. Vanwege de Volledigheidsstelling van Gödel is een uitspraak slechts dan universeel geldig als hij kan worden afgeleid uit de axioma's, zodat het Entscheidungsproblem ook kan worden gezien als de vraag naar een algoritme om te beslissen of een bepaalde uitspraak bewijsbaar is vanuit de axioma's met behulp van de regels van de logica. In 1936 publiceerden Alonzo Church en Alan Turing onafhankelijk van elkaar artikelen die aantonen dat een algemene oplossing voor het Entscheidungsproblem niet mogelijk is, ervan uitgaande dat het intuïtieve begrip '' gedekt wordt door functies die berekenbaar zijn door een turingmachine. Deze veronderstelling is nu bekend als de Church-Turing-hypothese. (nl)
- L'Entscheidungsproblem (in italiano: "problema della decisione") è un problema posto da David Hilbert nel 1928, all'interno dell'allora fervente dibattito sui fondamenti della matematica. Il problema consiste nel chiedere di esibire una procedura, eseguibile del tutto meccanicamente, in grado di stabilire, per ogni formula espressa nel linguaggio formale della logica del primo ordine, se tale formula è o meno un teorema della logica del primo ordine: in altri termini, se tale enunciato è o meno deducibile all'interno del sistema formale. Una risposta negativa al problema venne data da Alonzo Church nel 1936 e da Alan Turing, indipendentemente, pochi mesi dopo, in due lavori che, insieme, costituiscono le basi per la fondazione della teoria della computabilità. (it)
- O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado. Em , trabalhando independentemente, Alonzo Church e Alan Turing mostraram que é impossível decidir algoritmicamente se um enunciado na lógica de primeira ordem é verdadeiro ou falso. A questão retoma a Gottfried Leibniz, que no século XVII, depois de construir uma máquina de calcular mecânica, sonhou em construir uma máquina que pudesse manipular símbolos a fim de determinar os valores de verdade dos enunciados matemáticos. Ele percebeu que o primeiro passo teria que ser uma linguagem formal precisa, e muito do seu trabalho subsequente foi nesse sentido. Em 1928, David Hilbert e Wilhelm Ackermann propuseram tal questão da forma mostrada logo abaixo. Um enunciado de primeira ordem é chamado "universalmente válido" ou "logicamente válido" se segue dos axiomas do cálculo de predicados de primeira ordem. O Teorema da completude de Gödel indica que um enunciado é universalmente válido se, e somente se, é verdadeiro em toda interpretação num modelo. Na continuação do seu "programa" com o qual ele desafiou a comunidade matemática em 1900, na Conferência Internacional de 1928 David Hilber fez três questionamentos, ficando o terceiro conhecido como "O problema de decisão de Hilbert" ("Hilbert's Entscheidungsproblem") [Hodges p.91]. Em meados de 1930 ele acreditava que não existiria um problema insolúvel (Hodges p.92, citando Hilbert). Antes que a questão pudesse ser respondida, a noção de "algoritmo" tinha que ser formalmente definida. Isso foi feito por Alonzo Church em 1936 com o conceito de "calculabilidade efetiva", baseada no seu cálculo λ , e por Alan Turing, no mesmo ano, com o seu conceito de Máquinas de Turing. As duas abordagens são equivalentes, uma instância da Tese de Church-Turing. A resposta negativa ao Entscheidungsproblem foi dada por Alonzo Church em 1936 e, logo em seguida, de forma independente, por Alan Turing, também em 1936. Church provou que não existe algoritmo (função computável) que decide para duas expressões do cálculo λ se elas são equivalentes ou não. Ele se baseou no trabalho anterior de Stephen Kleene. Turing reduziu o problema da parada para as Máquinas de Turing ao Entscheidungsproblem, e o seu artigo é considerado muito mais influente do que o de Church. O trabalho de ambos autores foi muito influenciado por Kurt Gödel e o seu teorema da completude, principalmente pela enumeração de Gödel para fórmulas lógicas a fim de reduzir a lógica a aritmética. A seguir o argumento de Turing. Suponha que temos um algoritmo de decisão genérico para a lógica de primeira ordem. A questão se uma determinada Máquina de Turing pára ou não pode ser formulada como um enunciado de primeira ordem, o qual seria suscetível ao algoritmo de decisão. Mas Turing provou anteriormente que nenhum algoritmo genérico pode decidir se uma determinada Máquina de Turing pára. O Entscheidungsproblem é relacionado ao "Décimo problema de Hilbert", que pede a um algoritmo decidir se uma equação diofantina tem solução. A não-existência de tal algoritmo (provado por Yuri Matiyasevich em 1970) implica numa resposta negativa ao Entscheidungsproblem. (veja Teorema de Matiyasevich) É importante perceber que se nós nos restringirmos a uma teoria de primeira ordem específica com objetos específicos constantes, funções constantes, predicados constantes e axiomas subjetivos, a verdade dos enunciados nessa teoria pode muito bem ser algoritmicamente decidível. Exemplos disso incluem Aritmética de Presburger, campos reais fechados e tipos de variáveis em linguagens de programação. Entretanto, a teoria de primeira ordem dos números naturais expressa nos axiomas de Peano não pode ser decidida por tal algoritmo. Isso segue do argumento de Turing mostrado acima. (pt)
- Inom matematik och datavetenskap är Avgörbarhetsproblemet eller Entscheidungsproblemet (av tyskans Entscheidung 'beslut') en fråga som ursprungligen formulerades av David Hilbert 1928: Enligt för första ordningens logik är en utsaga universellt giltig om och endast om den kan härledas från dess axiom, så avgörbarhetsproblemet kan också ses som frågan om huruvida en utsaga är bevisbar utifrån axiomen eller inte. År 1936 respektive 1937 publicerade Alonzo Church och Alan Turing oberoende av varandra artiklar som visar att en allmän lösning på avgörbarhetsproblemet inte existerar. Dessa resultat är nu känd som Churchs teorem och Church-Turings hypotes. Avgörbarhetsproblemet har beröring med Hilberts tionde problem angående algoritmer för lösningar till Diofantiska ekvationer. Avsaknaden av någon sådan algoritm, fastställt av 1970, innebär också ett negativt svar på avgörbarhetsproblemet. (sv)
- Проблема разрешения (нем. Entscheidungsproblem) — задача из области оснований математики, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения «» на этом языке) — и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!», — в зависимости от того, истинно или ложно утверждение «». Ответ не требует обоснований, но должен быть верным. Такой алгоритм мог бы, к примеру, подтвердить гипотезу Гольдбаха и гипотезу Римана несмотря на то, что доказательства (и опровержения) пока неизвестны. Нерешаемость проблемы разрешения (неразрешимость множества истинных формул арифметики) для языка арифметики, содержащего «равенство», «сложение» и «умножение», является следствием неарифметичности этого множества. Неарифметичность является следствием теоремы Тарского «о невыразимости понятия истинности в языке средствами того же языка». В 1936 году — Алонзо Чёрч и независимо от него Алан Тьюринг опубликовали работы, в которых показали, что не существует алгоритма для определения истинности утверждений арифметики, а поэтому и более общая проблема разрешения также не имеет решения. Этот результат получил название: «теорема Чёрча — Тьюринга». (ru)
- 一个语言，是一个集合，且其补集为 。当是图灵机可识别时，语言则称为半可判定。当语言不是图灵机可识别，则为不可判定语言。当且仅当和都是图灵机可识别的时候，L才能称为可判定语言。 (zh)
- В математиці пробле́ма розв'я́зності (нім. Entscheidungsproblem) — проблема, сформульована Давидом Гільбертом 1928 року: знайти алгоритм, який би брав як вхідні дані опис формальної мови та математичного твердження цією мовою, і після скінченного числа кроків зупинявся би й видавав одну з двох відповідей: «Істина» або «Хиба», залежно від того, чи є твердження істинним, чи хибним. Не потрібно, щоб алгоритм давав якесь обґрунтування своєї відповіді, проте відповідь завжди має бути вірною. Такий алгоритм міг би, наприклад, визначити, чи є правдивими такі твердження, як гіпотеза Гольдбаха або гіпотеза Рімана, попри те, що жодного доведення (або спростування) цих тверджень поки не відомо. 1936 року Алонзо Черч та Алан Тюринг опублікували праці, в яких показали, що не існує алгоритму для визначення істинності тверджень арифметики, а відтак і загальніша проблема розв'язання також не має розв'язку. Цей результат отримав назву теза Черча — Тюрінга. (uk)
|
| rdfs:comment
|
- Entscheidungsproblem (německý výraz pro „rozhodovací problém“) je úloha, kterou poprvé předložil německý matematik David Hilbert roku 1928. Ptá se, existuje-li postup (algoritmus), který by uměl rozhodnout, jestli je dané matematické tvrzení v daném formálním jazyce nebo . Alonzo Church (1936) a Alan Turing (1937) nezávisle na sobě dokázali, že takový algoritmus neexistuje. (cs)
- In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. (en)
- 一个语言，是一个集合，且其补集为 。当是图灵机可识别时，语言则称为半可判定。当语言不是图灵机可识别，则为不可判定语言。当且仅当和都是图灵机可识别的时候，L才能称为可判定语言。 (zh)
- في الرياضيات تعد Entscheidungsproblem (تنطق [ɛntˈʃaɪdʊŋspʁoˌble:m], في الألمانية وتعني «مشكلة القرار») هو التحدي الذي يطرحه ديفيد هيلبرت عام 1928. Entscheidungsproblem تسأل عن خوارزمية التي ستتخذ وصفا للغة الرسمية وبيانا رياضيا في اللغة كمدخل وتقدم إما «صواب» أو «خطأ» كمخرج وفقا لصحة أو خطا البيان. الحاجة للخوارزمية لا تبرر لا إجابتها ولا تقدم دليلا ما دام صحيحا دائما. مثل هذه الخوارزمية تستطيع أن تقرر، على سبيل المثال، ما إذا كانت البيانات مثل حدسية غولدباخ أو فرضية ريمانصحيحة حتى لو لم يوجد دليل أو نقض معروف عن هذه البيانات. وكثيرا ما تم تحديد Entscheidungsproblem خاصة بأنها مشكلة قرار منطق الرتبة الأولى (وهذا يعني أن مشكلة تحديد، من الناحية الحسابية، ما إذا كان البيان من المرتبة الأولى صحيحا عالميا).في عامي 1936 و 1937 نشر ألونزو تشرتش وآلان تورنغ على الترتيب صحفا مستقلة تبين أنه من الم (ar)
- El Entscheidungsproblem (en català: problema de decisió) fou el repte en lògica simbòlica de trobar un algorisme que decidís si una fórmula de és un teorema. El 1936, de manera independent, Alonzo Church i Alan Turing demostraren que és impossible escriure tal algorisme. Com a conseqüència, és també impossible decidir amb un algorisme si una frase qualsevol de l'aritmètica és certa o falsa. (ca)
- En ciencias de la computación y matemáticas, el Entscheidungsproblem (en español: problema de decisión) fue el reto en lógica simbólica de encontrar un algoritmo general que decidiese si una fórmula del cálculo de primer orden es un teorema. En 1936, de manera independiente, Alonzo Church y Alan Turing demostraron ambos que es imposible escribir tal algoritmo. Como consecuencia, es también imposible decidir con un algoritmo si ciertas frases concretas de la aritmética son ciertas o falsas. (es)
- En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle). De façon équivalente par le théorème de complétude, il s'agit finalement de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). (fr)
- L'Entscheidungsproblem (in italiano: "problema della decisione") è un problema posto da David Hilbert nel 1928, all'interno dell'allora fervente dibattito sui fondamenti della matematica. Il problema consiste nel chiedere di esibire una procedura, eseguibile del tutto meccanicamente, in grado di stabilire, per ogni formula espressa nel linguaggio formale della logica del primo ordine, se tale formula è o meno un teorema della logica del primo ordine: in altri termini, se tale enunciato è o meno deducibile all'interno del sistema formale. (it)
- In de wiskunde en informatica is het zogeheten Entscheidungsproblem (Duits voor 'beslissingsprobleem') een uitdaging van David Hilbert in 1928. Het Entscheidungsproblem vraagt om een algoritme dat als invoer een uitspraak in een eerste-ordelogica (eventueel met een eindig aantal axioma's in plaats van de gebruikelijke axioma's van de eerste-ordelogica) krijgt en antwoordt met "ja" of "nee" al naargelang de uitspraak universeel geldig is of niet, dat wil zeggen, geldig in elke structuur die voldoet aan de axioma's. Vanwege de Volledigheidsstelling van Gödel is een uitspraak slechts dan universeel geldig als hij kan worden afgeleid uit de axioma's, zodat het Entscheidungsproblem ook kan worden gezien als de vraag naar een algoritme om te beslissen of een bepaalde uitspraak bewijsbaar is vanu (nl)
- Проблема разрешения (нем. Entscheidungsproblem) — задача из области оснований математики, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения «» на этом языке) — и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!», — в зависимости от того, истинно или ложно утверждение «». Ответ не требует обоснований, но должен быть верным. (ru)
- Inom matematik och datavetenskap är Avgörbarhetsproblemet eller Entscheidungsproblemet (av tyskans Entscheidung 'beslut') en fråga som ursprungligen formulerades av David Hilbert 1928: Enligt för första ordningens logik är en utsaga universellt giltig om och endast om den kan härledas från dess axiom, så avgörbarhetsproblemet kan också ses som frågan om huruvida en utsaga är bevisbar utifrån axiomen eller inte. (sv)
- O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado. Em , trabalhando independentemente, Alonzo Church e Alan Turing mostraram que é impossível decidir algoritmicamente se um enunciado na lógica de primeira ordem é verdadeiro ou falso. Entretanto, a teoria de primeira ordem dos números naturais expressa nos axiomas de Peano não pode ser decidida por tal algoritmo. Isso segue do argumento de Turing mostrado acima. (pt)
- В математиці пробле́ма розв'я́зності (нім. Entscheidungsproblem) — проблема, сформульована Давидом Гільбертом 1928 року: знайти алгоритм, який би брав як вхідні дані опис формальної мови та математичного твердження цією мовою, і після скінченного числа кроків зупинявся би й видавав одну з двох відповідей: «Істина» або «Хиба», залежно від того, чи є твердження істинним, чи хибним. Не потрібно, щоб алгоритм давав якесь обґрунтування своєї відповіді, проте відповідь завжди має бути вірною. Такий алгоритм міг би, наприклад, визначити, чи є правдивими такі твердження, як гіпотеза Гольдбаха або гіпотеза Рімана, попри те, що жодного доведення (або спростування) цих тверджень поки не відомо. (uk)
|