Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
20 views

Well-definedness of uncomputable functions.

I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never ...
2
votes
0answers
29 views

Is classical Euclidean geometry Turing complete?

By "classical Euclidean geometry" I don't mean the study of $\mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $\mathbb R^2$ that ...
3
votes
1answer
48 views

Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set?

Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and ...
1
vote
1answer
24 views

Show that the greatest common divisor $gcd(x,y)$ is primitive recursive.

Let $x,y \geq 2 $. Actually I have to show that $CD(x,y)$ is primitive recursive, where $ C(x,y) = 1$ if $gcd(x,y)=1$, otherwise $CD(x,y) = 0$. But I have showed that it is enough to show that $gcd(x,...
0
votes
1answer
46 views

Is this proof Ok? ( about computing languages with no loops)

I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter. What's wrong with the following argument: If there's an ...
7
votes
2answers
53 views

Is it possible to put a topology on Turing-recognizable languages to express density among all the languages?

In a Calculability and complexity course I had at univeristy, we proved that there exist languages that are not Turing-recognizable basiclly using Cantor's diagonal argument (the set of all languages ...
6
votes
1answer
75 views

What is the Turing degree of Truth?

First of all by Truth I mean the set $T$ of the Gôdel numbers of the true formulas of first order arithmetic. First order arithmetic is not decidable and $T$ is not decidable, additionally the ...
1
vote
1answer
25 views

Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R

"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
2
votes
2answers
42 views

Simple example of the minimization operator $\mu i$?

This is the definition of a minimization operator from A friendly Introduction to Mathematical Logic. I'm having trouble understanding this. How can this map a function of $n+1$ variables to a ...
1
vote
1answer
53 views

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R

Finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R i am looking for the simplest solution- using a known languages that do not demand another formal proof.
0
votes
0answers
19 views

For a property P, which sigma * belongs to P and P!=RE, prove that Lp does not belong to co-RE [closed]

For a property P, which sigma * belongs to P and P!=RE, prove that Lp does not belong to co-RE. i would like to know how should i prove that
1
vote
1answer
39 views

Finding languages such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R [duplicate]

I am struggling to find such languages $L_1$, $L_2$, and $L_3$ such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R. I know they exist, I need help finding them.
0
votes
1answer
53 views

Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$

I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that $$ L_{1} \subseteq L_{2} \subseteq L_{3} $$ where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$. I know ...
0
votes
0answers
30 views

Prove A function is NOT a Constructible function [closed]

a function For all k, when k is the number of ALL Turing machines with k states, we define BB(k) to be the max number of '1' which is written on the tape at the end of the computation. Note that the ...
-4
votes
1answer
39 views

Algorithms, computable numbers [closed]

Prove that there is not algorithm, which find out that given computable number is 0!!
-1
votes
1answer
19 views

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them? [duplicate]

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them? We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}. Thank you for your help
3
votes
1answer
21 views

Prove that image and preimage of $\Sigma_1$-sets under a function with a $\Sigma_1$-graph are $\Sigma_1$-sets

Assume $A \subset \mathbb{N}^k, B\subset \mathbb{N}$ to be $\Sigma_1$-sets and $f:\mathbb{N}^k \rightarrow \mathbb{N}$ a partial or total function with a $\Sigma_1$-graph. Prove that the image of $A$ ...
-1
votes
0answers
26 views

is the set {i | Dom($\phi_i$) = ∅} recursive, recursive enumerable or none of them

can somebody help me understand if the set {i | Dom($\phi_i$) = ∅} recursive, recursive enumerable or none of them? Dom($\phi_k$) is the set {x | $\phi_k$(x) ↓}. Thank you so much
1
vote
1answer
60 views

Prove that there is a $\Delta_1$-set $E$ which satisfies $S_0 \setminus S_1 \subset E \subset S_0$

I'd appreciate some help for the following exercise. $\Sigma_1, \Pi_1$ and $\Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy I think I can prove 2. when I have 1. - can ...
0
votes
1answer
47 views

Is the set {i | $\phi_i$ is total } recursively enumerable?

