Questions tagged [mathematical-foundations]

Questions about the relation of (subfields of) computer science to the relevant mathematical foundations and their application.

Filter by
Sorted by
Tagged with
207
votes
29answers
49k views

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more ...
39
votes
3answers
6k views

What exactly is a logic?

An apology might be in due for asking another question about prerequisites, but I was confused about the starting points. I have come across various terms such as "Modal Logic", "Temporal logic", "...
35
votes
11answers
10k views

Why is data in computer science considered to be discrete?

I understand that "structure" of data is totally dependent on Boolean Algebra, but: Why is data considered to be a discrete mathematical entity rather than a continuous one? Related to this: ...
23
votes
2answers
7k views

Do any programming languages use general recursive functions as their basis?

This is a naïve and, therefore, possibly malformed question, so apologies in advance! My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming ...
15
votes
6answers
2k views

What precisely differentiates Computer Science from Mathematics in theoretical context?

I am a university level student of Computer Science having a great passion to study Mathematics. I have a firm belief that Computer Science or Theoretical Computer Science is a direct branch of ...
15
votes
6answers
6k views

What parts of linear algebra are used in computer science?

I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For ...
15
votes
1answer
538 views

Mathematics topics or fields that increase computer programming proficiency? [closed]

Generally computer programmers who are mathematicians or have mathematics background are very good in terms of algorithms and computer programming in general. What I am not saying: Mathematics is ...
14
votes
3answers
2k views

Shannon Entropy of 0.922, 3 Distinct Values

Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits ...
11
votes
2answers
432 views

Mathematical conjectures equivalent to the halting of a Turing machine

This question is about whether every mathematical theorem can be reduced to the question of whether a single Turing machine halts. In particular, I'm interested in conjectures that are currently ...
9
votes
2answers
3k views

What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
9
votes
1answer
827 views

Monad in Haskell programming vs. Monad in category theory

I have a question about concept of monad used in Haskell programming and category theory in math. Recall in Haskell a monad consists of following components: A type constructor that defines for each ...
7
votes
2answers
948 views

Minor Mistake in Computability, Complexity, and Languages?

In the book Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions): A partial function on a set $S$ is simply a function ...
7
votes
2answers
347 views

Can you operate on and draw conclusions on functions described asymptotically?

This question is homework based (not using actual problem though)! Say you have a function described as: $$f(n) \in O(2n^2) \, .$$ Can you then go on the treat this as: $$f(n) = 2n^2$$ and ...
7
votes
1answer
176 views

What is a list of “reasonable but undecidable” theorems?

There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples: Rice's Theorem: "all ...
6
votes
5answers
25k views

What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?

In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation: $\log^2(n) = ?$ $\log(n)^2 = ?$ $(\log n)^2 = (\log(n)) \...
5
votes
3answers
1k views

Is there a formalization of the computational model for quantum computers?

There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, ...
5
votes
2answers
3k views

Predicate Logic Notation: What does a “dot” mean?

What does a dot (.) mean in predicates? $\forall a \in A. \exists d \in D. H(a,d)$ Especially, how is the above different to $ \exists d \in D. \forall a \in A. H(a,d)$ I've never seen this used ...
5
votes
1answer
471 views

Mathematical proofs implemented purely by Lambda Calculus

I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task. Is there a simple example, lambda ...
5
votes
1answer
208 views

Analogy between Gödel's incompleteness proof and Richard's argument

