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
0
votes
1answer
41 views

For any primitive recursive $f$ whose most values are equal to $0$, can there be found $N$ after which all of values of $f$ are equal to $0$?

$\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)...
0
votes
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 ...
0
votes
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$. ...
0
votes
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?
0
votes
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 ...
0
votes
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?...
0
votes
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 ...
7
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
4
votes
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 ...
0
votes
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) = \...
2
votes
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. ...
1
vote
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)$$...
7
votes
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$ ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
2
votes
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}$...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
40
votes
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 ...
13
votes
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 (...
2
votes
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 ...
2
votes
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 ...
0
votes
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^{(\...
4
votes
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?...
0
votes
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 ...
0
votes
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 ...
0
votes
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)} ...
0
votes
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 ...
0
votes
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 \...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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, ...
3
votes
2answers
264 views

What is the author trying to explain here?

From Aaronson's 2006 lecture notes for PHYS$771$: ... Why the Incompleteness Theorem doesn't contradict the Completeness Theorem? The easiest way to do this is probably through an example. Consider ...
2
votes
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 ...
0
votes
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 ...
7
votes
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,...
0
votes
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 $...
0
votes
0answers
33 views

What is the interpretation of Presburger Arithmetic in WS1S?

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

1
2 3 4 5
44