Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

142
votes
11answers
48k views

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
130
votes
3answers
14k views

How can it be decidable whether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...
72
votes
5answers
12k views

Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being ...
58
votes
10answers
9k views

Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
53
votes
6answers
11k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
43
votes
2answers
13k views

How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
42
votes
9answers
14k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
41
votes
3answers
8k views

Why can humans solve certain “undecidable” problems?

High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where ...
40
votes
5answers
9k views

Iteration can replace Recursion?

I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...
40
votes
4answers
11k views

What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
38
votes
9answers
8k views

Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
37
votes
4answers
7k views

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
37
votes
1answer
26k views

Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
36
votes
2answers
7k views

Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
34
votes
2answers
6k views

What can Idris not do by giving up Turing completeness?

I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific ...
33
votes
5answers
6k views

Can Quantum Computing solve Problems not even a Turing Machine can solve? [duplicate]

In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
32
votes
9answers
3k views

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
31
votes
5answers
7k views

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
30
votes
2answers
4k views

NP-Hard problems that are not in NP but decidable

I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable? For example, the halting problem is NP-Hard, not NP-Complete, but is ...
30
votes
2answers
4k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
29
votes
7answers
5k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
29
votes
1answer
2k views

Does there exist a Turing complete typed lambda calculus?

Do there exist any Turing complete typed lambda calculi? If so, what are a few examples?
29
votes
2answers
4k views

Why are the total functions not enumerable?

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i....
29
votes
1answer
2k views

Rice's theorem for non-semantic properties

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always ...
28
votes
2answers
4k views

Church-Turing Thesis and computational power of neural networks

The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine. The paper "Analog computation via neural networks" (Siegelmannn and Sontag, ...
28
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
28
votes
2answers
5k views

Why are there more non-computable functions than computable ones?

I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-...
27
votes
7answers
6k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
27
votes
6answers
7k views

Are there programs that can 'translate' source code between any two languages?

Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)? If there are, how do they work (techniques used, ...
27
votes
4answers
4k views

Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as: FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. ...
27
votes
2answers
746 views

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
26
votes
7answers
7k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
26
votes
2answers
6k views

What is the difference between quantum TM and nondetermistic TM?

I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
24
votes
4answers
11k views

Proof of the undecidability of the Halting Problem

I'm having trouble understanding the proof of the undecidability of the Halting Problem. If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ ...
24
votes
5answers
9k views

Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
23
votes
4answers
11k views

Is busy beaver the fastest growing function known to man?

I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver? We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn ...
22
votes
6answers
29k views

Recursive and recursively enumerable language definition for a layman

I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are . Can some one please tell me what they are in simple words?
22
votes
4answers
4k views

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
22
votes
6answers
3k views

Algorithm to solve Turing's “Halting problem‍​”

"Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist" Can I find a general algorithm to solve the halting problem for ...
21
votes
5answers
5k views

Why are functional languages Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
21
votes
2answers
916 views

Is there a “natural” undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
21
votes
4answers
3k views

Does a never-halting machine always loop?

A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt. Can someone ...
21
votes
3answers
1k views

Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (...
20
votes
5answers
4k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
19
votes
1answer
945 views

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
19
votes
5answers
850 views

What exactly is computation?

I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of ...
19
votes
1answer
288 views

Equivalence of Kolmogorov-Complexity definitions

There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity ...
19
votes
1answer
444 views

Ratio of decidable problems

Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...
19
votes
1answer
287 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
18
votes
6answers
5k views

Is every NP-hard problem computable?

Is it required that a NP-hard problem must be computable? I don't think so, but I am not sure.