We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

47 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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)$...
244 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 ...
143 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, ...
200 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 ...
377 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 ...
180 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 ...
192 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 ...
129 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") ...
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 ...
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 ...
216 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 ...
102 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) ...
488 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 ...
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 ...
141 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 ...
168 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 ...
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 ...
380 views

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

165 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 ...
241 views

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

Is there any programming language or system where function equality (extensionality) is decidable?
588 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 ...
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 ...
70 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 ...
109 views

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 ...
197 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-...
95 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 ...
78 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 ...
187 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.....
455 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 ...
82 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 ...
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 ...
519 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 ...
83 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 ...
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 ...
59 views

### Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
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 ...