100
The Matrix Mortality Problem for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?
(The 3x3 case is known to be undecidable. The 1x1 case, of course, is decidable.)
75
Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread. Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows ...
62
UPDATE: The problem I mentioned here is now known to be undecidable! http://arxiv.org/abs/1605.05274 Moreover, the paper was inspired by reading this very answer. :)
Programmers in your math-major audience may be surprised to learn that the question "is this type implicitly convertible to that type?" is not known to be decidable in any of Java 5, C# 4 and ...
50
Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"
47
System $F$ is quite expressive. As proved by Girard here, the functions of type $\mathbb{N}\rightarrow\mathbb{N}$ (where $\mathbb{N}$ is defined to be $\forall X.\ X\rightarrow (X\rightarrow X)\rightarrow X$) are exactly the definable functions ($\mathbb{N}\rightarrow\mathbb{N}$) in second order Heyting Arithmetic $\mathrm{HA}_2$. Note that this is the same ...
45
This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace $\mathbb{N}$ with $\mathtt{string}$ throughout below.
Let $\langle m, n\rangle$ ...
36
I think the issue is quite simple.
All interactive formalisms can be simulated by Turing machines.
TMs are inconvenient languages for research on interactive computation (in most cases) because the interesting issues get drowned out in
the noise of encodings.
Everybody working on the mathematisation of interaction knows this.
Let me explain this in more ...
32
It is easy to get confused about what it means to "represent" or "implement" a real number. In fact, we are witnessing a discussion in the comments where the representation is contentious. So let me address this first.
How do we know that an implementation is correct?
The theory which explains how to represent things in a computer is realizability. The ...
31
The problem of given a linear recurrence along with its initial values, does it take the value 0?
Two reference:
http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/
http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf
27
In terms of number computability (i.e., computing functions from $\mathbb{N} \to \mathbb{N}$), all known models of computation are equivalent.
However, it's still true that Turing machines are fairly painful for modelling properties like interactivity. The reason is a little bit subtle, and has to do with the kinds of questions that we want to ask about ...
25
A simple problem whose decidability is unknown is the following (I think it is still open):
Infinite chess:
Input: A finite list of chess pieces and their starting positions on a $Z \times Z$ chessboard;
Question: Can White force mate?
If we add the constraint that White must mate in $n$ moves ($n$ is part of the input), then it becomes decidable:
see Dan ...
24
As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment)...
23
In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):
input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0
It is clear that it is undecidable in general whether $p_T$ is linear-time or ...
23
Yes, it is. Here's how you do it:
You can compile basically any program you like to circuits. See for instance the work of Dan Ghica and his collaborators on the Geometry of Synthesis, which shows how to compile programs into circuits.
Dan R. Ghica. Geometry of Synthesis: A structured approach to VLSI design
Dan R. Ghica, Alex Smith. Geometry of Synthesis ...
22
I can think of a few possible answers coming from linear logic.
The simplest one is the affine lambda-calculus: consider only lambda-terms in which every variable appears at most once. This condition is preserved by reduction and it is immediate to see that the size of affine terms strictly decreases with each reduction step. Therefore, the untyped affine ...
21
No, it's not possible. Consider the following two inhabitants of the type $(A \to B) \to (A \to B)$.
$$
\begin{array}{l}
M = \lambda f.\;f \\
N = \lambda f.\;\lambda a.\; f\;a
\end{array}
$$
These are distinct $\beta$-normal forms, but cannot be distinguished by a lambda-term, since $N$ is an $\eta$-expansion of $M$, and $\eta$-expansion preserves ...
21
Any language which is not Turing complete can not write an interpreter for it self.
This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore your input and halt immediately". This programming language is not Turing complete but every program is an interpreter for the language.
21
You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it is not intuitive, or that it does not sufficiently explain what is going on. In contrast, he found Turing's analysis of computability and the ensuing notion of ...
20
Collatz Problem is simple-to-describe problem whose decidability is open. It involves a simple recurrence of elementary arithmetic operations.
$f(n)=\mathsf{\{}$ $n/2$ for even integer, $3n+1$ for odd integer
The problem is deciding whether iterating this function always return to 1 for a given positive integer $n_0$.
Interestingly, a generalization ...
20
It is unknown whether or not
it is decidable to determine if a given shape can tile the plane,
even for polyomino tiles.
(Image from Wikipedia.)
19
The question displays a fundamental misunderstanding about the nature of what can be done with computers. To correct this misunderstanding, I suggest getting a copy of the computer algebra software Maple and trying the commands
expand((1+sqrt(2))^5);
sin(Pi/4);
If computers can only deal with rational numbers, how do you explain the results?
18
Check out
the Computability and Complexity in Analysis network. Quote:
The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of ...
18
First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".
Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time.
Third, the result of Adamczewski et al. is only about finite automata and deterministic ...
17
Not even no.
Algorithms are not the right class of objects to be Turing-complete; asking whether an algorithm is Turing-complete is like asking whether a cat is prime. Objects that can be Turing-complete are usually called models of computation.
17
Yes, but you have to consider typed combinators. That is, you need to give $S$ and $K$
the following type schemas:
$$
\begin{array}{lcl}
K & : & A \to B \to A \\
S & : & (A \to B \to C) \to (A \to B) \to (A \to C)
\end{array}
$$
where $A, B$, and $C$ are meta-variables which can be instantiated to any concrete type at each use.
Then, you ...
17
Post's Correspondence problem with a fixed number of tiles of between 3 and 6.
While it is not really simple to describe, it does have a very "playful" description, and I find it suitable for intuition-level talks.
17
The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory.
Query containment takes as input two queries $Q_1$ and $Q_2$ and asks whether $Q_1$ applied to any database $I$ yields at least as many answers as $Q_2$ when applied to the same database $I$.
In conjunctive ...
17
You're assuming that numbers can only be represented as fractions (either literally, by having a datatype storing integer numerator and denominator, or implicitly by using some kind of floating point representation) but this isn't true. For example, you can easily represent rational complex numbers by storing the rational real and imaginary parts. Similarly,...
17
The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was answered negatively by Turing in his famous 1936 paper "On Computable Numbers, with an application to the Entscheidungsproblem". The word literally means ...
16
It depends on the total functional language.
This answer sounds like a cop-out, but nothing more specific can be said. After all, consider whatever important decidable program that you're interested in. Write a program in your favorite Turing-complete language to solve it. Since the problem is decidable, your program will halt on all inputs.
(Arguably, a ...
Only top voted, non community-wiki answers of a minimum length are eligible
