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

2,155 questions
Filter by
Sorted by
Tagged with
$\forall f: \mathbb{N} \to \mathbb{N}$ primitive recursive function, whose most values are equal to $0$, in general can there be algorithmically found a number $N$ such that $(\forall i > N)\,\,f(i)... 1answer 33 views Show that infinite sum/product of primitive recursive functions can be non-recursive. first of all there is another recently posted question with almost the same title which got closed (this is the question: Can an infinite product of recursive functions be non-recursive?). So my ... 0answers 15 views A Computable function for Partial Recursive Function We have a computable function$F = (x_0, x_1)$for set$M = \{f(x_1) ; f $is partial recursive$ \}$. That means$F$is a partial recursive function as well. Suppose function$g \simeq F(x, x) + 1$. ... 1answer 31 views What if both a set and its complement are recursively enumerable? [closed] If both a set and its complement are recursively enumerable, is the set recursive? If so, how do we prove it? 0answers 19 views Proof that the halting set is recursively enumerable using Dovetailing I am trying to understand how the halting set 𝐾:={(𝑖,𝑥)∣ program 𝑖 halts when run on input 𝑥} is recursively enumerable i.e. Turing machines that halt on a blank tape form a recursively ... 2answers 30 views Intuitve Proof that the halting set is recursively enumerable I am trying to understand intuitively how the halting set$K := \{(i, x) \mid$program$i$halts when run on input$x\}$is recursively enumerable. Is there a simple explanation which says why this is?... 1answer 63 views Why can't Desmos integrate$\int_0^\infty{\frac{\sin x}{x}dx}$[closed] Via Leibniz Rule and differentiation under the integral sign, or Feynman's Method I guess, the answer is clearly$\pi/2$. When you plug infinity into Desmos as a bound of integration it inherently ... 1answer 182 views Kunen exercise IV.4.13 (4): Topological version of effective AC I am dealing with Kunen's The Foundations of mathematics exercise IV.4.13 (4): Let$X$denote the Cantor set. Prove if$S\subset X\times X$is open, then there is an$F\subset S$such that$F$is the ... 0answers 58 views Is there a function that grows faster than all computable functions but does not have this property? Does there exist a strictly increasing function$f$from$\mathbb{N}$to$\mathbb{N}$which grows faster than all computable functions, but which does not have the following property: For all ... 1answer 22 views turing-reduction Proof:$A = \{(u,v) | T(M_u) \subseteq T(M_v)\}$by showing$H_0 \leq A$i have a hard time understand turing-reductions. This is my first exercise without a solution and I don't know wheter this is the proper solution. (The only thing i know for sure is, that A is indeed ... 1answer 82 views Running an infinite amount of Turing Machine steps in a finite amount of time: What consequences? If we had some sort of black box that allows us to run an infinite amount of steps of a Turing machine in a finite amount of time (no limitation on the length of the tape), and be able to output ... 2answers 71 views Is there a rote algorithm to tell whether a tensor (of two vectors) can be reduced to an elementary tensor? Given vector spaces$V$and$W$over a field$F$, is there an algorithm that can decide whether an expression $$v_{1}\otimes w_{1} + \cdots + v_{n}\otimes w_{n}$$ can be reduced to an expression of ... 0answers 10 views f,g are primitive recursive if$f(x,0)=\lambda_0 (x), g(x,0) = \lambda_1 (x)$and$f(x,y+1)= h_0(x,y,f(x,y),g(x,y)), g(x,y+1)=h_1(x,y,f(x,y),g(x,y))$. So I'm working on showing the following right now:$\lambda_0,\lambda_1,h_0,h_1$are all primitive recursive functions. f and g are defined the following way: $$f(x,0) = \lambda_0(x)\\ g(x,0) = \... 2answers 62 views The range of a non-computable function that grows faster than computable functions is undecidable Let f be a non-computable function that grows faster than every computable function. I have to prove that R=\text{Range}(f) is non-decidable. I'm trying to prove the statement by contradiction. ... 1answer 32 views finding the computable function in s-m-n theorem. in s-m-n theory if \phi_e^{(m+n)}(x,y) is a computable function with index e then there is a total comutable (m+1)-ary function s_n^m(e,x) such that:$$\phi_e^{(m+n)}(x,y)=\phi_{s_n^m(e,x)}^n(y)$$... 2answers 188 views Can we compute all digits of the Euler-Mascheroni constant? Let \gamma be the Euler-Mascheroni constant from calculus. Is there an algorithm that computes the n-th digit of the decimal expansion of \gamma given n as input? For all we know \gamma ... 0answers 51 views When is an infinite series computable? A real number is called computable if there is an algorithm that computes it up to any desired precision. Suppose f(x) is an elementary function s.t. \sum_{n=1}^\infty f(n) converges (for ... 1answer 38 views How to show that if there's a mapping reduction from L to its complement, it doesn't imply that L∈R? I have the following prove/disprove claim: if$$L\leq_m L^{c}$$then$$L\in R$$I figured out that I can theoretically provide a counter-example where both$$L,L^{c}\not\in(RE\cup co-RE)$$but ... 0answers 37 views Is it true that, for any X Polish uncountable, every boldface class of X is lightface with respect to some oracle? I am wondering the question in the title: let X be uncountable Polish. Consider the standard Borel structure on X; that is, \mathbf{\Sigma}_1^0(X) are the open sets, etc.. Is it true that, with ... 0answers 83 views Kleene's recursion theorem implies closure under unbounded search I want to show that Kleene's recursion theorem, i.e. for every k+1-ary function G there exists an index f such that$$\{f\}(\bar{x})\simeq G(f,\bar{x}),$$implies closure under unbounded search ... 1answer 41 views Can one capture the properties of Turing machine using only function definitions? I am trying to capture the definition of Turing machines as abstractly as possible (without any implementation). Will a definition like this do the trick? Definition [Turing machine]: Let \mathbb{L}... 2answers 62 views how can prove n^n is primitive recursive I try to prove n^n is primitive recursive,first i try to releationate this proof with the proof of x^y, but in this case is different, because the base is not the same. So my attempt was to see ... 0answers 44 views Can anyone explain this paper :? " The world problem: on the computability of the topology of 4-manifolds" Link to the paper is here: https://arxiv.org/pdf/gr-qc/0506019.pdf The author explains that the problem of determining if two 4-manifold are related by a homeomorphism is undecidable. And that this is ... 0answers 32 views Confusing recursive function definition I'm reading through https://plato.stanford.edu/entries/recursive-functions/ and came across a confusing part: One means of doing so is to first use recursion on the type ℕ→ℕ—a simple form of ... 6answers 4k views In what sense does a number "exist" if it is proven to be uncomputable? Uncomputable functions: Intro The last month I have been going down the rabbit hole of googology (mathematical study of large numbers) in my free time. I am still trying to wrap my head around the ... 0answers 125 views Are the algebraic real numbers an automatic structure? In the 1950's, Julius Büchi showed that (\mathbb{N},S,+,0) is not merely a decidable structure as Presburger had shown, but an automatic structure, i.e. there is an encoding of the natural numbers (... 0answers 52 views Using diagonalization approach, how to show the existence of at least one set of natural numbers that is not computable? I have studied the halting problem and the concepts of decidability and computability, however, I am stuck with the transfer of Turing machines to sets of natural numbers. Specifically, using the ... 1answer 106 views Why is Q (Robinson arithmetic) both undecidable and axiomatizable? I'm studying computability and its terminology is very confusing. So, Q (Robinson arithmetic) is undecidable AND axiomatizable, right? But if axiomatizable means that the collection of Q theorems is ... 1answer 25 views Recursive in a \Sigma^0_2-singleton implies recursive I've encountered two related remarks that I can't figure out. They are: If a real number is recursive in a \Sigma^0_2-singleton, then it is recursive; This is best possible, as \{\emptyset^{(\... 1answer 72 views Can you define functions which are not primitive recursive, yet total, in Type Theory? [closed] Ackermann's function is total but not primitive recursive. Can one define Ackermann's function in Type Theory, ie: Can you define functions which are not primitive recursive, yet total, in Type Theory?... 1answer 62 views Not computable but left computable number I can't find an example of number that is not computable but it is left computable. In general is already difficult to give example of non computable numbers, but I can't even find any number which is ... 1answer 33 views If a problem is \Sigma^1_1-hard, it is then not in co-RE? I am reading a paper where the authors prove that a certain problem is \Sigma^1_1-complete; in particular, it is also \Sigma^1_1-hard. Does this imply that the problem is not co-recursively ... 0answers 33 views is {w in {0,1}* | #0(w) = #1(w)} a regular language? is L = {w in {0,1}* | #0(w) = #1(w)} a regular language? I've managed to prove it is context free, but this doesn't really help. I've also saw a hint (here - prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} ... 1answer 20 views A proper general recursive function which grows slower than a primitive recursive function. Does there exist a general recursive function which is not primitive recursive, which grows slower than some primitive recursive function? In fact, is there such a function which is bounded by a ... 1answer 165 views Let W\subseteq\omega be an infinite c.e. set. Show that there is an infinite X\subseteq W such that X is computable. If I can prove that X is c.e. and \omega \setminus X is c.e. then I can prove that X is computable by the theorem "Let W \subseteq \omega. Then W is computable iff both W and \omega \... 1answer 75 views Are there countably many symbols (in the context of computation theory)? I've seen this kind of argument on countability of Turing-recognizable languages in several places: For any Turing machine M consider it's encoding into a string \langle M \rangle. This encoding ... 1answer 23 views Is the number of real numbers that satisfy this definition of ε-computability always countable? My question basically boils down to “is there a minimum error bound to which almost all numbers can be computed to?” It’s possible that the definition I’m inventing here for rigor already exists, but ... 0answers 105 views Models of PA inside a computationally weaker theory I have two questions about the computability power of theories, one about models of {PA} and the other about the model theory itself: Is it possible to create a model of {PA} inside a weaker ... 0answers 38 views What's the Theorem that asserts that not all of Axiom of Choice, Axiom of Infinityand Computability of all functions can be true consistently? As far as I know, all three of the following statements cannot be true at the same time in a consistent axiomatic system: Axiom of Choice Axiom of Infinity All functions are computable What's the ... 1answer 33 views Partial and total functions definitions I have an IT background and I'm trying to find proper and formal definitions of partial and total functions. I'm unsure about my answers, this is why I'm posting here. Do you think you could give me ... 2answers 60 views Generalization of nonexpressibility of solutions Are there any ideas/areas of math that generalize the idea of when a solution to a question can be expressed in some given formal system? Something that (at least in spirit) covers results like No ... 2answers 86 views Forcing Computable Functions I was wondering about the following issue and could not see how to address it. Let Comp_V(\omega) be the set of all computable funtions over \omega in some universe V of ZFC. Is it possible to ... 2answers 32 views Is this modified characteristic function computable? Let P(n,k) be decidable and define$$f(n)=\begin{cases}1&\text{if there are exactly two }k\text{ with }P(n,k),\\ \text{undefined}&\text{otherwise}.\end{cases}$$I wonder if this function is ... 1answer 94 views Is almost every definable number uncomputable? We know that almost all real numbers are undefinable. We also know that almost all real numbers are uncomputable. We also know that there are numbers that can be defined but not computed. However, ... 2answers 264 views What is the author trying to explain here? From Aaronson's 2006 lecture notes for PHYS771: ... Why the Incompleteness Theorem doesn't contradict the Completeness Theorem? The easiest way to do this is probably through an example. Consider ... 1answer 157 views Does an unsolvable game exist? (And can you formulate an example?) Let me first of all be more clear by explaining what a unsolvable game is. An unsolvable game is a game which can never be solved, not even hypothetically, because no strategy can force a win if the ... 2answers 42 views Must every Turing-complete language be able to enumerate precisely those algorithms which return a particular value? This kind of enumeration is particularly easy with some languages. For example, using SKI combinators, start with the expression \mathbf{SKK} (Church encoding for 1) and systematically apply the ... 1answer 87 views Is there a test for convexity? This is a very heterodox question. But here is the context. I'm programming a computational package, and the user may write/define a cost function freely, e.g.$$ cost(x,y) = e^{|x-y|} (x-y)^2.$$Now,... 0answers 45 views Reduction of RE and REC languages Suppose$L_1$is reduces to$L_2$in polynomial time,$L_1\leq_p^\mathsf{}L_2.$we know that if$L_2$is RE then$L_1$is also RE and$L_2$is REC then$L_1$is also REC. And also I know that if$...
It’s my understanding that Julius Büchi showed that $WS1S$, the weak monadic second-order theory of one successor is decidable by a finite-state automaton, and that this implies that Presburger ...