Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

72 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15 votes
0 answers
1k views

Can a Penrose tile cellular automaton be Turing-complete?

This question was based on an incorrect premise ... see Colin's comment below. Forget it. This was inspired by the discussion on this Math Overflow question. First, I need to define our terms. In a ...
Peter Shor 's user avatar
14 votes
0 answers
348 views

Computability of a "weird" set

The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying $$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$ are absurdly high. This leads to ...
Dominic van der Zypen's user avatar
13 votes
1 answer
491 views

Gap between $BB(n)$ and "second largest" $BB(n)$

If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$. What can we say about the second largest number in $HT(n)$...
Geoffrey Irving's user avatar
11 votes
0 answers
235 views

Can two-tape read-only Turing machines recognize any recursive language?

Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes. It cannot write on the tapes, but it can move on them in both ways, even move off from the input. So for example, ...
domotorp's user avatar
  • 14k
10 votes
0 answers
263 views

The halting problem in computational models weaker than Turing machines

What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it. I am ...
babou's user avatar
  • 1,542
9 votes
0 answers
327 views

Applications of "Seemingly Impossible Functional Programs"

What are some practical applications (existing or potential) for Martin Escardo's "Seemingly Impossible Functional Programs"? For starters, here are a few from: Alex Simpson’s Lazy functional ...
NietzscheanAI's user avatar
8 votes
0 answers
127 views

Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?

Abstractly, by a programming language that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, ``the program $p$ on string $x$ halts with output $y$.&...
Siddharth's user avatar
  • 851
8 votes
0 answers
178 views

Cell probe model vs transdichotomous ram

can someone explain me the difference between those two (cell probe model and transdichotomous ram)? In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
Matthew's user avatar
  • 81
7 votes
0 answers
138 views

Halting problem for finitary PCF

Is the halting problem decidable for finitary PCF? By "halting problem" I mean the problem of deciding whether a closed PCF term evaluates to bottom under the denotational semantics of PCF. ...
PaR's user avatar
  • 71
7 votes
0 answers
239 views

What are considered to be the most canonical and important consequences of the recursion theorem?

The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a ...
Andrej Bauer's user avatar
  • 29.1k
7 votes
0 answers
150 views

What can you do with a moving knife besides cutting a cake?

In the fair cake-cutting, two different computational models are used: A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies; A continuous ...
Erel Segal-Halevi's user avatar
7 votes
0 answers
225 views

Is there a programming language where any arbitrary recursive function can be fused?

Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
MaiaVictor's user avatar
  • 3,137
6 votes
0 answers
218 views

Small universal monotone Turing machines

This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
user76284's user avatar
  • 662
6 votes
0 answers
183 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 ...
Max New's user avatar
  • 1,695
6 votes
0 answers
380 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 ...
r.e.s.'s user avatar
  • 171
5 votes
0 answers
282 views

Has there been any development of complexity theory for other Turing degrees than 0?

(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.) Complexity theory can be very broadly ...
Gro-Tsen's user avatar
  • 841
5 votes
0 answers
94 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 ...
Stella Biderman's user avatar
5 votes
0 answers
96 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 ...
Christopher King's user avatar
5 votes
0 answers
206 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 ...
NisaiVloot's user avatar
  • 1,292
5 votes
0 answers
523 views

Prove Post Correspondence Problem Non-Recursive Without Reduction

Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...
Raphael's user avatar
  • 4,575
4 votes
0 answers
317 views

How to prove that a language that allows infinite loops is still not Turing-complete?

CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
paulotorrens's user avatar
4 votes
0 answers
130 views

Reference for "A Turing machine cannot be equipped with an oracle for itself"

Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
Alex Meiburg's user avatar
4 votes
0 answers
106 views

Logic of learning

Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation? I was Mathematician and Computer Science (dual degree undergraduate) ...
Mahdi Heidarpoor's user avatar
4 votes
0 answers
134 views

Lovasz Theta as a short certificate

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...
Turbo's user avatar
  • 12.9k
4 votes
0 answers
456 views

Are there connections between Turing machines and symbolic dynamic systems?

On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association": $\sigma(\ldots, x_{-1}...
Mooncer's user avatar
  • 431
4 votes
1 answer
178 views

Jumping (Busy) Beaver variant

Is the following Busy Beaver variant known? A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $...
Marzio De Biasi's user avatar
3 votes
0 answers
81 views

Generalizing Quines: Outputting an Arbitrary Function of Source Code

