# Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

145 questions
120 views

### In the beginning, computable functions where always total, but when where the partial functions included

The modern definition of computable functions $f : \mathbb N \to \mathbb N$ as given on wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some ...
127 views

### Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
88 views

### Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
47 views

### The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
89 views

### Wanted: Concrete Example of Busy Beaver Holdout

I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' ...
100 views

### Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
84 views

### Undecidable problems with efficient heuristics

Are there some undecidable problems for which there are efficient heuristic algorithms, that succeed on a sufficiently large subset of inputs to be worth using? The one application that comes to mind ...
73 views

### Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
53 views

### Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems

We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to ...
49 views

### Is there a name for the class of functions whose totality can be proved using “Ackermann-like” reasoning?

Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
58 views

### Is the number of tests needed to know if a program computes the identity computable?

Given a $\lambda$-term $t\in \Lambda$ and an integer $k$, we say that $t$ behave likes the identity when applied to $k$ if $tk\to_\beta^*k$ (where the integer is represented as a church numeral). We ...
71 views

### Direct reduction $L_{REG}\le_m L_{CFG}$

Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. ...
91 views

### Post's Correspondence Problem - BFS or DFS?

This question has recently occurred to me as I was working on an implementation of the (Bounded) Post's Correspondence Problem. Basically, which method is generally best for PCP? Breadth-first or ...
64 views

### Prove that variable projection is recursive

Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and $\mathcal{I}^n_i(x_1,...,x_n) = x_i$ be the $i$-th projection over $n$ variables. I would like to ...
47 views

### A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...
163 views

### A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
151 views

### Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
70 views

### The sequence in which every symbol minimizes conditional complexity?

I formulate the question in terms of universal distributions. Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary ...
58 views

### Is it a bad idea to require a correctness proof as part of a computable real number?

At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
24 views

### Is there a formal way of defining a Zeno Machine?

The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
37 views

### Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
159 views

### What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
29 views

### Semidecidable properties of computable reals

By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
82 views

### What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...