Skip to main content

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
96 votes
9 answers
20k 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 ...
user avatar
46 votes
4 answers
4k 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 ...
Mohammad Alaggan's user avatar
33 votes
5 answers
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 ...
Artem Kaznatcheev's user avatar
104 votes
15 answers
11k views

A simple decision 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 ...
Lev Reyzin's user avatar
  • 12k
44 votes
7 answers
6k 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 ...
Joseph O'Rourke's user avatar
40 votes
7 answers
7k 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. ...
zenna's user avatar
  • 835
62 votes
3 answers
9k 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 ...
Blaisorblade's user avatar
  • 2,069
40 votes
7 answers
9k 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 ...
AlexC's user avatar
  • 503
21 votes
2 answers
4k views

A total language that only a Turing complete language can interpret

Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind ...
Jake's user avatar
  • 1,213
20 votes
2 answers
6k views

What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ...
vzn's user avatar
  • 11.1k
19 votes
5 answers
3k 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 ...
Mike B.'s user avatar
  • 749
5 votes
1 answer
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 ...
jamaicanworm's user avatar
54 votes
5 answers
29k 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?
hawkeye's user avatar
  • 2,581
46 votes
5 answers
3k 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-...
Evan's user avatar
  • 563
32 votes
4 answers
4k 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 ...
Joey Adams's user avatar
25 votes
1 answer
2k 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?)
Steve's user avatar
  • 251
23 votes
6 answers
5k 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 <...
dbarbosa's user avatar
  • 365
15 votes
3 answers
975 views

Can it be determined if language L lies in NP?

Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
txwikinger's user avatar
14 votes
3 answers
2k views

Is there a complexity theory analogue of Rice's theorem in computability theory?

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ...
Mohammad Al-Turkistany's user avatar
49 votes
3 answers
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 ...
Timothy Chow's user avatar
  • 7,560
43 votes
2 answers
3k 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 ...
Manu's user avatar
  • 7,669
40 votes
7 answers
7k 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 ...
Alex ten Brink's user avatar
32 votes
1 answer
1k 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, ...
math4tots's user avatar
  • 423
30 votes
1 answer
3k 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 ...
Weier's user avatar
  • 413
30 votes
6 answers
3k 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:...
Gilles 'SO- stop being evil''s user avatar
27 votes
6 answers
3k 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 ...
user avatar
23 votes
2 answers
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 ...
Hooked's user avatar
  • 365
21 votes
1 answer
878 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?
NietzscheanAI's user avatar
19 votes
3 answers
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 ...
Velvet Ghost's user avatar
19 votes
2 answers
2k 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 ...
Mohammad Alaggan's user avatar
19 votes
3 answers
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'...
Emmanuel M. Smith's user avatar
14 votes
3 answers
1k views

Proof of undecidability not by reduction from the halting problem

The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc. It is ...
David Monniaux's user avatar
14 votes
3 answers
1k views

What are natural examples of non-relativizable proofs?

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
Sai's user avatar
  • 241
9 votes
3 answers
3k views

Are there languages that are not in RE nor CO-RE?

I am familiar with the theorem which states that some languages are not in the RE (Recursively Enumerable) class of languages, but that can mean either that they are all in CO-RE (or rather, the part ...
EpsilonVector's user avatar
9 votes
2 answers
440 views

Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
Sadeq Dousti's user avatar
  • 16.5k
4 votes
3 answers
595 views

Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ......
user avatar
2 votes
2 answers
2k views

Is there an alternative proof of the TM Halting Problem other than the "standard" one? [closed]

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a ...
johne's user avatar
  • 227
36 votes
4 answers
1k 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, ...
ripper234's user avatar
  • 883
33 votes
2 answers
4k 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 ...
Mike H-R's user avatar
  • 383
28 votes
4 answers
6k 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 ...
Noldorin's user avatar
  • 867
26 votes
4 answers
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": ...
didest's user avatar
  • 1,551
25 votes
3 answers
15k 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 ...
Ulkmun's user avatar
  • 379
23 votes
3 answers
950 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 ...
Tyson Williams's user avatar
21 votes
5 answers
5k 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 ...
mojuba's user avatar
  • 319
21 votes
3 answers
2k 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 ...
user76284's user avatar
  • 672
20 votes
2 answers
1k 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 ...
Marcos Villagra's user avatar
19 votes
1 answer
1k 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. -...
Joshua Grochow's user avatar
17 votes
2 answers
3k 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 ...
Nick Alger's user avatar
17 votes
2 answers
2k views

Explicit mu-recursive expression for Ackerman function

Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers ...
Artem Pelenitsyn's user avatar
14 votes
1 answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

Two papers I would include are: D. Kozen, "Indexing of subrecursive classes", STOC, 1978. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.