​​A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-...
Pooya Farshim's user avatar
3 votes
0 answers
84 views

Expressive power of lambda-calculus with restricted application

Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
pbaren's user avatar
  • 653
3 votes
0 answers
123 views

Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)

I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...
arbolverde's user avatar
3 votes
0 answers
60 views

Is relativization statement-dependent or proof-dependent?

I'm relearning some computability theory, and have encountered the idea of relativization of results to arbitrary subsets of $\omega$ and the subtlety of figuring out what the correct relativized ...
Alex Mine's user avatar
  • 139
3 votes
0 answers
33 views

references for optimal computation under memory constraint?

Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width) There is this reference ...
Yaroslav Bulatov's user avatar
3 votes
0 answers
263 views

A sequence wherein the Kolmogorov complexity of the terms does not increase

I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that : It can be proved in some axiomtic system $S$ that: $\...
ARi's user avatar
  • 405
3 votes
0 answers
152 views

The complexity of the disjoint union of a sequence of complete problems

Suppose that for every $k \in \mathbb{N}$ the decision problem $A_k$ is hard for $\mathsf{N}k\text{-}\mathsf{ExpTime}$. What is the complexity of their disjoint union $A = \{ (k,x) \mid k\in \mathbb{N}...
comco's user avatar
  • 203
3 votes
0 answers
177 views

How useful is program search in the field of programming-language theory?

I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter ...
MaiaVictor's user avatar
  • 3,137
3 votes
0 answers
408 views

Is there any system where function equality (extensionality) is decidable?

Is there any programming language or system where function equality (extensionality) is decidable?
MaiaVictor's user avatar
  • 3,137
3 votes
0 answers
603 views

Another weird $O(N \log{N})$ Turing machine

This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial ...
Marzio De Biasi's user avatar
3 votes
0 answers
193 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
kryptos's user avatar
  • 460
2 votes
0 answers
77 views

Many-one equivalence of sets that differ finitely

[This is a duplicate of my question from Mathematics Stack Exchange: https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely I am posting it here since it ...
ijon's user avatar
  • 95
2 votes
0 answers
60 views

Complexity measures for semi-decidable problems

Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...
Nicola Gigante's user avatar
2 votes
0 answers
122 views

Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
Noel Arteche's user avatar
2 votes
0 answers
118 views

Are there more learnable but undecidable cases except the halting problem

Per request, I cross post the question here which is original from math.stackexchange In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
Mountain's user avatar
  • 121
2 votes
0 answers
111 views

Halting behavior of a randomly selected Turing machine?

Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input. Is $\lim_{k \to \infty} \frac{h(k)...
user101010's user avatar
2 votes
0 answers
106 views

how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
wwjohnsmith's user avatar
2 votes
0 answers
149 views

Are there analogues of Specker sequences for other complexity classes?

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
Beau Madison Mount's user avatar
2 votes
0 answers
168 views

A variant of the tiling problem

A classic tiling problem with Wang tiles has the form: Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints $H,V\subseteq T\times T$, is there a way to tile a $w\times h$ rectangular grid with $...
phs's user avatar
  • 565
2 votes
0 answers
65 views

Simple version of Wang's tessellation problem

I'm reading about Wang's tessellation problem and the text mentions a simpler version: If we consider a finite set of tiles $W_{n}=\{w_{1},...,w_{n}\}$ where $n$ is bounded then the claim is that now ...
Belgi's user avatar
  • 161
2 votes
0 answers
210 views

Computing dual of the spectral norm of tensor of order 3

It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a $3^{rd}$ order tensor $T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$ is NP-...
Kcafe's user avatar
  • 151
2 votes
0 answers
139 views

density of undeciability

Consider a function $f:\mathbb{N} \to \{0,1\}$ whose is defined in terms of some universal Turing machine $U$. If $U$ halts when given $x$ as input then $f(x)=1$, otherwise $f(x)=0$. Clearly the ...
N. Virgo's user avatar
  • 709
2 votes
1 answer
280 views

What kind of string is produced by successive application of argmax M

Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$. Start with some $\omega_0$. Each subsequent ...
Gleb's user avatar
  • 93
2 votes
0 answers
80 views

Efficient asympotically universal predictors

A computable predictor is an algorithm $A$ computing a function $f_A : \{0,1\}^* \rightarrow \{0,1\}$. We regarding the function as providing a predicted continuation of a finite binary sequence. We ...
Vanessa's user avatar
  • 2,151