Stack Exchange Network

Stack Exchange network consists of 175 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).

1
vote
1answer
54 views

Completeness property and computability

I have this axiom which states the completeness property of a set $A$: Suppose that $A$ is a set. Every non-empty bounded above subset of $A$ has a least upper bound. But then my prof told me ...
3
votes
1answer
81 views

Proving that a separating set is not computable

Let $X =$ {$d$ : $\psi_d(0)=0\}$ and $Y$ = { $d$ : $\psi_d(0) = 1$ }. Show that if $S\subseteq \mathbb{N}$ has the property $X \subseteq S$ and $Y \cap S = \emptyset$ then $S$ is not recursive. So I ...
4
votes
1answer
62 views

Can bounded addition and multiplication be computable in a non-standard model of arithmetic?

Let $M = (N, \oplus, \otimes, <_M, 0_M, 1_M)$ be a nonstandard model of peano arithmetic. $\oplus$ and $\otimes$ are uncomputable due to Tennenbaum's theorem. For $c \in N$, let $\oplus_{<c}, \...
0
votes
0answers
43 views

Is this function computable?

Given the function $$ f(x) = \begin{cases} 1, & \text{if $x = W(M)$ is the encoding of a turing machine $M$ and $M$ halts if the empty word is entered } \\ undefined, & \text{otherwise} \...
0
votes
1answer
78 views

Do recursively enumerable subsets of $\mathbb{N}$ have a least element

I've been studying MK set theory and computability and I think I'm misunderstanding something. I'm considering some (nonempty) infinite recursively enumerable subset of $\mathbb{N}$. I'm trying to ...
1
vote
2answers
75 views

Proving $L=\left\{ \left\langle M\right\rangle \mid L\left(M\right)=A_{TM}\right\} \in\overline{RE\cup coRE}$

I'd like to prove the following statement: $$L=\left\{ \left\langle M\right\rangle \mid L\left(M\right)=A_{TM}\right\} \in\overline{RE\cup coRE}$$ Where $$A_{TM}=\left\{ \left\langle M,w\right\...
1
vote
2answers
72 views

Transcendental numbers

Can transcendental numbers be plotted? Also, can a computer recognize a transcendental number? I mean, for example, a computer, while computing, understand that the number it is computing is not ...
3
votes
1answer
65 views

Are the “weakly computable” sets precisely the arithmetical sets?

(By "stream" I mean "a sequence that might be finite.") Given a Turing machine $T$ and a natural number $n$, write $T_n$ for the stream of $0$'s and $1$'s that appears in the first position of the ...
0
votes
1answer
40 views

Increasing primitive recursive function range.

So suppose we have a primitive recursive function $f$ with the following property: $x\lt y \Rightarrow f(x)\lt f(y) $ Can we somehow prove that $X=rng(f) $ is also a primitive recursive set? I mean ...
0
votes
2answers
55 views

a hard mapping reduction problem