Is the set {i | $\phi_i$ is total } recursively enumerable? and can you please tell me why ? Bests Norman
0
votes
0answers
30 views

is SAT as set of satisfiable formulas in FOL recursive or recursive enumerable ?

Can somebody help to understand whether SAT as the set of satisfiable formulas of first-order classical logic. Is SAT recursive, r.e. or none of them? Thank you so much
0
votes
3answers
34 views

sequence that adds its previous results

Let $x = 0.3$. The first number of the sequence is $x$. The second number is the first number + $(0.3\cdot 0.3)$. The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$. This is a ...
0
votes
2answers
34 views

Finding a binary prefix code provided lengths

Firstly, I am relatively new to this particular forum, and I usually use Stack exchange (maths). I do not know if this is the right place to post so please be aware in case, I should ask this question ...
1
vote
1answer
53 views

Prove that function is totally computable

The problem that I'm working on is Graph of function $f : \mathbb{N}\rightarrow \mathbb{N}$ is set {$(x, f(x))$, $x \in \mathbb{N}$ and $f(x)$ $\neq \perp$} $\subseteq \mathbb{N}^{2}$. Prove that ...
0
votes
1answer
73 views

Proving that sets are recursive

I am stuck on proving that given sets are recursive or recursively enumerable. Those sets are: $$\begin{align} f(A) &= \{y, \exists x \in A:f(x) = y\}\\ f^{-1}(A) &= \{x, f(x) \in A\} \end{...
1
vote
0answers
64 views

Proof that specific function is primitive recursive

For all $(n_1, \cdots, n_k) \in \mathbb{N}^k$ let's define $<n_1, \dots, n_k>:=p_1^{n_1+1} \dotsc p_k^{n_k+1}$, whereby $(p_1, p_2, p_3, \cdots)=(2,3,5,7,\cdots)$ are the prime numbers. For ...
0
votes
1answer
27 views

Doubt regarding the variable by which time complexity is measured

In order to assert that a given algorithm for graphs runs in polynomial time, must the variable in the big-O function that represents the run time (denoted henceforth as $O(f(n))$) be the number of ...
1
vote
1answer
47 views

proof that specific disjoint sets are recursively enumerable, but don't lie in a decidable set and its complement

let's call a set $A \subseteq \mathbb{N}$ recursively enumerable if it's "partial characteristic function" $\tilde{\chi}_A$ is computable, whereby $\tilde{\chi}_A$ is defined as: $\tilde{\chi}_A$:= 1, ...
1
vote
1answer
32 views

Prove that EXT,TOT and INF are not recursively enumerable

I am currently working on the reduction method to demonstrate that a set is not recursively enumerable but I am struggling to find suitable functions for the reductions. In particular I have started ...
0
votes
1answer
108 views

What exactly does it mean for an Infinite Time Turing Machine to reach stage $\omega$ (and limit ordinal stage)?

The paper “Infinite Time Turing Machines” contains the following information: At each step of computation, the head reads the cell values which it overlies, reflects on its state, consults the ...
0
votes
1answer
52 views

Ultratasks in the ITTM Model

[Note: I have not previously seen a definition that relates Beth numbers to Supertasks, however my intuition is that one may exist] A supertask is a countably infinite sequence of operations that ...
2
votes
2answers
80 views

Is Chaitin's constant well-defined?

Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined. If I understand ...
1
vote
2answers
37 views

proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
26 views

How to prove that class of “recursive” and “recursively enumerable” languages are not equal?

I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal. I know that recursive languages are accepted by Turing machines ...
0
votes
0answers
31 views

proving statements involving primitive recursive functions and relations and (not) computable functions

I am learning about primitive recursive functions and primitive recursive relations (whereby a relation $R \subseteq \mathbb{N}^n$ is called primitive recursive if its characteristic function is ...
3
votes
2answers
105 views

Is there literature on non-computable numbers that can't be even be identified?

It seems to me that most real numbers can't be calculated by any finite set of instructions, even if we make use of non-computable functions. First, assume that we have an oracle that will provide ...
0
votes
1answer
25 views

Difference between Kleene's O and the system $S_1$

On pages 207-208, Rogers (Theory of Recursive Functions and Effective Computability) introduces two system of notations for ordinals: the first is what he calls $S_1$ and the second one is Kleene's $\...
1
vote
1answer
22 views

Computability of function of two arguments.

I understand that this question shouldn't be hard but still. Let $U: \mathbb N \times \mathbb N \rightarrow \mathbb N$ be a function such that for any fixed $c$ function $D_c(y) = U(c, y)$ is ...
1
vote
1answer
33 views

What is the difference between Turing-reducibility and m-reducibility?

The set $A$ is many-one reducible (m-reducible) to the set $ B $ if there is a total computable function $f$ such that $x ∈ A $ iff $f(x) ∈ B$ for all $x$. We shall write $A ≤_{m} B$ Let be $A, B \...
1
vote
1answer
41 views

Does every nonzero Turing degree adimit a nonzero incompatible degree?

It is well known that every nonzero Turing degree $\bf x$ adimits an incomparable degree $\bf y$, that is a degree such that $\bf x\not\le_T\bf y$ and $\bf y\not\le_T\bf x$. I was wondering whether ...
0
votes
0answers
23 views

Decidability of a relation on Functional space!

Suppose I have this functional space $(D=\{ a\searrow b; a \in A , b \in B\}, \leqslant)$ (partial order relation on step functions!),also suppose that relation $\leqslant_1$ is decidable on $(A,\...
1
vote
1answer
24 views

Is there a partial recursive function mapping $e$ to the least element of $W_e$?

Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_e\neq \varnothing$? Can we apply the $\mu$-operator (minimization) to a partially decidable predicate to ...
1
vote
1answer
40 views

Can you have indirect memory addressing in primitive recursive functions?

Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid". I'm unclear whether cell variables require constant indices or whether ...
0
votes
1answer
20 views

Set that is recursively enumerable but is NOT decidable

I was trying to find a set that is recursively enumerable i.e $$ \exists f\; \text{computable and a program $P$ that computes}\; f $$ such that $$ A = \{ x\; :\; P(x)\downarrow \}. $$ But it is ...
0
votes
0answers
26 views

Show that the decision problem for “the property $P$ such that $P(z)$ holds iff $\lambda x.(\left \{z \right \}(x))$ is total” is unsolvable.

Show that the decision problem for "the property $P$ such that $P(z)$ holds iff $\lambda x.(\left \{z \right \}(x))$ is total" is unsolvable. Here is my work so far, and I am not sure whether it is ...
1
vote
0answers
26 views

Show that $\lambda x.(\left \{x \right \}(x)\neq 0)$ is not recursive.

Show that $\lambda x.(\left \{x \right \}(x)\neq 0)$ is not recursive. I am trying to show this relation is not recursive using a code number for this relation so that I can ultimately prove that ...
0
votes
0answers
18 views

Writing a formal description for F to prove recursion.

I am making an update for finding a formal description using the language of recursion to show that the following is recursive: $\left\{\begin{matrix} F(0,y,z)=G(y)\\ F(x+1,y,z)=H(z,F(x,y,z)) \end{...
0
votes
0answers
38 views

Prove the index of the sum of any two computable numbers is computable

Define a real number $\alpha$ to be computable if there is a computable total function $f_\alpha$ that, given any rational $\epsilon$, yields a rational within $\epsilon$-vicinity of $\alpha$. Now, ...
0
votes
0answers
26 views

Proving an universal function for which there is computable total composition is principal

Let $U(n, x)$ be an universal function for the class of computable functions. Let $c(p, q)$ be a total computable function such that $\forall p, q, x : U(c(p, q), x) = U(p, U(q, x))$ — that is, given $...
0
votes
2answers
49 views

What does it mean for a set of L-sentences $\Sigma$ to be computable?

I was reading these notes and found the definition of computable set of L-sentences (page 101 paper pdf): $$ \ulcorner \Sigma \urcorner = \{ \ulcorner \sigma\urcorner : \sigma \in \Sigma \}$$ where ...