All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

142
votes
14answers
31k views

Is computer science a branch of mathematics?

I have been wondering, is computer science a branch of mathematics? No one has ever adequately described it to me. It all seems very math-like to me. My second question is, are there any books about ...
42
votes
2answers
1k views

Computation with a memory wiped computer

Here is another result from Scott Aaronson's blog: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging ...
33
votes
3answers
1k views

Is the 24 game NP-complete?

The $24$ game is as follows. Four numbers are drawn; the player's objective is to make $24$ from the four numbers using the four basic arithmetic operations (in any order) and parentheses however one ...
31
votes
6answers
3k views

Simple “real life” NP-hard problems?

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple ...
28
votes
4answers
987 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
27
votes
6answers
3k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
25
votes
5answers
2k views

Can mathematics get from other sciences what it got from physics?

Throughout history, physics has been an unparalleled source of '' inspiration'' for discovering/inventing mathematical ideas, which is due to its ability to describe the physical world. But can this ...
24
votes
1answer
635 views

Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
23
votes
12answers
3k views

How is the set of all programs countable?

I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish ...
22
votes
5answers
4k views

Is a brute force method considered a proof?

Say we have some finite set, and some theory about a set, say "All elements of the finite set $X$ satisfy condition $Y$". If we let a computer check every single member of $X$ and conclude that the ...
20
votes
1answer
506 views

Would relational calculus be Turing-complete if it allowed unsafe queries?

My understanding about Codd's concept of "safe queries" was created to ensure that a query would always terminate. One key ability of a Turing machine is that it can work on infinite calculations ...
19
votes
3answers
1k views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
19
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
19
votes
1answer
390 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
17
votes
5answers
929 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
17
votes
2answers
14k views

What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics? Is something like "Introduction to discrete Mathematics" enough?
17
votes
4answers
4k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
16
votes
3answers
4k views

How to Prove a Programming Language is Turing Complete?

I had some thoughts about how to prove the turing completeness of a programming language. I came to the conclusion, that if you could write a program that is able to parse a turing machine program, ...
16
votes
2answers
1k views

What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
15
votes
3answers
5k views

What are NP-complete problems and why are they so important?

I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?
15
votes
1answer
338 views

How to prove there are no more positive integers that are products of 2 and 3 consecutive numbers?

$6$ and $210$ share the property that both are the products of both two and three consecutive numbers. $6$ is $2\times3$ and $1\times2\times3$ and $210$ is $14\times15$ and $5\times6\times7$. It was ...
15
votes
6answers
786 views

What are the theorems of mathematics proved by a computer so far?

By theorems, I mean the ones you can find in an undergraduate course of mathematics, not the ones you can find in a textbook of automated proofs. I mean by "proved by a computer" that an existing ...
15
votes
4answers
3k views

Ackermann Function primitive recursive

I am reading the wikipedia page on ackermann's function, http://en.wikipedia.org/wiki/Ackermann_function And I am having trouble understanding WHY ackermann's function is an example of a function ...
15
votes
3answers
1k views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
14
votes
6answers
3k views

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be ...
14
votes
6answers
2k views

What math should a computer scientist take in college?

I'm a computer science major and like many of us we have to take two additional sciences. These two additional science courses are in addition to three semesters of calculus,two semesters of physics, ...
13
votes
4answers
9k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
13
votes
1answer
14k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
13
votes
3answers
369 views

Etymology of “topological sorting”

This may be a dumb question, but what's "topological" about topological sorting in graph theory? I thought topology was related to geometry and deformations.
13
votes
3answers
567 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what ...
12
votes
3answers
799 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
12
votes
4answers
211 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
12
votes
3answers
172 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
11
votes
4answers
805 views

What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will ...
11
votes
3answers
288 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
11
votes
5answers
1k views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
11
votes
4answers
748 views

why is $2.2250738585072014\text{e}{-308}$ not a number? [closed]

In programming the min value of a float is: $$2.2250738585072014\text{e}{-308}$$ but when I type this into a calculator, it says Not a Number. what I am wondering ...
11
votes
4answers
698 views

An analog of the Myhill-Nerode Theorem for context-free languages?

The Myhill-Nerode Theorem gives an exact characterization of the regular languages. Given any language, one can check whether it meets the criteria of the Myhill-Nerode theorem to decide whether or ...
11
votes
2answers
2k views

Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
11
votes
1answer
506 views

Assuming $P \neq NP$, do we know whether there are problems which are in $NP$, not in $P$ and are not $NP$ complete?

Here's a question. Have there been any theoretical results showing that if $P \neq NP$, there must exist some problems in $NP$ which are not $NP$-complete and which are not in $P$ either? Just ...
11
votes
0answers
381 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
11
votes
0answers
193 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
10
votes
3answers
1k views

Proving the Riemann Hypothesis without revealing anything other than you proved it

Consider the following assertion from Scott Aaronson's blog: Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other ...
10
votes
4answers
556 views

If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?

The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if This is definitely known to be true, This is definitely ...
10
votes
3answers
628 views

Solving P vs NP with computer

Is it possible to build a computer program that would (eventually) bring a solution to the P vs. NP question?
10
votes
3answers
265 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
10
votes
1answer
743 views

Fast inverse square root trick

I found what appears to be an intriguing method for calculating $$\frac{1}{\sqrt x}$$ extremely fast on this website, with more explanation here. However, the computer-science lingo and ...
10
votes
2answers
2k views

An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate ...
10
votes
1answer
630 views

Incremental calculation of inverse of a matrix

Does there exist a fast way to calculate the inverse of an $N \times N$ matrix, if we know the inverse of the $(N-1) \times (N-1)$ sub-matrix? For example, if $A$ is a $1000 \times 1000$ invertible ...