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,639 questions
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 ...
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 ...
62 views

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 ...
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 ...
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 ...
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 ...
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$-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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:...
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 ...
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 ...
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 ...
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 ...
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 ...
53 views

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 \... 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 ... 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 ... 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. ... 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 ... 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  that there is a subset$A\...
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 ...