# Questions tagged [computability]

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

1,882 questions
Filter by
Sorted by
Tagged with
44 views

### Can a Busy Beaver have duplicate transitions

Is there any evidence or proof that a Turing machine that is a Busy Beaver champion cannot have a state where both transitions are identical? For example, suppose state C has transitions 1RA for input ...
93 views

### What is the full definition of the head position “inferior limits” rule for Ordinal Turing Machines?

I cannot seem to find a full, unambiguous definition of the “inferior limits” rule for Ordinal Turing Machines Ordinal Turing Machines in case of how to determine the head position at limit ordinal ...
42 views

### Undecidability of the Halting Problem excluding the main diagonal

So the Halting Problem states (or at least one statement is) that there isn't a Turing Machine that decides whether or not a given Turing Machine halts on a given input, using only its description. I ...
12 views

39 views

### The set of Godel numbers of axioms of Robinson arithmetic is recursive

Prove that the set of Godel numbers of axioms of Robinson arithmetic is recursive. I'm studying Godel incompleteness theorems and I want to prove The set of Godel numbers of axioms of Robinson ...
20 views

### if $\ L_{1} \cup L_{2}$ is regular and $\ L_{1} \cap L_{2}$ is regular, and $\ L_{2}$ is regular, so $\ L_{1}$ is regular.

True / False: if $\ L_{1} \cup L_{2}$ is regular and $\ L_{1} \cap L_{2}$ is regular, and $\ L_{2}$ is regular, so $\ L_{1}$ is regular. My intuition: I assume is false, but couldn't find a counter ...
127 views

### An undecidable problem and a non-semidecidable one

Prove that the decision problem "Does $f$ match this behaviour?" is undecidable (assume the behaviour is nontrivial) and that the problem "Is $h(x)$ undefined?" is not semi-...
16 views

### Function defined by means of primitive recursive functions is a specific way can be shown to be recursive. But I cannot find a proof of that.

I am trying to get some grip on computable functions and was introduced to primitive recursive functions. An essential part is that a function $F:\mathbb N^{2}\to\mathbb N$ is primitive recursive if ...
55 views

### How can a subset be undecidable?

A subset of a set can have an undecidable member relation. Though how can you determine if $A$ is actually a subset of $B$ if the member relation of $A$ is not decidable? That feels contradictory ...
49 views

### Are “forgetful” and “mindful” Turing machines equivalent?

