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
187
votes
29answers
47k 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 ...
35
votes
3answers
5k 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", "...
34
votes
11answers
9k 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: ...
22
votes
2answers
6k 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 ...
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 ...
14
votes
1answer
507 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 ...
13
votes
5answers
5k 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 ...
11
votes
2answers
335 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-...
7
votes
2answers
940 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
341 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 ...
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
2k 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
310 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
195 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(...
4
votes
3answers
231 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
1answer
270 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
1answer
244 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
509 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
43 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
253 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
1answer
94 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
113 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
132 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 ...
3
votes
5answers
7k 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)) \...
3
votes
2answers
335 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
2answers
78 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, ...
3
votes
1answer
793 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
66 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
79 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
2answers
979 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 ...
2
votes
1answer
81 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
2answers
1k 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
56 views
2
votes
1answer
106 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
52 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
67 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 ...
2
votes
0answers
122 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 ...
2
votes
0answers
34 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 ...
1
vote
4answers
2k views

What is the role of mathematics in programming?

I am almost totally uneducated in programming and computer science in general, though I am really fascinated by these topics. I read that mathematics is important in programming and that nowadays many ...
1
vote
3answers
119 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)...
1
vote
2answers
83 views

What are the other language models of computation similar to lambda calculus?

I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals ...
1
vote
2answers
191 views

Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
1
vote
4answers
98 views

What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying ...
1
vote
1answer
223 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 ...
1
vote
1answer
51 views

What Does The Notation of Union Over K represent?

I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows: $$P= \bigcup_{k}TIME(n^k)$$ I have not seen the Union over k notation ...
1
vote
2answers
79 views

“Mathematical Physics”'s equivalent for Computer Science

Mathematical Physics is a well defined scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics. Is ...
1
vote
1answer
63 views

Pre-requisite knowledge before diving into algorithms

I'm having some difficulty trying to follow what the authors of some of the more highly recommended books on algorithms. I ran into the same problem when trying out some online courses. My goal is to ...