HTML Microdata document

This HTML5 document contains 475 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dbt	http://dbpedia.org/resource/Template:
dbpedia-da	http://da.dbpedia.org/resource/
dbpedia-el	http://el.dbpedia.org/resource/
dbpedia-sv	http://sv.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-lmo	http://lmo.dbpedia.org/resource/
dbpedia-bg	http://bg.dbpedia.org/resource/
dbpedia-fi	http://fi.dbpedia.org/resource/
dbr	http://dbpedia.org/resource/
dbpedia-hr	http://hr.dbpedia.org/resource/
n23	https://arxiv.org/abs/
dbpedia-ar	http://ar.dbpedia.org/resource/
dbpedia-he	http://he.dbpedia.org/resource/
dbpedia-fr	http://fr.dbpedia.org/resource/
n56	http://www.lel.ed.ac.uk/~gpullum/
dcterms	http://purl.org/dc/terms/
dbpedia-cs	http://cs.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
n34	http://dx.doi.org/10.1093/acprof:oso/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
n31	http://d-nb.info/gnd/
dbp	http://dbpedia.org/property/
dbpedia-eo	http://eo.dbpedia.org/resource/
xsdh	http://www.w3.org/2001/XMLSchema#
n38	http://www.turingarchive.org/browse.php/B/
dbpedia-uk	http://uk.dbpedia.org/resource/
dbpedia-sr	http://sr.dbpedia.org/resource/
dbo	http://dbpedia.org/ontology/
dbpedia-vi	http://vi.dbpedia.org/resource/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-sk	http://sk.dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
dbc	http://dbpedia.org/resource/Category:
dbpedia-de	http://de.dbpedia.org/resource/
dbpedia-pl	http://pl.dbpedia.org/resource/
dbpedia-th	http://th.dbpedia.org/resource/
n12	https://www.youtube.com/
dbpedia-ru	http://ru.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
wikidata	http://www.wikidata.org/entity/
dbpedia-nl	http://nl.dbpedia.org/resource/
gold	http://purl.org/linguistics/gold/
n24	http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimTeX/
yago-res	http://yago-knowledge.org/resource/
n27	https://global.dbpedia.org/id/
n45	https://archive.org/details/introductiontoth00sips/page/
n40	http://hi.dbpedia.org/resource/
dbpedia-it	http://it.dbpedia.org/resource/
dbpedia-ca	http://ca.dbpedia.org/resource/
n37	http://motherboard.vice.com/read/
prov	http://www.w3.org/ns/prov#
foaf	http://xmlns.com/foaf/0.1/
dbpedia-simple	http://simple.dbpedia.org/resource/
n36	http://dbpedia.org/resource/C2:
dbpedia-zh	http://zh.dbpedia.org/resource/
dbpedia-ko	http://ko.dbpedia.org/resource/
dbpedia-tr	http://tr.dbpedia.org/resource/
dbpedia-fa	http://fa.dbpedia.org/resource/
n32	https://archive.org/details/
dbpedia-es	http://es.dbpedia.org/resource/
freebase	http://rdf.freebase.com/ns/
owl	http://www.w3.org/2002/07/owl#

Statements

Subject Item: dbr:Primitive_recursive_function
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Proof_of_impossibility
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Roger_Penrose
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Rounding
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Entscheidungsproblem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_computability_and_complexity_topics
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Multiverse
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Decider_(Turing_machine)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Algorithm
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Algorithmic_information_theory
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:History_of_compiler_construction
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:History_of_computing_hardware
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_important_publications_in_theoretical_computer_science
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_mathematical_constants
rdfs:seeAlso: dbr:Halting_problem

