Halting problem (original) (raw)
En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal: donada una descripció d'un programa i el seu estat inicial, determinar si el programa, quan executa aquesta entrada, s'atura (completa). L'alternativa és que funciona per sempre sense aturar-se Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir. Es diu que el problema de la parada és indecidible amb màquines de Turing.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal: donada una descripció d'un programa i el seu estat inicial, determinar si el programa, quan executa aquesta entrada, s'atura (completa). L'alternativa és que funciona per sempre sense aturar-se Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir. Es diu que el problema de la parada és indecidible amb màquines de Turing. (ca) Problém zastavení (halting problem) je úloha teorie vyčíslitelnosti, která může být neformálně zadána takto: Znáte-li zdrojový kód programu a jeho vstup, rozhodněte, zda program zastaví, nebo zda poběží navždy bez zastavení. V roce 1936 Alan Turing dokázal, že obecný algoritmus, který by řešil problém zastavení pro všechny vstupy všech programů, neexistuje. Problém zastavení se proto označuje jako algoritmicky nerozhodnutelný problém. Je však částečně rozhodnutelný, což lze ukázat simulací univerzálním Turingovým strojem, který zastaví, pokud simulovaný TS normálně či abnormálně zastavil. (cs) مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير. (ar) Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο Άλαν Τιούρινγκ, το 1936, απέδειξε ότι δεν υπάρχει κάποιος γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου. Κομμάτι κλειδί της απόδειξης ήταν ένας μαθηματικός ορισμός ενός υπολογιστικού προγράμματος, γνωστού ως μηχανή Τιούρινγκ. Το πρόβλημα τερματισμού είναι στις μηχανές Turing. Είναι ένα από τα πρώτα παραδείγματα προβλήματος απόφασης. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον . (el) Problemo de halto estas tasko de , kiu povas esti neformale donita jene: Se vi konas fontkodon de programo kaj ties eniron, decidu, ĉu la programo haltos aŭ ĉu ĝi funkcios por ĉiam sen halto. En la jaro 1936 Alan Turing pruvis, ke ĝenerala algoritmo, kiu solvus la problemon de halto por ĉiuj eniroj de ĉiuj programoj, ne ekzistas. La problemo de halto tial estas markata kiel algoritme . (eo) Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt werden, entsteht eine Berechnungsvorschrift, ein sogenannter Algorithmus. Zur Ausführung von Algorithmen benutzt man in der theoretischen Informatik abstrakte Maschinen. Eine typische abstrakte Maschine ist die Turingmaschine.Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt. Obwohl das für viele Algorithmen leicht beantwortet werden kann, konnte der Mathematiker Alan Turing beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Diesen Beweis vollzog er an einer Turingmaschine.Das Halteproblem ist somit algorithmisch nicht entscheidbar. Das Resultat spielt eine grundlegende Rolle in der Berechenbarkeitstheorie.Der Begriff Halteproblem wurde nicht von Turing geprägt, sondern erst später durch Martin Davis in seinem Buch Computability and Unsolvability. (de) El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing y una palabra , determinar si terminará en un número finito de pasos cuando es ejecutada usando como dato de entrada.Alan Turing, en su famoso artículo «On Computable Numbers, with an Application to the Entscheidungsproblem» (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible (no computable o no recursivo), en el sentido de que ninguna máquina de Turing lo puede resolver. (es) In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program–input pairs cannot exist. For any program f that might determine whether programs halt, a "pathological" program g, called with some input, can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case. A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly. Jack Copeland attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s. (en) En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non. Alan Turing a montré en 1936 que le problème de l'arrêt est indécidable, c'est-à-dire qu'il n'existe pas de programme informatique qui prend comme entrée une description d'un programme informatique et un paramètre et qui, grâce à la seule analyse de ce code, répond VRAI si le programme s'arrête sur son paramètre et FAUX sinon. Une partie importante de la démonstration a été la formalisation du concept de programmes informatiques : les machines de Turing. En pratique, il n'y a donc pas de méthode générale d'analyse statique capable de déterminer si un programme boucle indéfiniment ou non, bien qu'il soit cependant possible pour certaines séquences de codes identifiables de s'assurer que la construction génère potentiellement une boucle infinie. Ce résultat est généralisé par le théorème de Rice à de nombreuses autres propriétés concernant l'analyse des programmes. (fr) 計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。 アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。 (ja) Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato ingresso finito, stabilire se l'algoritmo in questione termina o continua la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale in grado di risolvere il problema per tutti i possibili ingressi. La versione più nota del problema è quella proposta nel 1936 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità. (it) 계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다. (ko) Het stopprobleem, ook bekend als het 'halting problem', is het beslissingsprobleem uit de wiskunde en informatica, om te bepalen of een algoritme bij een eindige invoer in een eindig aantal stappen eindigt of dat het eindeloos blijft doorgaan. Het is een bekend voorbeeld van een wiskundig probleem dat onbeslisbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd bewezen door Alan Turing in 1936. (nl) Problem stopu – zagadnienie algorytmiczne odpowiadające, dla danego algorytmu, na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu. Problem stopu bywa trudny do rozstrzygnięcia, przykładem może być sformułowany w prosty sposób problem Collatza, dla którego odpowiedź jest dotychczas nieznana. (pl) Stopproblemet eller haltproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som informellt kan beskrivas så här: Med en given beskrivning av ett program och dess indata, bestäm om programmet, när det utförs med indatat, någonsin stoppar (slutför beräkningen). Alternativet är att det fortsätter i evighet utan avbrott. En annan beskrivning av problemet lyder: Är det möjligt att inom ändlig tidsrymd med något program avgöra om ett godtyckligt program stannar för godtyckliga indata? Alan Turing visade 1936 att en allmän algoritm för att lösa stopproblemet för samtliga (program, indata)-par inte kan existera. Man säger att stopproblemet inte är rekursivt lösbart. (sv) Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём. В терминах функций проблему можно доступно описать следующим образом: Для любой функции F(G, start_state) которая может определять останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F, результат выполнения будет противоположен тому, который предсказывает F. Для многих других задач[каких?] можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима. (ru) Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: ''Dadas uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente.'' Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir. Dizemos que o problema da parada é indecidível nas Máquinas de Turing. (pt) В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно (uk) 停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。 (zh) |
| dbo:wikiPageExternalLink | https://archive.org/details/undecidablebasic0000davi%7C https://archive.org/details/introductiontoau00hopc%7C https://archive.org/details/introductiontoth00sips/page/173 http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimTeX/halt http://www.turingarchive.org/browse.php/B/12 http://motherboard.vice.com/read/does-the-halting-problem-mean-no-moral-robots http://dx.doi.org/10.1093/acprof:oso/9780199233212.001.0001%7Ctitle=The https://arxiv.org/abs/1411.2842 https://www.youtube.com/watch%3Fv=92WHN-pAFCs |
| dbo:wikiPageID | 21391870 (xsd:integer) |
| dbo:wikiPageLength | 50166 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123597048 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Entscheidungsproblem dbr:MISRA_C dbr:Bertrand_Russell dbr:Brainfuck dbr:David_Hilbert dbr:Algorithm dbc:Mathematical_problems dbr:Human_brain dbr:Hypercomputer dbr:Beta_normal_form dbr:Peano_Axioms dbr:Peano_axioms dbr:Character_(computing) dbr:Decision_problem dbc:1936_introductions dbr:Infinite_loop dbr:Interpreter_(computing) dbr:James_R._Newman dbr:Computability_theory_(computer_science) dbr:Computable_function dbr:Coq dbr:SPARK_(programming_language) dbr:Oracle_machine dbr:RE-complete dbr:Christopher_Strachey dbr:Church–Turing_thesis dbr:Enumeration dbr:General_recursive_function dbr:Correctness_(computer_science) dbr:Arithmetical_hierarchy dbr:Machine_that_always_halts dbr:Stephen_Kleene dbr:Computable_number dbr:Computation dbr:Computer_program dbr:Computer_scientist dbr:Partial_function dbr:Proposition dbr:Tag_system dbr:Markov_algorithm dbr:Brouwer–Hilbert_controversy dbr:Busy_Beaver dbr:Busy_beaver dbc:Undecidable_problems dbr:Total_function dbr:Transcendental_number dbr:Turing's_proof dbr:Turing_Machine dbr:Gödel_numbering dbr:Julia_Robinson dbr:Linear_bounded_automaton dbr:Alan_Turing dbr:Alfred_North_Whitehead dbr:Alonzo_Church dbr:Alphabet dbr:Data_type dbr:Ernest_Nagel dbr:Normal_number dbr:Numeral_system dbr:Kolmogorov_complexity dbr:Proof_by_contradiction dbr:Degree_of_unsolvability dbr:Natural_density dbr:Probability dbr:Real-time_computing dbr:Recursively_enumerable dbr:Reduction_(complexity) dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorem dbr:Hilbert's_problems dbr:International_Congress_of_Mathematicians dbr:J._Barkley_Rosser dbr:Jack_Copeland dbr:Taylor_Booth_(mathematician) dbc:Computability_theory dbc:Theory_of_computation dbr:Lambda_calculus dbr:Effective_method dbr:Heuristic_(computer_science) dbr:Termination_analysis dbr:Register_machine dbr:Martin_Davis_(mathematician) dbr:Marvin_Minsky dbr:Kurt_Gödel dbr:Natural_number dbr:Cantor's_diagonal_argument dbr:Reduction_(recursion_theory) dbr:Chaitin's_constant dbr:Self-referential dbr:Model_of_computation dbr:Turing_machine dbr:Undecidable_problem dbr:Universal_Turing_machine dbr:Worst-case_execution_time dbr:Formalism_(mathematics) dbr:Programming_language dbr:Rule_of_least_power dbr:Event_loop dbr:Pseudocode dbr:P_versus_NP_problem dbr:Rice's_theorem dbr:Turing_degree dbr:Primitive_recursive dbr:Halting_probability dbr:Turing-complete dbr:Chaitin dbr:Emil_Post dbr:Physical_process dbr:Programming_system dbr:Recursion_theory dbr:Definable_number dbr:Gentzen dbr:Post_system dbr:C2:HaltingProblem dbr:David_Bolter dbr:Edward_Beltrami |
| dbp:date | 1935-04-19 (xsd:date) 1936-10-07 (xsd:date) |
| dbp:event | Kleene includes a discussion of the unsolvability of the halting problem for Turing machines and reformulates it in terms of machines that "eventually stop", i.e. halt: "... there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops." (en) Church publishes the first proof that the Entscheidungsproblem is unsolvable. (en) In a paper, Stephen Kleene states that "In setting up a complete algorithmic theory, what we do is describe a procedure ... which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?'." (en) Alan Turing's paper On Computable Numbers With an Application to the Entscheidungsproblem went to press in May 1936 and reached print in January 1937. Turing's proof departs from calculation by recursive functions and introduces the notion of computation by machine. This is one of the "first examples of decision problems proved unsolvable". (en) J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing (en) Hilbert recasts his 'Second Problem' at the Bologna International Congress. He posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable? The third question is known as the Entscheidungsproblem . (en) Emil Post explores the halting problem for tag systems, regarding it as a candidate for unsolvability. Its unsolvability was not established until much later, by Marvin Minsky. (en) Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" (en) Martin Davis uses the term 'halting problem' in a series of lectures at the Control Systems Laboratory at the University of Illinois in 1952. It is likely that this is the first such use of the term. (en) Kurt Gödel announces a proof as an answer to the first two of Hilbert's 1928 questions. "At first he [Hilbert] was only angry and frustrated, but then he began to try to deal constructively with the problem... Gödel himself felt—and expressed the thought in his paper—that his work did not contradict Hilbert's formalistic point of view" (en) David Hilbert poses his "23 questions" at the Second International Congress of Mathematicians in Paris. "Of these, the second was that of proving the consistency of the 'Peano axioms' on which, as he had shown, the rigour of mathematics depended". (en) Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory", which proposes that the intuitive notion of an effectively calculable function can be formalized by the general recursive functions or equivalently by the lambda-definable functions. He proves that the halting problem for lambda calculus is not effectively calculable. (en) Emil Post's paper "Finite Combinatory Processes. Formulation I" is received. Post adds to his "process" an instruction " Stop". He called such a process "type 1 ... if the process it determines terminates for each specific problem." (en) |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Authority_control dbt:Cite_book dbt:Cite_journal dbt:Cn dbt:End_date dbt:Further dbt:ISBN dbt:Main dbt:More_footnotes dbt:Page_needed dbt:Quote dbt:Reflist dbt:See_also dbt:Sfn dbt:Sfnm dbt:Short_description dbt:Start_date dbt:Timeline-event dbt:Trim dbt:Var dbt:Use_shortened_footnotes dbt:Mathematical_logic |
| dcterms:subject | dbc:Mathematical_problems dbc:1936_introductions dbc:Undecidable_problems dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Problem |
| rdf:type | owl:Thing yago:WikicatMathematicalProblems yago:WikicatParadoxes yago:Abstraction100002137 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:Contradiction107206887 yago:Difficulty114408086 yago:Falsehood106756407 yago:Message106598915 yago:Paradox106724559 yago:Problem114410605 dbo:Disease yago:State100024720 yago:Statement106722453 |
| rdfs:comment | En teoria de la computabilitat el problema de la parada és un problema de decisió que es pot formular de forma informal: donada una descripció d'un programa i el seu estat inicial, determinar si el programa, quan executa aquesta entrada, s'atura (completa). L'alternativa és que funciona per sempre sense aturar-se Alan Turing va provar el 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir. Es diu que el problema de la parada és indecidible amb màquines de Turing. (ca) Problém zastavení (halting problem) je úloha teorie vyčíslitelnosti, která může být neformálně zadána takto: Znáte-li zdrojový kód programu a jeho vstup, rozhodněte, zda program zastaví, nebo zda poběží navždy bez zastavení. V roce 1936 Alan Turing dokázal, že obecný algoritmus, který by řešil problém zastavení pro všechny vstupy všech programů, neexistuje. Problém zastavení se proto označuje jako algoritmicky nerozhodnutelný problém. Je však částečně rozhodnutelný, což lze ukázat simulací univerzálním Turingovým strojem, který zastaví, pokud simulovaný TS normálně či abnormálně zastavil. (cs) مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير. (ar) Problemo de halto estas tasko de , kiu povas esti neformale donita jene: Se vi konas fontkodon de programo kaj ties eniron, decidu, ĉu la programo haltos aŭ ĉu ĝi funkcios por ĉiam sen halto. En la jaro 1936 Alan Turing pruvis, ke ĝenerala algoritmo, kiu solvus la problemon de halto por ĉiuj eniroj de ĉiuj programoj, ne ekzistas. La problemo de halto tial estas markata kiel algoritme . (eo) El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing y una palabra , determinar si terminará en un número finito de pasos cuando es ejecutada usando como dato de entrada.Alan Turing, en su famoso artículo «On Computable Numbers, with an Application to the Entscheidungsproblem» (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible (no computable o no recursivo), en el sentido de que ninguna máquina de Turing lo puede resolver. (es) 計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。 アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。 (ja) Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato ingresso finito, stabilire se l'algoritmo in questione termina o continua la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale in grado di risolvere il problema per tutti i possibili ingressi. La versione più nota del problema è quella proposta nel 1936 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità. (it) 계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다. (ko) Het stopprobleem, ook bekend als het 'halting problem', is het beslissingsprobleem uit de wiskunde en informatica, om te bepalen of een algoritme bij een eindige invoer in een eindig aantal stappen eindigt of dat het eindeloos blijft doorgaan. Het is een bekend voorbeeld van een wiskundig probleem dat onbeslisbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd bewezen door Alan Turing in 1936. (nl) Problem stopu – zagadnienie algorytmiczne odpowiadające, dla danego algorytmu, na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu. Problem stopu bywa trudny do rozstrzygnięcia, przykładem może być sformułowany w prosty sposób problem Collatza, dla którego odpowiedź jest dotychczas nieznana. (pl) Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: ''Dadas uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente.'' Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir. Dizemos que o problema da parada é indecidível nas Máquinas de Turing. (pt) В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно (uk) 停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。 (zh) Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον . (el) In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program–input pairs cannot exist. Jack Copeland attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s. (en) Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt werden, entsteht eine Berechnungsvorschrift, ein sogenannter Algorithmus. Zur Ausführung von Algorithmen benutzt man in der theoretischen Informatik abstrakte Maschinen. Eine typische abstrakte Maschine ist die Turingmaschine.Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt. Obwohl das für viele Algorithmen leicht beantwortet werden kann, konnte der Mathematiker Alan Turing beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Diesen Beweis vollzog er an einer Turingmaschine.Das Halteproblem ist somit algorithmisch nicht (de) En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non. (fr) Stopproblemet eller haltproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som informellt kan beskrivas så här: Med en given beskrivning av ett program och dess indata, bestäm om programmet, när det utförs med indatat, någonsin stoppar (slutför beräkningen). Alternativet är att det fortsätter i evighet utan avbrott. En annan beskrivning av problemet lyder: Är det möjligt att inom ändlig tidsrymd med något program avgöra om ett godtyckligt program stannar för godtyckliga indata? (sv) Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. В терминах функций проблему можно доступно описать следующим образом: (ru) |
| rdfs:label | مسألة توقف (ar) Problema de la parada (ca) Problém zastavení (cs) Halteproblem (de) Πρόβλημα τερματισμού (el) Problemo de halto (eo) Problema de la parada (es) Problème de l'arrêt (fr) Halting problem (en) Problema della terminazione (it) 정지 문제 (ko) 停止性問題 (ja) Stopprobleem (nl) Problem stopu (pl) Проблема остановки (ru) Problema da parada (pt) Stopproblemet (sv) Проблема зупинки (uk) 停机问题 (zh) |
| rdfs:seeAlso | dbr:Turing_jump |
| owl:sameAs | freebase:Halting problem http://d-nb.info/gnd/4247732-3 yago-res:Halting problem wikidata:Halting problem dbpedia-ar:Halting problem dbpedia-bg:Halting problem dbpedia-ca:Halting problem dbpedia-cs:Halting problem dbpedia-da:Halting problem dbpedia-de:Halting problem dbpedia-el:Halting problem dbpedia-eo:Halting problem dbpedia-es:Halting problem dbpedia-fa:Halting problem dbpedia-fi:Halting problem dbpedia-fr:Halting problem dbpedia-he:Halting problem http://hi.dbpedia.org/resource/हॉल्टिंग_प्रॉब्लम dbpedia-hr:Halting problem dbpedia-it:Halting problem dbpedia-ja:Halting problem dbpedia-ko:Halting problem dbpedia-lmo:Halting problem dbpedia-nl:Halting problem dbpedia-pl:Halting problem dbpedia-pt:Halting problem dbpedia-ru:Halting problem dbpedia-simple:Halting problem dbpedia-sk:Halting problem dbpedia-sr:Halting problem dbpedia-sv:Halting problem dbpedia-th:Halting problem dbpedia-tr:Halting problem dbpedia-uk:Halting problem dbpedia-vi:Halting problem dbpedia-zh:Halting problem https://global.dbpedia.org/id/4oTi5 |
| prov:wasDerivedFrom | wikipedia-en:Halting_problem?oldid=1123597048&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Halting_problem |
| is dbo:wikiPageRedirects of | dbr:Lossy_Turing_machine dbr:Halting_Problem dbr:The_halting_problem dbr:Halt_problem dbr:Halting_Theorem dbr:Halting_predicate dbr:Turing's_halting_problem dbr:Turing's_halting_theorem dbr:Determining_whether_a_program_is_going_to_run_forever |
| is dbo:wikiPageWikiLink of | dbr:Primitive_recursive_function dbr:Proof_of_impossibility dbr:Roger_Penrose dbr:Rounding dbr:Entscheidungsproblem dbr:List_of_computability_and_complexity_topics dbr:Multiverse dbr:Decider_(Turing_machine) dbr:Algorithm dbr:Algorithmic_information_theory dbr:History_of_compiler_construction dbr:History_of_computing_hardware dbr:List_of_important_publications_in_theoretical_computer_science dbr:Perl dbr:Unbounded_nondeterminism dbr:Universality_probability dbr:Deadlock_prevention_algorithms dbr:Decision_problem dbr:Depth-first_search dbr:Description_number dbr:Double_pushout_graph_rewriting dbr:Index_of_computing_articles dbr:Index_of_philosophy_articles_(D–H) dbr:Index_set_(computability) dbr:Inductive_probability dbr:Infinite_loop dbr:Kőnig's_lemma dbr:Quantum_computing dbr:List_of_mathematical_logic_topics dbr:List_of_mathematical_proofs dbr:Computability dbr:Computability_theory dbr:Computable_function dbr:Context-free_grammar dbr:Control-flow_graph dbr:Coq dbr:Mathematical_logic dbr:Generic-case_complexity dbr:Oracle_machine dbr:Trakhtenbrot's_theorem dbr:Timeline_of_mathematical_logic dbr:Church–Turing_thesis dbr:Collatz_conjecture dbr:Emil_Leon_Post dbr:Enumeration dbr:General_recursive_function dbr:Geoffrey_K._Pullum dbr:Georg_Cantor dbr:Glossary_of_artificial_intelligence dbr:Constructive_set_theory dbr:Conway's_Game_of_Life dbr:Correctness_(computer_science) dbr:Creative_and_productive_sets dbr:The_Princeton_Companion_to_Mathematics dbr:Optimal_stopping dbr:Andrey_Markov_Jr. dbr:Arithmetical_hierarchy dbr:Arithmetical_set dbr:Basis_theorem_(computability) dbr:Lossy_Turing_machine dbr:Louise_Hay_(mathematician) dbr:Computable_number dbr:Computable_set dbr:Computably_enumerable_set dbr:Computation_in_the_limit dbr:Computer_science dbr:Emptiness_problem dbr:Full-employment_theorem dbr:Function-level_programming dbr:Function_type dbr:Functional_programming dbr:Low_basis_theorem dbr:Partial_function dbr:Post_correspondence_problem dbr:Malament–Hogarth_spacetime dbr:Static_program_analysis dbr:Tag_system dbr:Theory_of_computation dbr:Many-one_reduction dbr:Axel_Thue dbr:Busy_beaver dbr:Additive_smoothing dbr:Thought_experiment dbr:Toby_Ord dbr:Turing's_proof dbr:Type_system dbr:Distributed_computing dbr:Game_semantics dbr:K-trivial_set dbr:Large_countable_ordinal dbr:Liskov_substitution_principle dbr:Unrestricted_grammar dbr:Alan_Turing dbr:Algorithmically_random_sequence dbr:Alonzo_Church dbr:EXPTIME dbr:Fallibilism dbr:First-order_logic dbr:Barber_paradox dbr:Differential_topology dbr:Foundations_of_mathematics dbr:History_of_logic dbr:Iteratee dbr:Kolmogorov_complexity dbr:Tessellation dbr:Proof_by_contradiction dbr:Mathematical_problem dbr:RE_(complexity) dbr:Reduction_(complexity) dbr:Gödel's_incompleteness_theorems dbr:Counter_machine dbr:Hypercomputation dbr:Halting_Problem dbr:Abstract_interpretation dbr:Advice_(complexity) dbr:BlooP_and_FlooP dbr:T2_Temporal_Prover dbr:Code_coverage dbr:Cognitivism_(psychology) dbr:Heyting_arithmetic dbr:Termination_analysis dbr:Theory_of_everything dbr:Reduction_(computability_theory) dbr:Register_machine dbr:Martin_Davis_(mathematician) dbr:Bootstrapping_(compilers) dbr:Philosophy_of_artificial_intelligence dbr:Post–Turing_machine dbr:Circuits_over_sets_of_natural_numbers dbr:The_halting_problem dbr:Cantor's_diagonal_argument dbr:Chaitin's_constant dbr:Kleene's_T_predicate dbr:Kleene's_recursion_theorem dbr:Process_calculus dbr:Software_bug dbr:Self-hosting_(compilers) dbr:Loop_variant dbr:Mathematical_universe_hypothesis dbr:Turing_machine dbr:Shape_analysis_(program_analysis) dbr:Undecidable_problem dbr:Unit_testing dbr:Universal_Turing_machine dbr:Wang_tile dbr:Worst-case_execution_time dbr:Semi-Thue_system dbr:Walther_recursion dbr:Diagonal_argument dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_undecidable_problems dbr:Turing_jump dbr:Tracing_garbage_collection dbr:Malware_research dbr:Richard's_paradox dbr:NP-completeness dbr:NP-hardness dbr:Post's_theorem dbr:Zero-day_(computing) dbr:Semantic_gap dbr:Turing_reduction dbr:Simple_set dbr:Outline_of_logic dbr:Outline_of_software_engineering dbr:PA_degree dbr:P_versus_NP_problem dbr:Rice's_theorem dbr:Size-change_termination_principle dbr:Turing_degree dbr:Smart_contract dbr:Turing_completeness dbr:Halt_problem dbr:Halting_Theorem dbr:Halting_predicate dbr:Turing's_halting_problem dbr:Turing's_halting_theorem dbr:Determining_whether_a_program_is_going_to_run_forever |
| is rdfs:seeAlso of | dbr:List_of_mathematical_constants dbr:Gödel's_incompleteness_theorems |
| is foaf:primaryTopic of | wikipedia-en:Halting_problem |