Premise: Define a "mindful" Turing machine (MTM) to be a Turing machine (TM) with a log that records the configuration of the head (i.e. current state, symbol being read, next state, symbol ...
66 views

### Does “recursive” mean the same in “recursive functions” and in definition of Fibonacci function?

Why are recursive functions called "recursive"? Does "recursive" mean that we can define a family of functions inductively (from primitive recursive functions to composite ...
21 views

### Analogue of Turing recognizable languages

A language $S$ is called Turing recognizable if for some Turing machine $S$ is exactly the set of inputs when the machine halts. How can we call the language which is the set of outputs for some ...
45 views

### Decidability of $2^a \bmod a^3$?

From some limited testing, it seems to me like $2^a \bmod a^3$ has no repeat values except for some powers of $2$. More generally, it also seems that $x^a \bmod (a^3+k)$ often holds to this, although ...
36 views

### Prove that $\{p: U(p,p)\downarrow\}\equiv_m K_e=\{p:\phi_p()\downarrow\}$

Let $U$ be a universal function for the class of computable functions of one argument. This means $U:N\times N\to N$ is a partial computable function, and for any partial computable $f$ of one ...
33 views

### Is there any infinitesimal number both definable and computable?

Suppose we take for example the smallest number strictly greater than 0 (which in the conventional real number system realm doesn't exist but in some other number systems does (e.g the hypereals). ...
35 views

### A transitive closure axiom for a machine operating system.

The following section is pure speculation on my part, but I feel compelled to share it on the math stackexchange. I used tags on this question to draw in experts, not to imply any knowledge I have in ...
26 views

### Separation axiom implied by semidecidability of comparison

I am studying computable analysis. What I'm fascinated by is the analogy between computable analysis and general topology: a Wikipedia article Semidecidable sets are analogous to open sets. So I ...
78 views

### confusion of halting problem

Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts. lets P be program that determine one of the ...
62 views

### Coarsenings of the topology on $2^\omega$ with $F_\sigma$ (sub)base

Motivation: I am interested in computational representations of topological spaces which are particularly "explicit", in the somewhat vague sense that we can specify everything we care about ...
53 views

### Can $S_R(A)$ always be embedded into $S_R(\mathbb{N})$?

Suppose $A$ is a recursively enumerable subset of $\mathbb{N}$. Let’s call a $\mu$-recursive function $f$ a recursive permutation of $A$, if it is undefined on $\mathbb{N}\setminus A$ and $f|_A$ is a ...
36 views

### Are there more learnable but undecidable cases except the halting problem

In the ICML 1992 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting problem is learnable in a probabilistic learnability. So except halting problem, are there ...
43 views

### What is a data structure, in terms of computability theory?

In computability theory, an algorithm is exactly a Turing machine. What is a data structure, in terms of computability theory then? Can computability theory be used for defining the concept of data ...
44 views

### In terms of computability theory, what is a programming language?

In terms of computability theory, what is a programming language? https://en.wikipedia.org/wiki/Turing_completeness says In computability theory, a system of data-manipulation rules (such as a ...
58 views

### “Natural” example of an undecidable subset of $\Bbb N$

All the simple examples of undecidable problems that I know deal with symbolic computation or calculation. For example, the halting problem, whether Diophantine equations have solutions, the word ...
111 views

### Is $S_R$ finitely generated?

Suppose $S_R$ - is the set of all total recursive bijections on $\mathbb{N}$. It is not hard to see that this set forms a group with respect to composition, and that $|S_R| = \aleph_0$. Is $S_R$ ...
21 views

### Does a r.e. language as a r.e. set assume some encoding from the set of all words to the set of natural numbers?

https://en.wikipedia.org/wiki/Recursively_enumerable_set says A subset S of the set of natural numbers is called recursive enumerable, if there is a partial recursive function whose domain is exactly ...
35 views

### Is PCP itself worth while?

Post correspondence problem has been used in proving other problems undecidable in computability theory. I was wondering which mathematical field PCP itself belongs to: stringology, combinatorics on ...
32 views

### Do computability and algorithms respectively imply Turing machines which halt on all inputs, or general Turing machines?

I am reading Ullman's Introduction to Automata, Languages and Computation (1979), and also want to keep up to date with the terminology of the field. When talking about computability of a problem, is ...
58 views

### The use of soundness in the Kritchman-Raz proof and Berry's paradox

In the Kritchman-Raz paper the authors recall Chaitin's proof of a version of the first incompleteness theorem (italics are mine): Chaitin’s incompleteness theorem states that for any rich enough ...
58 views

### Alternative conditions for deciding the halting problem

I have been trying to learn about the halting problem lately, in particular reviewing the proof that the halting problem is undecidable. I understand, abstractly, the idea of this proof, but it has ...
32 views

### What kind of functions can be computed by finite automata with outputs? [closed]

The functions which can be computed by Turing machines are exactly the (partially/general) recursive functions. What kind of functions can be computed by finite automata with outputs (e.g. Mealy and ...
24 views

### What does “L being a CFL” as “a property of CFL's” mean?

In Ullman's Introduction to Automata, Languages and Computation (1979): 8.8 Use Theorem 8.14 to show that the following properties of CFL's are undecidable. a) L is a linear language. b) L is a CFL. ...
24 views

### Family of unary partial computable functions having total computable extension is computable.

I have to prove: Family of unary partial computable functions having total computable extension is computable. But it is not so obvious for me. Here i provide some definitions: If the function $h$ ...
71 views

57 views

### Does a formal system that proves everything that is provable exists?

The Church thesis states that "a function is computable iff it is computable by a Turing machine." Similarly, I wonder if there exists some thesis that states that "a mathematical truth ...
36 views

### Computability problem/exercice — can't solve

I'm really blocked in the first part of the below exercise and can't solve it. It would be great if you could help! Show that there exists a partial recursive function $g:\mathbb{N}\to \mathbb{N}$ ...
19 views

### Behavior of a simple tag system?

My understanding is that tag systems of TS(2,2) (two symbols, deletion number 2) are supposed to be fairly well understood; they should all be decidable, etc. As near as I can tell, this is the ...
24 views

### Prove that the problem of tiling a quarter of the plane of a polimino of the same type is decidable.

I know that it is not decidable in the general case but I feel that there is the solution when we have only one type of shape.
Let’s define a transducer as a $5$-tuple $(Q, A, B, \phi, \psi)$, where $Q$ is a finite collection of states, $A$ is a finite input alphabet, $\phi: Q\times A \to Q$ is the transition function and \$\...