# Questions tagged [computer-science]

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 questions from scientific computing, use (computational-mathematics).

5,565 questions
Filter by
Sorted by
Tagged with
66k 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 ...
• 20.9k
10k views

### Unsolved Problems due to Lack of Computational Power

I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are ...
125k views

### Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
• 967
4k 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 program;...
• 9,307
22k views

### Is there a math expression equivalent to the conditional ternary operator?

Is there a math equivalent of the ternary conditional operator as used in programming? a = b + (c > 0 ? 1 : 2) The above means that if $c$ is greater than $0$ ...
• 812
24k 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, ...
• 652
2k 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 (...
• 1,415
9k views

### Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
• 529
131k views

### What is the $3$-SAT problem? [closed]

In the hopes of improving my knowledge on the question, could someone outline the inputs and outputs for the 3-SAT problem? It would also be helpful if you could express how this problem differs in ...
• 849
43k 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?
• 553
4k views

### Under the Curry-Howard correspondence or loosely "proofs-as-programs", do we also have "programs-as-proofs" and what would some arb. program prove?

Curry-Howard Correspondence Now, pick any 5-30 line algorithm in some programming language of choice. What is the program proving? Or, do we not also have "programs-as-proofs"? Take the ...
• 21.6k
825 views

### A strange occurrence in the decimal digits of $\pi$?

I was messing around with various ways to calculate $\pi$ with my computer, and I noticed something a bit strange. I was using $\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+... = \frac{\pi}{4}$, ...
4k 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 ...
• 4,196
24k views

### what are the different applications of group theory in CS? [closed]

What are some applications of abstract algebra in computer science an undergraduate could begin exploring after a first course? Gallian's text goes into Hamming distance, coding theory, etc., I ...
2k 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.4k
9k 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 ...
• 29.1k
8k views

### How to start with automated theorem proving?

I'm interested in this question, but I'm not going to list my knowledge/demands but rather gear it to more general purpose; so the first thing concerns the prerequisites, i.e. How much theoretical ...
59k views

### Representing IF ... THEN ... ELSE ... in math notation

How do I correctly represent the following pseudocode in math notation? EDIT1: Formula expanded. EDIT2: Clarification. (a,b) represents a line segment on a 1D line. a <= b for each segment. The ...
• 671
16k 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 ...
• 347
8k 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 ...
• 19.3k
8k 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 ...
• 2,734
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 ...
33k views

### Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
• 471
5k 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 ...
• 1,277
32k views

### Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}$ However https://en.wikipedia.org/...
• 395
5k views

### How do you correctly reason that this directed graph is acyclic?

How can you correctly reason that this directed graph is acyclic? I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is equal ...
• 953
11k 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: ...
• 493
16k 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 ...
• 635
10k views

### Is Calculus necessary for computer science student? [closed]

I'm a freshman in university and I'm studying Computer science and engineering. This will be my second year of studying. We don't have Calculus as a mandatory class but I can take it from elective ...
• 451
65k views

### Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
• 475
25k views

### Is it possible to generate truly random numbers using a computer? [closed]

I know that there are many algorithms to generate pseudorandom numbers but is it possible to generate truly random numbers using a computer program?
• 703
41k views

### What does it mean to say a language is context-free?

What does it mean to say a language is context-free?
13k 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 ...
• 353
5k views

### Is a "network topology'" a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
• 523
3k views

### What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
• 1,664
762 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 ...
• 14.8k
460 views

### Golden Ratio appears in this Rule 30 variation?

The cellular automaton Rule 30 is most commonly explored starting with a single 1 cell against a background of infinitely many 0 ...
• 6,014
6k 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 ...
• 353
3k 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 ...
• 251
52k views

• 1,032
7k 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 ...
94k views

### How does linear algebra help with computer science?

I'm a Computer Science student. I've just completed a linear algebra course. I got 75 points out of 100 points on the final exam. I know linear algebra well. As a programmer, I'm having a difficult ...
• 3,469
4k views

### Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
• 223
4k views

### Which resources are available to self-study GAP?

Background: This year I'll do another Group Theory course ( Open University M336 ). In the past I have used Mathematica's AbstractAlgebra package but (although visually appealing ) this is no longer ...
• 2,779
514 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 ...
• 28k
5k 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 ...
2k 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.
• 489