Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
4
votes
2answers
338 views

About the decidability of sets enumerated in non decreasing order

It is well known that a set of numbers enumerable in nondecreasing order is decidable. However, the typical proof, by cases on the finiteness of the enumerated set, is not constructive. In general, it ...
4
votes
1answer
778 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 ...
4
votes
1answer
638 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!
4
votes
1answer
120 views

Representation as sum of unit fractions: primitive recursive?

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{...
4
votes
1answer
184 views

Explanation of 1-generic to prove undecidability of halting problem

This question is about an answer in question Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? Bjørn Kjos-Hanssen answer ...
4
votes
1answer
1k views

Initial conditions for universal Rule 110

In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer. I was wondering what specific initial conditions ...
4
votes
0answers
133 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
393 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
152 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
2answers
347 views

Does the physical Church-Turing thesis imply that all physical constants are computable?

The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine. Let us create a machine that, for example, outputs the digits of the ...
3
votes
2answers
473 views

Does an infinitely long tape make any difference when proving theorems about Turing Machines?

Standard accounts of Turing Machines in the literature assume an infinitely long tape in at least one direction (and indeed infinitely time long to perform its computations). Clearly in practice no ...
3
votes
2answers
167 views

Can complexities differ w.r.t. different computational models?

I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable ...
3
votes
2answers
703 views

Is the following language in RE?

There's a computability theory exercise that had me stuck for a long time. I have the language L={ M | there exists a reduction from HP to L(M) } I managed to ...
3
votes
1answer
317 views

More complex integers

In connection to this question: Expected values of Kolmogorov complexity in a random sample Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > ...
3
votes
1answer
375 views

Can all mathematical operations be encoded with a Turing Complete language? [closed]

In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using: Sequence Selection Iteration After completing a Computer Science ...
3
votes
1answer
191 views

Computability of infinite-dimensional vector space

So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be ...
3
votes
2answers
2k views

What are “$\mu$-recursive functions” and $\mu$-calculus?

I saw in this question a reference to $\mu$-recursive functions or $\mu$-calculus as some computation model equivalent to Turing machines and $\lambda$-calculus. I know about these two but never heard ...
3
votes
2answers
168 views

Compactness of domino tilings

I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
3
votes
1answer
671 views

Is simply typed lambda calculus equivalent to primitive recursive functions

It's well known that the computation models untyped lambda calculus and $\mu$-recursive function are equivalent in terms of computability (in fact they are both Turing complete.) It is also well known ...
3
votes
1answer
220 views

Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
3
votes
1answer
197 views

Decidability of first-order theory of real closed fields with functions

By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over ...
3
votes
1answer
105 views

Is it possible to determine if a reduction is correct?

Suppose we have an arbitrary term, x, in Lambda Calculus, or in an equivalent turing-complete system. Suppose we ask an oracle what is the normal form of that term, ...
3
votes
1answer
2k views

Langton's ant highway conjecture and undecidability

I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'. I also read that it has been ...
3
votes
1answer
303 views

Abstract definition of universal computation

There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known ...
3
votes
1answer
69 views

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ? $$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$ Second question: if it is possible that every $L$...
3
votes
1answer
120 views

What is the simplest universal unidimensional interaction net system?

The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? ...
3
votes
1answer
93 views

Results about computability power or limitations of shared read/write registers

I want to know more results about the computability power or limitations of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory. Two typical examples are: [1]. ...
3
votes
1answer
159 views

n-approximable functions

I came across the following definition in a paper: We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: ...
3
votes
2answers
256 views

Runtime of a TM enumerator

Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)? For simplicity let's say the string ...
3
votes
1answer
277 views

Are randomly generated infinite patterns computable?

Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the ...
3
votes
1answer
239 views

Is $ALL\setminus(RE \cup co-RE)$ empty? [duplicate]

Possible Duplicate: Are there languages that are not in RE nor CO-RE? Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or ...
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
254 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
129 views

What is the largest complexity class that a non-Turing complete proof assitant, like Coq, can achieve? [duplicate]

Given that all functions in Coq will terminate, it cannot cover the entire $RE$. So what is the class it can achieve? Is it $R$?
3
votes
0answers
199 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
3
votes
0answers
148 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}...
3
votes
0answers
166 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
258 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
591 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
5answers
344 views

A definition of computable numbers that requires to “wait an infinite amount of time” to get the correct result; how to make this precise

Consider the following definition: A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its ...
2
votes
2answers
372 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
2
votes
2answers
225 views

Would it be possible for a compiler to convert a recursive sum into the average formula?

def sum1(n): if n==0: return 0 else: return n + sum1(n-1) def sum2(n): return n*(n+1)/2 A compiler can not convert ...
2
votes
3answers
608 views

Template Metaprogramming and Turing Completeness

I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that ...
2
votes
3answers
327 views

Is there any programming language in which any equivalent program has a unique, decidable normal representation?

Is there any programming language in which any equivalent program has a unique normal representation, and that normal representation is decidable? Is other words, suppose A and B are programs ...
2
votes
2answers
157 views

how to formalize the class(?) of computational models and their equivalence

Introductory books to theoretical computer science usually introduce a the Turing machine and some of its variants, as well as the Random Access machine as computational models. Sometimes more ...
2
votes
1answer
173 views

Is there a difference between incompleteness and unknowable? [closed]

Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never ...
2
votes
1answer
484 views

Computability Theory prerequisites

What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?
2
votes
3answers
171 views

Reference request: Arithmetic circuit complexity

I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
2
votes
1answer
671 views

Undecidable problems not Turing-complete?

are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting ...

1
3 4
5
6 7