let L={(M1),(M2)|M1,M2 are TM's and L(M1)={(M)| M is a TM and M2 accepts (M)}} so my guess is L is not in RE but im having a hard time finding the right mapping reduction....any ideas ?
2
votes
1answer
82 views

If the halting set is Turing-reducible to a c.e. set B, is B m-equivalent to the halting set?

Say you have a c.e set $B$. Then $B$ is $m$-reducible to the halting set $K$. If I know additionally that $K \leq_T B$, can I infer $K \equiv_m B$? Intuitively, I would say yes, as the Turing degree ...
1
vote
1answer
42 views

Ackermann function property for positive $n$

Ackermann's function is: $A(0,y) = y + 1 $ $ A(x+1,0)= A(x,1)$ $ A(x+1,y+1)= A(x,A(x+1,y)$ which is a total computable function but not a primitive recursive one. Why is the following property ...
0
votes
3answers
69 views

Prove whether the problem is decidable [closed]

Main topic is to decide if the problem that selected partial μ-recursive function is an injective function is decidable, undecidable or semi-decidable. The function is injective when $\forall a,b\;f(...
3
votes
1answer
198 views

Does there exist an uncountably infinite language?

If an alphabet $= \{a, b\}$ I believe an example of a finite language over that alphabet with positive cardinality would be the set equal to $(a+b)^4$ An example of a countably infinite language ...
2
votes
0answers
47 views

Classes of TMs for which we can solve the halting problem

I am trying to solve a problem concerned with a certain class of Turing machines. Namely, ones that have at most $k$ states for some fixed $k$ on binary tape alphabet, and that are deciders. Given ...
-1
votes
1answer
41 views

Decidability if a given expression is equal to a prime number

Let us assume there is a number which is well-defined and computable, but it is hard to compute it. E.g., $x=\pi^{(\pi^{(\pi^\pi)})}$. It is not even known if the given number is an integer (which is ...
1
vote
1answer
64 views

Does solving the complexity class ALL collapse all Turing degrees?

I came across this paper by Scott Aaronson and though I understand nothing of quantum computing, the fact that there was an (even hypothetical and probably unrealizable) model of ...
4
votes
2answers
83 views

Definition of (lazy) conditional in partial recursive functions

I'm currently working on formalizing the theory of partial recursive functions, and something seems peculiar about the standard definition. The definition of the primitive recursion clause of $\mu$-...
2
votes
1answer
93 views

Do given Turing Machines M,N accepts equinumerous languages?

I was doing some exercises from computability and complexity and then I have stuck on this problem: What type of problem (decidable, semi-decidable, undecidable) is the problem (show it): Do given ...
1
vote
1answer
73 views

I need reference proving Turing computable function with oracle of $\chi_A$ is $A$-recursive

Many introductory book for computability theory introduces turing machine with oracle and $A$-recursiveness and often assumed that they are equivalent. I can prove $A$-recursive functions are turing ...
1
vote
2answers
133 views

Are any of the counterintuitive functions whose existence is postulated by the axiom of choice computable?

Mathematicians often consider a collection of sets and need to select one element from each one. Usually there is a simple constructive way to do so, and everything works out fairly intuitively. As I ...
5
votes
0answers
363 views

Show that $f(x) = \lfloor \sqrt{2} \cdot x\rfloor$ is primitive recursive function.

Trying to wrap my head around primitive recursive functions. Especially bounded minimalisation and how to prove something is indeed primitive recursive. Found the following problem for the subject ...
1
vote
0answers
43 views

A productive set contains an infinite r.e. set.

I am having some trouble showing the following: If P is productive, then P contains an infinite r.e. set W. (It is part of a theorem from Soare's "Recursively Enumerable Sets and Degrees). The ...
2
votes
1answer
108 views

Is the set of finite groups primitive recursive?

This problem bothers me for about two weeks. Let $\mathcal{C}$ be the collections of all finite groups. Is $\mathcal{C}$ a primitive recursive set ? I think we can embed it to a set which is ...
1
vote
2answers
25 views

question about m-degrees : Is $<_m$ except $\{\mathbb{N} \}$, $\{\emptyset\}$ total order?

I'm recently reading computability theory(nigel cutland p.162.). This book introduces $m$-degree $a,b,c...$ and defines $a<_mb$ and shows this is partial order.$<_m$ is a partial order because ...
2
votes
1answer
31 views

What is a Gödel numbering for the free group $F_S$, when $S$ is finite?

Wikipedia's article on presentations of groups says: If $S$ is indexed by a set I consisting of all the natural numbers $\mathbb{N}$ or a finite subset of them, then it is easy to set up a simple one ...
0
votes
0answers
39 views

If $f(x)$ is defined nowhere, and $z(x)$ is zero everywhere, then what is $f(x)z(x)$?

Let $f(x)=\mu y(id^2_1(x+1,y)=0)$ and $g(x)=f(x)z(x)$ where $id^2_1(x,y)=x$ and $z(x)=0$. Then $f(x)$ is defined nowhere and $z(x)=0$ everywhere. Then what is the value of $g$? Is it undefined or just ...
0
votes
1answer
28 views

Why is this TM problem decidable

Please explain to me (like I'm an idiot) how the problem Does M on input Λ ever write a nonblank symbol on the tape? given TM M as an input is decidable. To ...
1
vote
2answers
125 views

What is wrong with my application of the Myhill-Nerode theorem on this language?

Let $L=\left\{ w\in\Sigma^{*}\mid w\text{ has an equal number of 01 and 10}\right\}$ (e.g. $010\in L$) over $\Sigma=\left\{ 0,1\right\} $ I initially tried to prove that $L$ is not regular Proof:...
1
vote
0answers
47 views

Prove $A$ is creative set

Let $\varphi_i$ be the $i$-th partial function of our enumeration. Consider the set $$ A = \{ y \in \mathbb{N} \mid \varphi_{\mathrm{fact}(y)}(y) \downarrow \} $$ I have to prove this set to be ...
0
votes
0answers
146 views

Application of Rice's Theorem

How can I prove, by applying Rice's theorem, that the language L is undecidable? $L = \lbrace \alpha : M_{\alpha}(x) =x^2 \,\,\, \forall x \in \lbrace 0,1\rbrace^* \rbrace $ I think this is a ...
5
votes
1answer
143 views

Is there actually a universal notion of computability?

A few weeks ago, I came upon this great post by JDH and it has been troubling me ever since. The TL;DR for the proof is that we can encode the outputs of any function into the axioms of a set theory ...
0
votes
2answers
299 views

Are uncomputable numbers a subset of real numbers?

I know that Chaitin's constant is an uncomputable real number, but I'm curious as to if there are any proven examples of non-real uncomputable numbers? Could uncomputable numbers be complex? The ...
0
votes
2answers
52 views

not a computable function

Define $\Phi_e^K(x)$ to be the output of the eth Turing machine that has K (the diagonal language) on its oracle tape and x on its input tape. Is the map f: (x,e) $\mapsto$ $\Phi^K_e(x)$ a computable ...
1
vote
1answer
53 views

How to show that the Condition is Diophantine

I'm reading Matiyasevich book Hilbert's Tenth Problem, and I've got a doubt on Chapter 6, Section 6.4: When he defines the relation: For $a,b \in \mathbb{N}$ $explog(a,b)\Leftrightarrow \exists x \...
2
votes
1answer
169 views

Kleene post theorem

Recall Kleene-Post's theorem says that there exists A and B $\leq_T \emptyset'$ that are incomparable. Recall $\cup_s \sigma_s= A$ and $\cup_s \tau_s= B$ where $\sigma_s$ and $\tau_s$ are decided ...
1
vote
1answer
63 views

Arity problem while showing factorial is primitive recursive.

So i have been recently introduced to computability and recursion. And we are doing everything very formally. That is why when forming a primitive recursion we need g,h to be computable and then f is ...
1
vote
1answer
130 views

Application of pumping lemma

Thank you in advance if you can help me out with this. So, i have a grammar that produces strings like [([([(00000)(01101)(011)])(000)])]. Non-empty ( ) can contain [ ] or any number of 0s and 1s. ...
1
vote
2answers
281 views

Classify language as decidable, undecidable but recognisable or unrecognizable

I'm currently studying unrecognizable languages in Turing Machines and came across this problem L1 := {< M > | M is a TM and M accepts at least one string w in {0,1}* with more zeros than ones} I ...
4
votes
0answers
68 views

Why is Feferman's generic hyperarithmetic set not implicitly definable?

I think I've figured this out, but the answer was not what I expected, so I thought I'd run it by the collective mind to see if I'm missing something. Feferman proved [1] that there is a subset $A\...
5
votes
3answers
243 views

Busy Beaver function growth rate compared to computable functions

Fix a definition of a turing machine (or a programming language) and define $BB(n)$ to be the maximum of number of steps a program with less than $n$ states (or with less than $n$ bits) can take to ...
1
vote
1answer
27 views

using quantifiers for predicates, prenex normal form

Say we have $A=B$ iff $\forall x (x \in A \Rightarrow x \in B$) and $\forall y (y \in B \Rightarrow y \in A$) can we write the above as: $\forall x [(x \in A \Rightarrow x \in B$) and $(x \in B \...
2
votes
1answer
75 views

Turing machine - Reducible

Given that Membership Problem is known undecidable Membership Problem: "Given a Turing machine M and string w, does M accept input w?" Emptiness Problem: "Given a Turing machine M, is L(M) = ∅ ?" L(...
1
vote
1answer
124 views

A recursively enumerable theory without a decidable set of axioms.

A theory is a set of first order sentences over some signature. A set of sentences are called axioms for the theory, if the deductive closure of the axioms equals the theory. Now, if I have a ...
-1
votes
1answer
45 views

Is there an effective way of deciding whether a given Godel numbers for a formula or a sequence of formulas??

If we have a Godel number, how can we tell that this number for a formula or for a sequence of formulas effectively? If we have X is a Godel number of some formula, then we can consider this formula ...
0
votes
1answer
22 views

Supplementing $L_A$ with new function symbols

I'm working on this homework problem: We know that all primitive recursive formulas can be expressed in $L_A$. We could have just define new function symbols for them then, to save space. Show that ...
1
vote
1answer
199 views

Is the set of primitive recursive functions (on $\mathbb{N}$) effectively enumerable?

My intuition says that the set of PR functions on $\mathbb{N}$ are not effectively enumerable. I'm trying to come up with a diagonal argument to show this. Suppose that $f_1,f_2,...$ was an ...
0
votes
0answers
51 views

Why define functions with the empty domain? (specifically in primitive recursion)

A function can have an empty domain, as long as the range is not empty, as this satisfies the conditions of existence and uniqueness of images. However such a function can never be called, as there is ...
1
vote
1answer
44 views

What is so Basis-y about Basis Theorems?

In computability theory, a basis for some collection C of classes (eg the $\Pi_1$ classes) is a class B such that every member of C contains a member of B. My question is why a basis is in this sense ...
0
votes
3answers
247 views

Proof that $\textit{INFINITE}_{\text{DFA}}$ is decidable.(Sipser Q.4.10)

The answer of the question is given below: But I could not understand the intuition behind 2 and 3 in the description of the machine below, could anyone explain this for me please?