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

Filter by
Sorted by
Tagged with
4
votes
0answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
12 views

A problem on $m$-reducibility

I'm trying to solve the following problem: (a) Show that for a computably enumerable but not computable set $A$, $A\not\leq_m \overline A$. (b) Show that if $A$ is computably enumerable, then $A\le_m ...
1
vote
1answer
52 views

Proving Rice's theorem using Kleene's fixed point theorem

Here's Rice's theorem from recursion theory: Let $\mathscr F$ be the class of all unary computable functions. Let $\mathscr A\subset \mathscr F$ be an arbitrary nontrivial property of computable ...
2
votes
0answers
72 views

The beta-function lemma (in Boolos and Jeffrey) without primes?

Boolos and Jeffrey in Computability and Logic (3rd ed.) give a proof of the Beta-function Lemma (14.2, pp. 162-3) that makes use of the idea that any finite sequence of natural numbers: $i_0, ..., i_k$...
1
vote
1answer
76 views

What does “$\to$” mean in statements like “$A(M) \,\&\, F^{(n)}\to CC_n$” and “$(x)[(N(x)\to(\exists x')F(x,x') ]$”? [closed]

The following snippets are from Turing's On Computable Numbers, pages 260-261 (PDF link via virginia.edu). What does this arrow expression mean? "I shall show that all formulae of the form $A(M)...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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-...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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). ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
-1
votes
1answer
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 ...
-2
votes
1answer
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 ...
0
votes
1answer
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 ...
12
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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$ ...
2
votes
2answers
71 views

Determining the size of a theory's models

While these are technically separate questions, I think that the answer to either question will be clearer if both questions are answered together. So I'm asking them together. Proposition 1 If $\...
2
votes
1answer
41 views

Is any variety generated by a recursively presented group always recursive?

Let’s denote the minimal variety of groups (a class of all groups, that satisfy a given set of identities of equivalently a class of groups that is closed under subgroups, quotients and direct ...
0
votes
1answer
44 views

Is a TM with oracle also a TM?

From Ullman's Introduction to Automata Theory, Languages and Computation, in a TM with oracle $A$ : Observe that if $A$ is a recursive set, then the oracle $A$ can be simulated by another Turing ...
0
votes
1answer
63 views

What kind of problem is the membership problem of a recursive enumerable language?

Is it correct that the membership problem (i.e. the characteristic function) of a recursive language is a decidable i.e. computable problem? What kind of problem is the membership problem of a ...
0
votes
2answers
38 views

What is the relation between recursive languages and partial recursive functions?

From Introduction to Automata Theory, Language, and Computation by Ullman et. al.: The Turing machine is studied both for the class of languages it define (called the recursively enumerable sets) and ...
0
votes
0answers
35 views

Computability theory in relation to other fields

In Geometric Group Theory (or, perhaps more specifically, in Combinatorial Group Theory) we phrase algebraic concepts as operations on words. This gives the subject a more combinatorial flavor (thus ...
1
vote
0answers
38 views

Why is the blank-tape halting problem $H_0$ so relevant in literature?

After comparing some text books and lectures about computability theory I encountered not only the halting problem $$H = \{\langle M,x \rangle \mid \text{the Turing machine $M$ halts on input $x$}\}$$ ...
1
vote
1answer
40 views

An analogue of Rayo's function for ordinals

I have spent a little time, just for fun, wondering about how to construct larger and larger countable ordinals, and I finally tried to take a cue from Rayo's function by considering the following $\...
1
vote
1answer
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 ...
0
votes
0answers
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}$ ...
0
votes
0answers
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 ...
1
vote
0answers
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.
1
vote
0answers
87 views

How many recursive language families are there?

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 $\...
1
vote
1answer
87 views

Proving innumerable number of RE-hard languages

I'm trying to prove that there are uncountably many RE-hard languages, using Rice's theorem. However, every try leads me to the wrong conclusion the are innumerable many languages in RE... EDIT: I ...

1
2 3 4 5
38