Questions tagged [computability]

Computability theory a.k.a. recursion theory.

334 questions
Filter by
Sorted by
Tagged with
291 views

Reference for checking primitive recursiveness

There is a theorem that states a function $f$ can be computed with a Turing-machine in time $O(g)$ with primitive recursive $g$ (of the length of input) iff $f$ is primitive recursive. Where can I ...
836 views

Computing Functions with Dynamical Systems

I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes ...
261 views

Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity. Background/Motivation: Coming ...
262 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
127 views

A function is lambda-2-definable iff it is HG computable and provably type correct in lambda-PRED2

I'm having a problem regarding Theorem 5.4.40.3 of Barendregt's Lambda calculi with types (1992), a chapter in Handbook in logic in computer science. (I'm referring to the PostScript version available ...
322 views

351 views

Hilbert's Tenth Problem and nonrecursive Diophantine sets

In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a ...
1k views

What is a reasonable representation/encoding of objects? [closed]

Question What is a reasonable representation of objects (for computability)? What is the criteria that we should apply to see if a representation is reasonable? This answer by Andrej suggests ...
248 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
271 views

Equivalence problem for one-counter automata

I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones? ...
167 views

Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
256 views

How to describe the set of “all computable functions” using Coq?

Would the set of all computable functions be just the set of all maps of the form f : forall n : nat, P n -> nat where ...
271 views

The Complexity of Advice in Computational Indistinguishability

One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc. ...
398 views

Efficient Algorithm for bilinear pairing on ECC

Bilinear Pairing in the elliptic curves is a wonderful mathematical mapping which is usually defined by the map $e:G_{1} \times G_{1} \rightarrow G_2$ for some groups of $G_{1}$ and $G_{2}$. For ...
75 views

Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula ...
85 views

Which computational models support bigotous programs?

A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem. In fact, its pretty ...
139 views

Notions of Computability at Higher Type III

I've recently found a very nice survey paper called "Notions of Computability at Higher Type" by John R. Longley. The paper says it is part of a 3-part series, with the 3rd concerning non-extensional ...
164 views

Exact catchup point between SGH and FGH of ordinals?

An ordinal hierarchy is a way to assign a function $f_{\alpha} : \mathbb{N} \rightarrow \mathbb{N}$ to each (recursive) ordinal $\alpha$. The corresponding functions are expected to be monotone and ...
351 views

Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and define $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. Question: Does the function $\Delta$ eventually dominate every ...
894 views

Why have computer scientists chosen recursor instead of iterator in primitive recursion?

I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more ...
516 views

Is one definition of the word paradox, “something that can be used to prove the halting problem undecidable?”

I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ......
672 views

Examples of reversible computations

Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly ...
1k views

Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
387 views

Is every busy beaver strictly monotonic asymptotically?

To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing ...
649 views

Enumerating decidable languages

[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.] Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
189 views

Is there any relationship of hardness between the two problems?

Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D. Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y ...
208 views

Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm? ...
257 views

Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states: We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
122 views

Complexity of type-checking in relation to complexity of normalization

In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can ...
255 views

Primitive Recursive Definition : Binary numbers

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the ...
194 views

Arithmetic Analogues of P versus BPP

In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there? If there is no such analogy, why is randomness in the resource bounded case ...
932 views

Transition Diagram of a Universal Turing Machine

I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? I need this as a reference, so preferably a book or a published ...
460 views

Show that minimal CFG is undecidable via mapping reduction

Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE. The ...
523 views

Original proof that “almost all decision problems are uncomputable”?

Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!
Consider the following ternary relation $R\subseteq\mathbb{N}^3$: $(p,q,m)\in R$ iff $p,q>0$ and there is a set $S\subseteq \{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $|S|=m$ and \$\frac{...