Questions tagged [computability]

Computability theory a.k.a. recursion theory.

44 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15
votes
0answers
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 ...
13
votes
1answer
299 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)$...
12
votes
0answers
237 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 ...
11
votes
0answers
128 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, ...
10
votes
0answers
197 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 ...
10
votes
1answer
363 views

Reversible Turing tarpits?

This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ...
8
votes
0answers
175 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 ...
8
votes
0answers
189 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 ...
8
votes
0answers
126 views

What is known about reduction by “$P_1$ interprets $P_2$” for generalized programming languages?

Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
8
votes
0answers
161 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 ...
7
votes
0answers
143 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 ...
7
votes
0answers
214 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 ...
6
votes
0answers
94 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) ...
6
votes
0answers
485 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 ...
5
votes
0answers
84 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 ...
5
votes
0answers
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 ...
5
votes
0answers
157 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 ...
5
votes
0answers
349 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 ...
4
votes
0answers
131 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 ...
4
votes
0answers
366 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}...
4
votes
1answer
148 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 $...
3
votes
0answers
32 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 ...
3
votes
0answers
249 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: $\...
3
votes
0answers
147 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{...
3
votes
0answers
164 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 ...
3
votes
0answers
233 views

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

Is there any programming language or system where function equality (extensionality) is decidable?
3
votes
0answers
585 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 ...
3
votes
0answers
191 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 ...
2
votes
0answers
69 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 ...
2
votes
0answers
107 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 \...
2
votes
0answers
113 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 $...
2
votes
0answers
55 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 ...
2
votes
0answers
196 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-...
2
votes
0answers
94 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 ...
2
votes
0answers
77 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 ...
2
votes
0answers
185 views

Particle collisions for universal computation

Proof of universality of Game of Life is straightforward (CAFAQ): (two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: 111111.....
2
votes
1answer
426 views

Langton's ant questions

I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless. So that is why I'm asking. 1) Is there a mathematical ...
1
vote
0answers
78 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
42 views

Proof for multiplicative dominance of universal probability distribution

I'm looking for the proof of the Leonid Levin theorem that states that the universal prior distribution function multiplicatively dominates all other functions of its type. The original article is ...
1
vote
0answers
513 views

Is it possible a recursive compression algorithm based on L-systems or a variant?

According to the Internet, there's a way to get an L-system's rules by it's string, unfortunately I can't read it because it's behind a paywall. Question: If that paper is right, is it possible to ...
1
vote
0answers
82 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 ...
1
vote
0answers
170 views

What is the the optimal computational model for memristive style CMOS?

I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be ...
0
votes
0answers
129 views

Oracle that will provide any computable information about another oracle

Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then ...
0
votes
0answers
853 views

Understanding the HRU Model (Protection in Operating Systems)

As of now I am feeling terrible because I have spent the past 10 hours trying to understand this paper titled "Protection in Operating Systems" by Harrison, Ruzzo and Ullman. At this point, any help ...