If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula: $$n \in K \equiv \overline{\textit{Bew}}[R(...
5
votes
1answer
367 views

Set theory and computer science

It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science? Is it possible to define algorithms as a first step? More specifically, how to ...
4
votes
3answers
266 views

How Types avoids Russel's Paradox?

I gone through the Russel's paradox. From Wikipedia : According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is ...
4
votes
2answers
90 views

Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

Recently I was reading again this propositions as types paper by Philip Wadler: http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf It gives an impression, ...
4
votes
1answer
278 views

Are numbers types and what is “Number”?

I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me ...
4
votes
2answers
116 views

What are the implications of Homotopy Type Theory?

I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory. Can anyone tell me, in functional programming terms or ...
4
votes
1answer
293 views

How do you represent LISP as mathematical / logical model?

I asked this in stackoverflow, but the question probably fits here better. This question arose from the objection that LISP is regarded as a functional language with some simple principles, namely ...
4
votes
1answer
938 views

Why is the zero-th power of the empty set {ε}?

It has been asked before why $\emptyset^\star=\{\epsilon\}$. The answer boils down to $\emptyset^\star$ being defined as $$ L^\star = \bigcup_{i=0}^\infty L^i, $$ where a word in $L^i$ is the ...
4
votes
1answer
45 views

Reference Request: Overlaps between complexity theory and dynamical systems?

Per Wikipedia: In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space. Examples include the mathematical models that ...
4
votes
1answer
132 views

What is the name of this type of function composition?

If standard function composition is defined as: (define compose { (B → C) → (A → B) → (A → C) } F G -> (λ X (F (G X)))) What type of ...
4
votes
1answer
203 views

Mathematical equivalent of reduce()?

filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable. map() can be through of as a function mapping domain to codomain. ...
4
votes
1answer
136 views

Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...
4
votes
2answers
116 views

Usefulness of Differential Geometry

I recently came across these books: Differential Geometry and Lie Groups: A Computational Perspective Differential Geometry and Lie Groups: A Second Course Their subject matter really intrigues me, ...
3
votes
2answers
1k views

How does a computer interpret real numbers?

I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers. But I want to know how does ...
3
votes
2answers
405 views

Terminologies of “Process calculus” and “Process algebra” [duplicate]

In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me. My questions are: Are there formal, standard, and widely-accepted ...
3
votes
1answer
1k views

What mathematical background is enough to go through the entire Knuth's TAOCP?

I am an undergrad. I can do mathematics fine and am a lot more interested to explore. I turned towards TAOCP as it is highly mathematically oriented so as to excel at maths and programming at the same ...
3
votes
1answer
69 views

MAP estimation (for stationary iid gaussian environment)

This is my first post, and have been self studying Haykin's Neural Networks and Learning Machines book. I'm not sure if this is a typo or if I'm doing something wrong, but I've been stuck on a ...
3
votes
0answers
75 views

Examples of continuations in pure mathematics [closed]

I am not a computer scientist and have no knowledge of programming. However, I wondered continuations occur as natural and interesting mathematical structures, perhaps as algebraic or type theoretic ...
3
votes
0answers
146 views

Can cognitive architectures (CLARION, SOAR, ACT-R) be used for creative mathematical reasoning?

Can cognitive architectures (CLARION, SOAR, ACT-R, others) be used for creative mathematical reasoning? As far as I understand, then it is the best to encode formal mathematical knowledge in the ...
3
votes
0answers
98 views

Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
2
votes
4answers
173 views

How does maths consistency impacts on computer science?

Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem)...
2
votes
1answer
267 views

What is discrete mathematics and why am I learning about it?

I started computer science in university. And we started learning about Discrete and it's mathematics which is completely based on logic, which I understand. however, how is predicates, sets, proofs ...
2
votes
2answers
2k views

What is a mod b if a < b? [closed]

So when you are decrypting an encryption with modular arithmetic, I know the modulus operator (%) gives the remainder of a/b, but what if a is less than b? For example, 5%2 is 1, since the answer is ...
2
votes
1answer
47 views

A general picture of formal verification in software

I'm trying to piece together a general picture of the state of formal software verification, and I'm having a good bit of trouble. For context, I come from mostly a math background. I'm quite familiar ...
2
votes
1answer
98 views

What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
2
votes
1answer
41 views

Why is addition in GF(2^8) the same as XOR?

I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure ...
2
votes
1answer
63 views
2
votes
1answer
113 views

Equivalence relations with $\cap$, $\cup$ and $\circ$

I have the relations $E_1$ and $E_2$. A reflexive, symmetric and transitive property shows that two relations are equivalent to each other. I need to prove if this is true for the following a) $E_1 ∩...
2
votes
0answers
69 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
2
votes
0answers
58 views

Why, intuitively, is Lob's theorem true? [closed]

Lob's theorem states that: Let $\textbf{Prov}(n^A)$ be the arithmetic statement such that $PA\vdash$ $A$ iff $\textbf{Prov}(n^A)$, where $PA$ is peano arithmetic, and $n^A$ is the godel number of $A$....
2
votes
0answers
27 views

Soft Question: Looking for resources on computation over reals

As the title suggests, I want to take a look at resources (books, lectures or papers) that are available (free or paid) on computation over reals. Thanks in advance!
2
votes
0answers
48 views

physical significance of membership function greater than one

In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that ...