# decidability

Published articles for decidability.

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

## 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.