101
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.)
64
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 ...
52
Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"
50
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$ ...
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
28
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 ...
25
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)...
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 ...
22
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 ...
21
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 ...
answered Sep 6 '13 at 8:41
Mohammad Al-Turkistany
20.3k4 gold badges56 silver badges143 bronze badges
21
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.)
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
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
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 ...
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
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,...
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
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
Yes.
First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood ...
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
The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 and Defintion 11.2.10 of the HoTT book.)
The following theorem is valid in any topos (a model of higher-order intuitionistic logic):
Theorem: There is a ...
16
Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic.
A general purpose programming language has general recursion. This allows it to populate every type, but we would not conclude from this fact that programming is a ...
16
This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result in the usual computable numbers, or you're trying to surpass that.
First we have Turing's definition of computable real number, and it is the one others have ...
15
I'm not sure whether this is what you're looking, but the phase transition in random SAT is an example. Let $\rho$ be the ratio of number of clauses to number of variables. Then a random SAT instance with parameter $\rho$ is very likely to be satisfiable if $\rho$ is less than a fixed constant (near 4.2) and is very likely to be unsatisfiable if $\rho$ is a ...
15
Probably you already got these in your bag :-)
Two way one counter machine over unary alphabet (Minsky61).
Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1].
Quantum one counter automata [2].
With binary alphabets, the emptiness remains undecidable for:
One way machines with one ...
15
I can see why the question is being downvoted, but this is too good not to post. Suppose you have a coin with bias $p\in[0,1]$, which might be rational or irrational. Question: using only finite memory, can you devise a test for determining whether $p$ is rational or not from a sequence of independent $p$-coin flips? Incredibly, as Hirschler and Cover showed ...
15
Hmm, turns out there's actually an matching upper bound that isn't too hard:
To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of machines of description length at most $n$ which halt. This number is not more than $2^{n}$, so it can be represented with about $n$ bits. Then we can start all such ...
14
Here are two results cited in Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators":
Theorem 3: The class of mortal Turing machines is exactly the class of the constant running time Turing machines.
$ConstT = \{ M \mid \exists s $ s.t. for all initial configurations $C$, $M$ halts in no more ...
14
No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete.
When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle ...
Only top voted, non community-wiki answers of a minimum length are eligible
