Halting problem
http://dbpedia.org/resource/Halting_problem an entity of type: Thing
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.
rdf:langString
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.
rdf:langString
مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير.
rdf:langString
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 .
rdf:langString
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.
rdf:langString
計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。 アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。
rdf:langString
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à.
rdf:langString
계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно
rdf:langString
停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。
rdf:langString
Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον .
rdf:langString
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.
rdf:langString
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
rdf:langString
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.
rdf:langString
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?
rdf:langString
Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. В терминах функций проблему можно доступно описать следующим образом:
rdf:langString
rdf:langString
مسألة توقف
rdf:langString
Problema de la parada
rdf:langString
Problém zastavení
rdf:langString
Halteproblem
rdf:langString
Πρόβλημα τερματισμού
rdf:langString
Problemo de halto
rdf:langString
Problema de la parada
rdf:langString
Problème de l'arrêt
rdf:langString
Halting problem
rdf:langString
Problema della terminazione
rdf:langString
정지 문제
rdf:langString
停止性問題
rdf:langString
Stopprobleem
rdf:langString
Problem stopu
rdf:langString
Проблема остановки
rdf:langString
Problema da parada
rdf:langString
Stopproblemet
rdf:langString
Проблема зупинки
rdf:langString
停机问题
xsd:integer
21391870
xsd:integer
1123597048
xsd:date
1935-04-19
xsd:date
1936-10-07
rdf:langString
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."
rdf:langString
Church publishes the first proof that the Entscheidungsproblem is unsolvable.
rdf:langString
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?'."
rdf:langString
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".
rdf:langString
J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing
rdf:langString
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 .
rdf:langString
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.
rdf:langString
Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I"
rdf:langString
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.
rdf:langString
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"
rdf:langString
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".
rdf:langString
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.
rdf:langString
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."
rdf:langString
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.
rdf:langString
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.
rdf:langString
مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير.
rdf:langString
Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο Άλαν Τιούρινγκ, το 1936, απέδειξε ότι δεν υπάρχει κάποιος γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου. Κομμάτι κλειδί της απόδειξης ήταν ένας μαθηματικός ορισμός ενός υπολογιστικού προγράμματος, γνωστού ως μηχανή Τιούρινγκ. Το πρόβλημα τερματισμού είναι στις μηχανές Turing. Είναι ένα από τα πρώτα παραδείγματα προβλήματος απόφασης. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον .
rdf:langString
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 .
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。 アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。
rdf:langString
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à.
rdf:langString
계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём. В терминах функций проблему можно доступно описать следующим образом: Для любой функции F(G, start_state) которая может определять останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F, результат выполнения будет противоположен тому, который предсказывает F. Для многих других задач[каких?] можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима.
rdf:langString
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.
rdf:langString
В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно
rdf:langString
停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。
xsd:nonNegativeInteger
50166