# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

348 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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!
120 views

152 views

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 ...
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 ...
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 ...
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, ...
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 ...
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. ...
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 ...
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, ...
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 ...
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 ...
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$...
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? ...
93 views

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]. ...
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: ...
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 ...
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 ...
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 ...
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 ...
254 views

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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?