Subject Item: dbr:Perl
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Unbounded_nondeterminism
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Universality_probability
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Deadlock_prevention_algorithms
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Decision_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Depth-first_search
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Description_number
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Double_pushout_graph_rewriting
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Index_of_computing_articles
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Index_of_philosophy_articles_(D–H)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Index_set_(computability)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Inductive_probability
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Infinite_loop
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Kőnig's_lemma
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Quantum_computing
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_mathematical_logic_topics
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_mathematical_proofs
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computability
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computability_theory
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computable_function
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Context-free_grammar
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Control-flow_graph
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Coq
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Mathematical_logic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Generic-case_complexity
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Oracle_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Trakhtenbrot's_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Timeline_of_mathematical_logic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Church–Turing_thesis
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Collatz_conjecture
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Emil_Leon_Post
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Enumeration
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:General_recursive_function
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Geoffrey_K._Pullum
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Georg_Cantor
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Glossary_of_artificial_intelligence
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Constructive_set_theory
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Conway's_Game_of_Life
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Correctness_(computer_science)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Creative_and_productive_sets
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:The_Princeton_Companion_to_Mathematics
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Optimal_stopping
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Andrey_Markov_Jr.
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Arithmetical_hierarchy
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Arithmetical_set
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Basis_theorem_(computability)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Lossy_Turing_machine
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Louise_Hay_(mathematician)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computable_number
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computable_set
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computably_enumerable_set
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computation_in_the_limit
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Computer_science
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Emptiness_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Full-employment_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Function-level_programming
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Function_type
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Functional_programming
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Low_basis_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Partial_function
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Post_correspondence_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Malament–Hogarth_spacetime
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Static_program_analysis
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Tag_system
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Theory_of_computation
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Many-one_reduction
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Axel_Thue
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Busy_beaver
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Additive_smoothing
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Thought_experiment
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Toby_Ord
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing's_proof
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Type_system
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Distributed_computing
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Game_semantics
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:K-trivial_set
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Large_countable_ordinal
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Liskov_substitution_principle
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Unrestricted_grammar
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Alan_Turing
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Algorithmically_random_sequence
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Alonzo_Church
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:EXPTIME
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Fallibilism
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:First-order_logic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Barber_paradox
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Differential_topology
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Foundations_of_mathematics
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:History_of_logic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Iteratee
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Kolmogorov_complexity
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Tessellation
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Proof_by_contradiction
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Mathematical_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:RE_(complexity)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Reduction_(complexity)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Gödel's_incompleteness_theorems
rdfs:seeAlso: dbr:Halting_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Halting_problem
rdf:type: yago:Message106598915 owl:Thing yago:State100024720 yago:Communication100033020 yago:Falsehood106756407 yago:WikicatParadoxes yago:Attribute100024264 yago:Problem114410605 yago:Difficulty114408086 yago:Condition113920835 yago:WikicatMathematicalProblems yago:Contradiction107206887 dbo:Disease yago:Paradox106724559 yago:Abstraction100002137 yago:Statement106722453
rdfs:label: Stopprobleem 정지 문제 Problema de la parada 停机问题 Problema de la parada Problema da parada Problemo de halto Halteproblem Problema della terminazione Проблема зупинки Problem stopu Halting problem Problém zastavení Problème de l'arrêt 停止性問題 مسألة توقف Πρόβλημα τερματισμού Stopproblemet Проблема остановки
rdfs:comment: Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. В терминах функций проблему можно доступно описать следующим образом: 계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다. 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 . 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. 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. 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? В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно 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. Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον . 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. 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. 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 مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير. 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. 停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。 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. 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à. 計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。 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.
rdfs:seeAlso: dbr:Turing_jump
dcterms:subject: dbc:1936_introductions dbc:Mathematical_problems dbc:Computability_theory dbc:Theory_of_computation dbc:Undecidable_problems
dbo:wikiPageID: 21391870
dbo:wikiPageRevisionID: 1123597048
dbo:wikiPageWikiLink: dbr:Normal_number dbr:MISRA_C dbr:Christopher_Strachey dbr:SPARK_(programming_language) dbr:Emil_Post dbr:Gregory_Chaitin dbr:Worst-case_execution_time dbr:Kolmogorov_complexity dbr:Alfred_North_Whitehead dbr:Pseudocode dbr:Real-time_computing dbr:Lambda_calculus dbr:Heuristic_(computer_science) dbr:J._Barkley_Rosser dbr:Gentzen dbr:Busy_beaver dbr:Algorithm dbr:Jack_Copeland dbr:Cantor's_diagonal_argument dbr:Proposition dbr:Register_machine dbr:Busy_Beaver dbr:Markov_algorithm dbr:Gödel_numbering dbr:Hypercomputer dbr:International_Congress_of_Mathematicians dbr:Turing-complete dbc:1936_introductions dbr:David_Hilbert dbr:Model_of_computation dbr:Reduction_(complexity) dbr:Natural_density dbr:Total_function dbr:P_versus_NP_problem dbr:Brainfuck dbr:Marvin_Minsky dbc:Mathematical_problems dbr:Coq dbr:Martin_Davis_(mathematician) dbr:Rice's_theorem dbr:Kurt_Gödel dbr:Enumeration dbr:Recursively_enumerable dbr:Physical_process dbr:Recursion_theory dbr:Primitive_recursive dbr:Computer_program dbr:Peano_Axioms dbc:Computability_theory dbr:Peano_axioms dbr:Data_type dbr:Brouwer–Hilbert_controversy dbr:Transcendental_number dbr:Computer_scientist dbr:Ernest_Nagel dbr:Gödel's_incompleteness_theorem dbr:Chaitin's_constant dbc:Theory_of_computation dbr:Probability dbr:Natural_number dbr:Post_system dbr:Formalism_(mathematics) dbr:Programming_system dbr:Character_(computing) n36:HaltingProblem dbr:Human_brain dbr:Julia_Robinson dbr:Interpreter_(computing) dbr:Universal_Turing_machine dbr:Alan_Turing dbr:Beta_normal_form dbr:Computation dbr:Event_loop dbr:General_recursive_function dbr:Computable_function dbr:Computability_theory_(computer_science) dbr:Turing_degree dbr:Degree_of_unsolvability dbr:Correctness_(computer_science) dbr:Halting_probability dbr:Machine_that_always_halts dbr:Hilbert's_problems dbr:Computable_number dbr:James_R._Newman dbr:Edward_Beltrami dbr:Self-referential dbr:Definable_number dbr:David_Bolter dbr:Infinite_loop dbr:RE-complete dbc:Undecidable_problems dbr:Effective_method dbr:Turing_machine dbr:Oracle_machine dbr:Alphabet dbr:Programming_language dbr:Turing's_proof dbr:Linear_bounded_automaton dbr:Undecidable_problem dbr:Bertrand_Russell dbr:Turing_Machine dbr:Arithmetical_hierarchy dbr:Church–Turing_thesis dbr:Partial_function dbr:Decision_problem dbr:Rule_of_least_power dbr:Chaitin dbr:Tag_system dbr:Termination_analysis dbr:Alonzo_Church dbr:Taylor_Booth_(mathematician) dbr:Proof_by_contradiction dbr:Stephen_Kleene dbr:Entscheidungsproblem dbr:Reduction_(recursion_theory) dbr:Numeral_system
dbo:wikiPageExternalLink: n12:watch%3Fv=92WHN-pAFCs n23:1411.2842 n24:halt n32:undecidablebasic0000davi%7C n34:9780199233212.001.0001%7Ctitle=The n37:does-the-halting-problem-mean-no-moral-robots n38:12 n32:introductiontoau00hopc%7C n45:173 n56:loopsnoop.html
owl:sameAs: dbpedia-el:Πρόβλημα_τερματισμού dbpedia-ca:Problema_de_la_parada dbpedia-he:בעיית_העצירה dbpedia-lmo:Problema_de_la_fermada wikidata:Q622849 dbpedia-bg:Halting_проблем dbpedia-sv:Stopproblemet dbpedia-hr:Problem_zaustavljanja yago-res:Halting_problem dbpedia-ar:مسألة_توقف dbpedia-uk:Проблема_зупинки dbpedia-da:Halting-problemet dbpedia-fr:Problème_de_l'arrêt n27:4oTi5 dbpedia-tr:Sonlanma_problemi n31:4247732-3 freebase:m.03k9j dbpedia-it:Problema_della_terminazione dbpedia-th:ปัญหาการยุติการทำงาน n40:हॉल्टिंग_प्रॉब्लम dbpedia-vi:Bài_toán_dừng dbpedia-fa:مسئله_توقف dbpedia-sr:Халтинг_проблем dbpedia-pl:Problem_stopu dbpedia-pt:Problema_da_parada dbpedia-eo:Problemo_de_halto dbpedia-sk:Problém_zastavenia dbpedia-ru:Проблема_остановки dbpedia-nl:Stopprobleem dbpedia-ja:停止性問題 dbpedia-cs:Problém_zastavení dbpedia-simple:Halting_problem dbpedia-de:Halteproblem dbpedia-es:Problema_de_la_parada dbpedia-ko:정지_문제 dbpedia-fi:Pysähtymisongelma dbpedia-zh:停机问题
dbp:wikiPageUsesTemplate: dbt:Var dbt:ISBN dbt:End_date dbt:Quote dbt:Short_description dbt:Trim dbt:Sfn dbt:Sfnm dbt:Use_shortened_footnotes dbt:Timeline-event dbt:Mathematical_logic dbt:Page_needed dbt:Further dbt:Reflist dbt:Start_date dbt:More_footnotes dbt:Anchor dbt:Cn dbt:Main dbt:Authority_control dbt:Cite_book dbt:Cite_journal dbt:See_also
dbp:date: 1936-10-07 1935-04-19
dbp:event: 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". Church publishes the first proof that the Entscheidungsproblem is unsolvable. 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 . 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. 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. 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." 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. 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" J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" 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?'." 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". 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."
dbo:abstract: Проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде: Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки. Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы. Проблема остановки занимает центральное место в теории вычислимости, поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём. В терминах функций проблему можно доступно описать следующим образом: Для любой функции F(G, start_state) которая может определять останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F, результат выполнения будет противоположен тому, который предсказывает F. Для многих других задач[каких?] можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки. Это делается по схеме "от противного": пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует алгоритма решения проблемы остановки. А значит, предположение было неверным и исходная задача также неразрешима. 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. مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف. في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير. 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. Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον. Ο Άλαν Τιούρινγκ, το 1936, απέδειξε ότι δεν υπάρχει κάποιος γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου. Κομμάτι κλειδί της απόδειξης ήταν ένας μαθηματικός ορισμός ενός υπολογιστικού προγράμματος, γνωστού ως μηχανή Τιούρινγκ. Το πρόβλημα τερματισμού είναι στις μηχανές Turing. Είναι ένα από τα πρώτα παραδείγματα προβλήματος απόφασης. Ο (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον . 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. 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. 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. 계산 복잡도 이론에서 정지문제(停止問題, halting problem)는 판정 문제의 일종으로 다음과 같이 요약할 수 있다. 프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라. 1936년에 앨런 튜링이 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 한다. 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 . 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. 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. 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à. 停机问题（英語：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。 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. 計算可能性理論において停止性問題（ていしせいもんだい、英: halting problem）または停止問題は、「どんなチューリングマシン、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。 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. 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. В теорії обчислюваності, проблема зупинки є проблемою розв'язності, що може бути сформульована так: Дано опис алгоритму та скінченну множину вхідних даних. Треба вирішити, чи виконання алгоритму завершиться, чи він буде виконуватись нескінченно
gold:hypernym: dbr:Problem
prov:wasDerivedFrom: wikipedia-en:Halting_problem?oldid=1123597048&ns=0
dbo:wikiPageLength: 50166
foaf:isPrimaryTopicOf: wikipedia-en:Halting_problem

Subject Item: dbr:Counter_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Hypercomputation
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Halting_Problem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Abstract_interpretation
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Advice_(complexity)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:BlooP_and_FlooP
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:T2_Temporal_Prover
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Code_coverage
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Cognitivism_(psychology)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Heyting_arithmetic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Termination_analysis
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Theory_of_everything
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Reduction_(computability_theory)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Register_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Martin_Davis_(mathematician)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Bootstrapping_(compilers)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Philosophy_of_artificial_intelligence
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Post–Turing_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Circuits_over_sets_of_natural_numbers
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:The_halting_problem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Cantor's_diagonal_argument
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Chaitin's_constant
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Kleene's_T_predicate
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Kleene's_recursion_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Process_calculus
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Software_bug
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Self-hosting_(compilers)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Loop_variant
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Mathematical_universe_hypothesis
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Shape_analysis_(program_analysis)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Undecidable_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Unit_testing
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Universal_Turing_machine
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Wang_tile
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Worst-case_execution_time
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Semi-Thue_system
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Walther_recursion
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Diagonal_argument
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:List_of_undecidable_problems
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing_jump
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Tracing_garbage_collection
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Malware_research
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Richard's_paradox
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:NP-completeness
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:NP-hardness
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Post's_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Zero-day_(computing)
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Semantic_gap
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing_reduction
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Simple_set
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Outline_of_logic
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Outline_of_software_engineering
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:PA_degree
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:P_versus_NP_problem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Rice's_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Size-change_termination_principle
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing_degree
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Smart_contract
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Turing_completeness
dbo:wikiPageWikiLink: dbr:Halting_problem

Subject Item: dbr:Halt_problem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Halting_Theorem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Halting_predicate
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Turing's_halting_problem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Turing's_halting_theorem
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: dbr:Determining_whether_a_program_is_going_to_run_forever
dbo:wikiPageWikiLink: dbr:Halting_problem
dbo:wikiPageRedirects: dbr:Halting_problem

Subject Item: wikipedia-en:Halting_problem
foaf:primaryTopic: dbr:Halting_problem