# halting problem

Published articles for halting problem.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Methods of Proof -- Diagonalization

DevFeed: [Methods of Proof -- Diagonalization](<https://devfeed.tech/articles/methods-of-proof-diagonalization-40384.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/06/08/methods-of-proof-diagonalization/>)

Published: 2015-06-08T09:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>), [Collections](<https://devfeed.tech/topics/collections.md>)

Tags: [bijections](<https://devfeed.tech/tags/bijections.md>), [cardinality](<https://devfeed.tech/tags/cardinality.md>), [diagonalization](<https://devfeed.tech/tags/diagonalization.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [methods-of-proof](<https://devfeed.tech/tags/methods-of-proof.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>), [uncountability](<https://devfeed.tech/tags/uncountability.md>)

### AI overview

This tutorial introduces diagonalization as an advanced method of mathematical proof. It explains the table-and-diagonal construction and presents the theorem that no bijection exists between the natural numbers and the real numbers.

### Source excerpt

A while back we featured a post about why learning mathematics can be hard for programmers, and I claimed a major issue was not understanding the basic methods of proof (the lingua franca between intuition and rigorous mathematics). I boiled these down to the "basic four," direct implication, contrapositive, contradiction, and induction. But in mathematics there is an ever growing supply of proof methods. There are books written about the "probabilistic method," and I recently went to a lecture where the "linear algebra method" was displayed.

## The Halting Problem

DevFeed: [The Halting Problem](<https://devfeed.tech/articles/the-halting-problem-40751.md>)

Original publisher: [Read original article](<https://radek.io/posts/the-halting-problem/>)

Published: 2014-07-27T00:00:00Z

Content type: article

Language: en

Sources: [Radek Pazdera](<https://devfeed.tech/sources/radek-pazdera.md>)

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [computers](<https://devfeed.tech/tags/computers.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [infinite](<https://devfeed.tech/tags/infinite.md>), [input](<https://devfeed.tech/tags/input.md>), [logic](<https://devfeed.tech/tags/logic.md>), [loops](<https://devfeed.tech/tags/loops.md>), [program](<https://devfeed.tech/tags/program.md>), [reduction](<https://devfeed.tech/tags/reduction.md>)

### AI overview

The article explains Alan Turing's halting problem: no general method can always determine whether an arbitrary program will halt or run forever. It describes the problem's connection to undecidability, diagonalization, and reductions, and briefly discusses Turing's work with Alonzo Church.

### Source excerpt

And other things computers cannot solve

## Other Complexity Classes

DevFeed: [Other Complexity Classes](<https://devfeed.tech/articles/other-complexity-classes-40264.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/02/29/other-complexity-classes/>)

Published: 2012-02-29T17:12:35Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Computing](<https://devfeed.tech/topics/computing.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [nondeterminism](<https://devfeed.tech/tags/nondeterminism.md>), [open-questions](<https://devfeed.tech/tags/open-questions.md>), [oracle](<https://devfeed.tech/tags/oracle.md>), [primer](<https://devfeed.tech/tags/primer.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This article introduces complexity classes beyond P and NP, including PSPACE and NPSPACE, and discusses oracle-based classes. It explains that PSPACE equals NPSPACE while many relationships among complexity classes remain open.

### Source excerpt

Not Just Time, But Space Too! So far on this blog we've introduced models for computation, focused on Turing machines and given a short overview of the two most fundamental classes of problems: P and NP. While the most significant open question in the theory of computation is still whether P = NP, it turns out that there are hundreds (almost 500, in fact!) other "classes" of problems whose relationships are more or less unknown.

## P vs. NP, A Primer (And a Proof Written in Racket)

DevFeed: [P vs. NP, A Primer (And a Proof Written in Racket)](<https://devfeed.tech/articles/p-vs-np-a-primer-and-a-proof-written-in-racket-40263.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/02/23/p-vs-np-a-primer-and-a-proof-written-in-racket/>)

Published: 2012-02-23T19:57:35Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Computing](<https://devfeed.tech/topics/computing.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Racket](<https://devfeed.tech/topics/racket.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [class](<https://devfeed.tech/tags/class.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computing](<https://devfeed.tech/tags/computing.md>), [decidability](<https://devfeed.tech/tags/decidability.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [fast](<https://devfeed.tech/tags/fast.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [input](<https://devfeed.tech/tags/input.md>), [language](<https://devfeed.tech/tags/language.md>), [machine](<https://devfeed.tech/tags/machine.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [p-versus-np](<https://devfeed.tech/tags/p-versus-np.md>), [primer](<https://devfeed.tech/tags/primer.md>), [racket](<https://devfeed.tech/tags/racket.md>), [solve](<https://devfeed.tech/tags/solve.md>), [theory](<https://devfeed.tech/tags/theory.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

A primer on the distinction between decidability and computational efficiency, introducing the complexity class P and its definition in terms of polynomial-time decision by a Turing machine. It also discusses efficient algorithms and gives a card-sorting example.

### Source excerpt

Decidability Versus Efficiency In the early days of computing theory, the important questions were primarily about decidability. What sorts of problems are beyond the power of a Turing machine to solve? As we saw in our last primer on Turing machines, the halting problem is such an example: it can never be solved a finite amount of time by a Turing machine. However, more recently (in the past half-century) the focus of computing theory has shifted away from possibility in favor of determining feasibility.

## Turing Machines--A Primer

DevFeed: [Turing Machines--A Primer](<https://devfeed.tech/articles/turing-machines-a-primer-40218.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/04/turing-machines-a-primer/>)

Published: 2011-07-04T16:35:44Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Automaton](<https://devfeed.tech/topics/automaton.md>), [function](<https://devfeed.tech/topics/function.md>)

Tags: [acceptance](<https://devfeed.tech/tags/acceptance.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computers](<https://devfeed.tech/tags/computers.md>), [concepts](<https://devfeed.tech/tags/concepts.md>), [decidability](<https://devfeed.tech/tags/decidability.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [input](<https://devfeed.tech/tags/input.md>), [machine](<https://devfeed.tech/tags/machine.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>), [process](<https://devfeed.tech/tags/process.md>), [pushdown-automata](<https://devfeed.tech/tags/pushdown-automata.md>), [state](<https://devfeed.tech/tags/state.md>), [symbols](<https://devfeed.tech/tags/symbols.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This tutorial introduces Turing machines as a model of computation. It defines their states, tape symbols, input symbols, initial state, accepting and rejecting states, and transition function, then explains how the tape, read-write head, state transitions, and halting behavior work.

### Source excerpt

We assume the reader is familiar with the concepts of determinism and finite automata, or has read the corresponding primer on this blog. The Mother of All Computers Last time we saw some models for computation, and saw in turn how limited they were. Now, we open Pandrora's hard drive: Definition: A Turing machine is a tuple $ (S, \Gamma, \Sigma, s_0, F, \tau)$, where $ S$ is a set of states, $ \Gamma$ is a set of tape symbols, including a special blank symbol $ b$, $ \Sigma \subset \Gamma$ is a set of input symbols, not including $ b$, $ s_0$ is the initial state, $ A \subset S$ is a set of accepting states, $ R \subset S$ is a set of rejecting states, $ \tau: S - (A \cup R) \times \Gamma \to S \times \Gamma \times \left \{ L, R \right \}$ is a partial function called the transition function, where $ L, R$ correspond to "left shift" and "right shift," respectively.