# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

331 questions
Filter by
Sorted by
Tagged with
15answers
9k views

### A simple problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
10answers
14k views

### What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
2answers
7k views

### Realizability theory: difference in power between Lambda calculus and Turing Machines

I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering). Andrej Bauer wrote, here, that some functions are realizable ...
3answers
2k views

### Is there a sensible notion of an approximation algorithm for an undecidable problem?

Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be ...
5answers
19k views

### Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
5answers
2k views

### Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-...
2answers
2k views

### Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing ...
7answers
4k views

### Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
7answers
6k views

### Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
9answers
19k views

### What is the difference between non-determinism and randomness?

I recently heard this - "A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
4answers
3k views

### Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question. The classical proof of the ...
7answers
6k views

### What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
4answers
854 views

### Correspondence between complexity classes and logic

I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, ...
5answers
2k views

### Programming languages for efficient computation

It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard ...
6answers
5k views

### What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness. So far I've created a game state ...
4answers
3k views

### Can a probabilistic Turing machine solve the halting problem?

A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem? That is, can a ...
1answer
2k views

### Halting problem, uncomputable sets: common mathematical proof?

It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N. A proof could be ...
1answer
919 views

### Programming languages with canonical functions

Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
2answers
2k views

### What functions can System F not compute?

In this wikipedia article on Turing Completeness it states that: The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed ...
6answers
2k views

### Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning:...
6answers
2k views

### How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
4answers
5k views

### Church's Theorem and Gödel's Incompleteness Theorems

I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are ...
4answers
1k views

### Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton? This would almost disprove Wolfram's "Principle of Computational Equivalence": ...
2answers
1k views

### To what extent can an algorithm predict the time complexity an arbitrary input program?

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. I can, however, certainly write a program that can ...
5answers
1k views

### Problem teaching computability

I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. ...
1answer
1k views

### Class of functions computable by Coq

Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)
3answers
828 views

### Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank ...
3answers
700 views

### Is there a result in computability theory that does not relativize?

I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that Our axiomatization has its limit: it cannot prove any results in computability ...
3answers
2k views

### If an abstract machine can simulate itself, does that make it Turing complete?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
2answers
891 views

### $\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
5answers
2k views

### (False?) proof for computability of a function?

Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable: Either for all n, $0^n$ appears in $\pi$, or there is ...
2answers
2k views

### What are the limits of total functional programming?

What are the limitations of total functional programming? It is not Turing-complete, but still supports a large subset of the possible programs. Are there important constructs that you could write in ...
3answers
1k views

### Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
1answer
552 views

### Combinators for the Primitive Recursive Functions

It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?
5answers
4k views

### Is it possible to test if a computable number is rational or integer?

Is it possible to algorithmically test if a computable number is rational or integer? In other words, would it be possible for a library that implements computable numbers to provide the functions <...
2answers
538 views

### Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).: If A ...
3answers
2k views

### Why has hypercomputation research died down?

I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could ...
2answers
580 views

### For a random oracle R, does BPP equal the set of computable languages in P^R?

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a ...
1answer
7k views

### How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
2answers
458 views

### Problems with efficient solution except for a small fraction of inputs

The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is ...
4answers
806 views

### Can testing show the absence of bugs?

$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line. How many points are required to uniquely determine a ...
5answers
3k views

### Can a computer simulate itself as part of a simulated world?

Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything ...
1answer
2k views

### What are the limits of computation in this universe?

I understand that Turing completeness requires unbounded memory and unbounded time. However there is a finite amount of atoms in this service thus making memory bounded. For example even though $\pi$...
3answers
2k views

### How do models of hypercomputation overcome the Halting Problem?

Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access ...
2answers
943 views

### Smallest possible universal combinator

I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal ...
1answer
632 views

### Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. -...
2answers
2k views

### Decidability of fractal maze

A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article: Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy ...
1answer
1k views

### Feasibility of Gödel machines

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
2answers
1k views

### What do we know about restricted versions of the halting problem

(UPDATE: a better formed question is posed here as the comments for the accepted answer below show that this question is not well-defined) The classical proof of the impossibility of the halting ...
1answer
741 views

### To what extent can the mathematics of Reals be applied to Computable Reals?

Is there a general theorem that would state, with proper sanitization, that most known results regarding the use of real numbers can actually be used when considering only computable reals? Or is ...