Skip to main content

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).

Filter by
Sorted by
Tagged with
215 votes
13 answers
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 ...
user107952's user avatar
  • 20.9k
68 votes
18 answers
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 ...
67 votes
3 answers
125k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
metdos's user avatar
  • 967
64 votes
2 answers
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;...
Casebash's user avatar
  • 9,307
63 votes
14 answers
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$ ...
dataphile's user avatar
  • 812
53 votes
3 answers
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, ...
bot47's user avatar
  • 652
53 votes
2 answers
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 (...
Jason's user avatar
  • 1,415
51 votes
5 answers
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, ...
user356363's user avatar
48 votes
3 answers
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 ...
nubela's user avatar
  • 849
45 votes
4 answers
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?
pragmacoder's user avatar
44 votes
3 answers
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 ...
HighAsAKiteOnMath's user avatar
44 votes
1 answer
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}$, ...
Harry Partridge's user avatar
43 votes
5 answers
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 ...
GMB's user avatar
  • 4,196
42 votes
11 answers
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 ...
user avatar
38 votes
3 answers
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 ...
Akhil Mathew's user avatar
  • 31.4k
37 votes
3 answers
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 ...
Chris Taylor's user avatar
  • 29.1k
37 votes
6 answers
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 ...
user avatar
36 votes
5 answers
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 ...
IamIC's user avatar
  • 671
33 votes
12 answers
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 ...
user63209's user avatar
  • 347
32 votes
6 answers
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 ...
Gadi A's user avatar
  • 19.3k
31 votes
8 answers
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 ...
John Hoffman's user avatar
  • 2,734
30 votes
5 answers
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 ...
Daniel Faust Montana's user avatar
30 votes
2 answers
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 ...
alh's user avatar
  • 471
29 votes
3 answers
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 ...
Simon Kuang's user avatar
  • 1,277
29 votes
3 answers
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/...
Shashwat's user avatar
  • 395
28 votes
7 answers
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 ...
kathelk's user avatar
  • 953
27 votes
4 answers
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: ...
puri's user avatar
  • 493
27 votes
3 answers
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 ...
pauliwago's user avatar
  • 635
26 votes
9 answers
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 ...
Hunali's user avatar
  • 451
26 votes
5 answers
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 ...
Abaco's user avatar
  • 475
25 votes
9 answers
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?
Razin's user avatar
  • 703
25 votes
4 answers
41k views

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

What does it mean to say a language is context-free?
user avatar
25 votes
4 answers
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 ...
AlanFoster's user avatar
25 votes
4 answers
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 ...
bshanks's user avatar
  • 523
25 votes
3 answers
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 ...
JWP_HTX's user avatar
  • 1,664
25 votes
1 answer
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 ...
r.e.s.'s user avatar
  • 14.8k
25 votes
1 answer
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 ...
Trevor's user avatar
  • 6,014
24 votes
5 answers
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 ...
Igglyboo's user avatar
  • 353
23 votes
3 answers
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 ...
awesom-o's user avatar
  • 251
23 votes
4 answers
52k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow S(...
CodeKingPlusPlus's user avatar
23 votes
2 answers
11k views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Strict-weak Ordering term. I have this requirement while sorting strings.
Pranit Kothari's user avatar
23 votes
2 answers
34k views

Computational complexity of computing the determinant

The formula for the determinant of an $n$ by $ n$ matrix given by expansion of minors involves $n!$ terms. As such, computing the determinant of a given matrix of with integer entries via expansion by ...
Jonah Sinick's user avatar
  • 1,032
23 votes
4 answers
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 ...
coffeemachine's user avatar
22 votes
5 answers
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 ...
Billie's user avatar
  • 3,469
22 votes
1 answer
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 ...
user13's user avatar
  • 223
22 votes
2 answers
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 ...
nilo de roock's user avatar
22 votes
1 answer
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 ...
nullUser's user avatar
  • 28k
21 votes
5 answers
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 ...
Amelio Vazquez-Reina's user avatar
21 votes
3 answers
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.
pepsi's user avatar
  • 489
21 votes
4 answers
1k views

What areas of math can be tackled by artificial intelligence?

Artificial intelligence is nearing, with image/speech recognition, chess/go engines etc. My question is, what areas of math that are interesting to mathematicians, is likely to be the first to be able ...
badmf's user avatar
  • 390

1
2 3 4 5
112