In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. B.

PropertyValue
dbpprop:abstract
  • In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. B. Jack Copeland (2004) attributes the actual term halting problem to Martin Davis.
  • Das Halteproblem ist ein Problem aus der Theoretischen Informatik. Es besteht darin, in einem bestimmten Berechnungskalkül zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift zu einem Ende gelangt. Alan M. Turing bewies als erster, dass das Halteproblem in dem von ihm eingeführten Kalkül der Turingmaschine nicht entscheidbar ist. Genau genommen hat er gezeigt, dass nicht immer beweisbar ist, dass eine nicht-terminierende Turingmaschine nicht hält. Umgekehrt kann jedoch immer gezeigt werden, dass eine terminierende Turingmaschine anhält. Hier gibt es auch einen wichtigen Zusammenhang zur Unvollständigkeit sehr komplexer formaler Systeme. Ein Problem mit der Eigenschaft, dass positive Beantwortung prinzipiell bzw. manchmal möglich ist, negative jedoch nicht, heißt semi-entscheidbares Problem.
  • 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 al 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.
  • 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.
  • 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 <math>M</math> y una palabra <math>w</math>, determinar si <math>M</math> se detendrá cuando es ejecutada usando <math>w</math> 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.
  • Pysähtymisongelma koskee syötteenä annetun, mielivaltaisen ohjelman pysähtymistestausta. Ongelmassa pitää määrittää, pysähtyykö ohjelman suoritus koskaan annetulla syötteellä. Alan Turing todisti vuonna 1936, että ei voi olla olemassa algoritmia, joka ratkaisisi pysähtymisongelman kaikilla syötteillä. Pysähtymisongelma on mahdoton ratkaista nykyisillä laskennan malleilla. Kuvitellaan, että olisi olemassa ratkaisu, funktio, jolle annetaan syötteenä ohjelman koodi ja sen saama syöte: PYSÄHTYYKÖ(ohjelma, syöte) Voitaisiinkin tehdä ohjelma, joka käyttäisi edellä mainittua funktiota hyväkseen: PYSÄHDY_ITSE(ohjelma) if(PYSÄHTYYKÖ) suorita_päättymätön_silmukka else pysähdy "PYSÄHDY_ITSE" annetaan parametriksi pysähtymistestausfunktiolle. Todistuksen kannalta tämän ohjelman olennainen osa on ehtolause. Jos funktio palauttaa toden, tulisi ohjelman pysähtyä, mutta tällöin päädytäänkin ikuiseen silmukkaan, eikä ohjelma siis pysähdykään. Kyseinen ristiriita on todistus siitä, että toimivaa pysähtymistestausfunktiota ei voi olla olemassa.
  • En théorie de la calculabilité, le problème de l'arrêt consiste, étant donné un programme informatique quelconque, à dire s'il finira par s'arrêter ou non. Ce problème n'est pas décidable, c'est-à-dire qu'il n'existe pas de programme informatique qui prendrait comme entrée le code d'un programme informatique quelconque et qui grâce à la seule analyse de ce code ressortirait VRAI si le programme s'arrête et FAUX sinon. Plus concrètement, on ne peut élaborer un compilateur capable de déterminer dans tous les cas si le programme bouclera indéfiniment ou non. 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.
  • Il problema della fermata o problema dell'arresto è un problema proposto nel 1937, insieme alla dimostrazione della sua indecidibilità, dal matematico Alan Turing. Nel problema si chiede se sia sempre possibile, descritto un programma ed un determinato input finito, stabilire se il programma in questione termini o si ripeta all'infinito. È stato dimostato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input.
  • 停止性問題（ていしせいもんだい）は、チューリング機械（≒プログラム、アルゴリズム）Aに入力xを入れたら有限時間で停止するか、という問題。アラン・チューリングは1936年、停止性問題を解くチューリング機械が存在しない事を対角線論法で示した。すなわちそのようなチューリング機械の存在を仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾が導かれる。
  • Het stopprobleem is het probleem uit de wiskunde en informatica, of het mogelijk is vast te stellen of een algoritme bij een eindige invoer eindigt in een eindig aantal stappen of eindeloos blijft doorgaan. Het is in z'n algemeenheid een bekend voorbeeld van een wiskundig probleem dat onberekenbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd bewezen door Alan Turing in 1936.
  • Problemem stopu nazywamy sytuację, gdy dla danego algorytmu należy stwierdzić, czy program realizujący dany algorytm zatrzyma się. Pytanie może odnosić się albo do konkretnych danych wejściowych, albo do wszystkich możliwych danych. Jeśli program zatrzymuje się dla wszystkich danych, to mówimy, że ma własność stopu. Problem stopu jest często bardzo trudny do rozstrzygnięcia dla konkretnych algorytmów. Np. dla problemu Collatza przedstawionego poniższym pseudokodem nie znamy odpowiedzi na pytanie o własność stopu. x:=x0 repeat if x jest parzyste then x := x/2 else x := 3*x + 1 until x = 1 Dotychczas dla wszystkich sprawdzonych doświadczalnie wartości x0 > 0 algorytm się zatrzymywał, jednak nie udało się udowodnić własności stopu dla dowolnej liczby x0.
  • Na teoria da computabilidade o problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Dado uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente, dada essa entrada. 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.
  • В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде: Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки. Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга. Петр Новиков в 1955 г. показал, что проблема остановки почти наверняка эквивалентна так называемой "проблеме тождества слов" в теории групп и компьютерной лингвистике.
  • Stopproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som kan informellt 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. Alan Turing visade 1936 att en allmän algoritm för att lösa stopproblemet för samtliga (program, indata)-par kan inte existera. Man säger att stopproblemet är oavgörbart.
  • В теорії обчислюваності, проблема зупинки є проблемою розрешимості, що може бути зформульована наступним чином: Маючи описання комп'ютерної програми та скінченну множину вхідних даних, вирішити, чи завершить роботу програма у скінченний час, чи буде працювати нескінченно, отримавши вказані вхідні данні. В 1936 році, Алан Тюринг довів, що не може існувати загального алгоритму для розв'язання проблеми зупинки для всіх пар програма-вхідні дані. Тепер проблема зупинки називається нерозв'язною на множині машин Тюринга.
  • 停机问题（halting problem）是目前逻辑数学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个<math> s \in S</math>。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的(countable) S 也是可停机的，在使用 oracle 输入的帮助下。 通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。 停机问题本质是一阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. B.
  • Das Halteproblem ist ein Problem aus der Theoretischen Informatik. Es besteht darin, in einem bestimmten Berechnungskalkül zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift zu einem Ende gelangt. Alan M. Turing bewies als erster, dass das Halteproblem in dem von ihm eingeführten Kalkül der Turingmaschine nicht entscheidbar ist. Genau genommen hat er gezeigt, dass nicht immer beweisbar ist, dass eine nicht-terminierende Turingmaschine nicht hält.
  • 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 al 1936 que un algorisme general per resoldre el problema de la parada per totes les possibles parelles programa-entrades no pot existir.
  • 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.
  • 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 <math>M</math> y una palabra <math>w</math>, determinar si <math>M</math> se detendrá cuando es ejecutada usando <math>w</math> como dato de entrada.
  • Pysähtymisongelma koskee syötteenä annetun, mielivaltaisen ohjelman pysähtymistestausta. Ongelmassa pitää määrittää, pysähtyykö ohjelman suoritus koskaan annetulla syötteellä. Alan Turing todisti vuonna 1936, että ei voi olla olemassa algoritmia, joka ratkaisisi pysähtymisongelman kaikilla syötteillä. Pysähtymisongelma on mahdoton ratkaista nykyisillä laskennan malleilla.
  • En théorie de la calculabilité, le problème de l'arrêt consiste, étant donné un programme informatique quelconque, à dire s'il finira par s'arrêter ou non. Ce problème n'est pas décidable, c'est-à-dire qu'il n'existe pas de programme informatique qui prendrait comme entrée le code d'un programme informatique quelconque et qui grâce à la seule analyse de ce code ressortirait VRAI si le programme s'arrête et FAUX sinon.
  • Il problema della fermata o problema dell'arresto è un problema proposto nel 1937, insieme alla dimostrazione della sua indecidibilità, dal matematico Alan Turing. Nel problema si chiede se sia sempre possibile, descritto un programma ed un determinato input finito, stabilire se il programma in questione termini o si ripeta all'infinito. È stato dimostato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input.
  • Het stopprobleem is het probleem uit de wiskunde en informatica, of het mogelijk is vast te stellen of een algoritme bij een eindige invoer eindigt in een eindig aantal stappen of eindeloos blijft doorgaan. Het is in z'n algemeenheid een bekend voorbeeld van een wiskundig probleem dat onberekenbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd bewezen door Alan Turing in 1936.
  • Problemem stopu nazywamy sytuację, gdy dla danego algorytmu należy stwierdzić, czy program realizujący dany algorytm zatrzyma się. Pytanie może odnosić się albo do konkretnych danych wejściowych, albo do wszystkich możliwych danych. Jeśli program zatrzymuje się dla wszystkich danych, to mówimy, że ma własność stopu. Problem stopu jest często bardzo trudny do rozstrzygnięcia dla konkretnych algorytmów. Np.
  • Na teoria da computabilidade o problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Dado uma descrição de um programa e uma entrada finita, decida se o programa termina de rodar ou rodará indefinidamente, dada essa entrada. 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.
  • В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде: Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо.
  • Stopproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som kan informellt 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. Alan Turing visade 1936 att en allmän algoritm för att lösa stopproblemet för samtliga (program, indata)-par kan inte existera.
rdfs:label
  • Halting problem
  • Halteproblem
  • Problema de la parada
  • Problém zastavení
  • Problema de la parada
  • Pysähtymisongelma
  • Problème de l'arrêt
  • Problema della fermata
  • 停止性問題
  • Stopprobleem
  • Problem stopu
  • Problema da parada
  • Проблема остановки
  • Stopproblemet
  • Проблема зупинки
  • 停机问题
owl:sameAs
skos:subject
foaf:page
is dbpedia-owl:Person/knownFor of
is dbpedia-owl:knownFor of
is dbpprop:knownFor of
is dbpprop:redirect of