Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [mathematical-foundations]

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

1
vote
2answers
63 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 ...
0
votes
0answers
36 views

Mathematical resource material accompanying TAPL

I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types. Prior to this chapter I found the book challenging but ...
1
vote
1answer
20 views

How can we compute how many processes should be in memory at a time to make CPU utilization max?

From the given formula, we can compute the CPU utilization: CPU Utilization = 1 - P^n Where p is the probability of I/O and n is the total number of processes. E.g, If we were to find CPU ...
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 ...
0
votes
0answers
11 views

Is there any formula to find the exact number of optimal codes for a distribution of probability, where 2 signals or more have the same probability?

for example, An alphabet whose 4 letters appear with these probabilities: p1 = p2 = 0.3, p4 = p3 = 0.2. Is there a way to compute the number of optimal codes?
1
vote
1answer
12 views

How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
0
votes
1answer
19 views

What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy $$ I(A_i) = I(A) + \log (4)?$$
-3
votes
1answer
278 views

Is Alan Turing's proof of the incomputability of halting problem invalid?

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...
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 ...
2
votes
0answers
48 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$....
1
vote
1answer
30 views

Syntax of recurrence formula not clear

I have this task for Analysis of Algorithms module in university $$ \begin{align*} W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\ G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\...
0
votes
1answer
39 views

How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically: var foo = { a: 10, b: 'bar', c: true } You could say that it was a function ...
34
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", "...
1
vote
0answers
25 views

Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule. $$ \lim_{n\...
0
votes
0answers
95 views

Understanding GAN optimization equation

I am having trouble understanding the below optimization equation for Generative Adversarial Nets: $\underset{G}{\mathrm{min}} \: \underset{D}{\mathrm{max}} \: V(D,G) = \mathbb{E}_{x \sim p_{data}(x)}...
5
votes
1answer
192 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(...
1
vote
0answers
52 views

Should I go for computer science or maths? [closed]

I am in 11th grade. The only subject which I love the most is solving alegebraic equations and questions related to it. I enjoy doing trigonometry but hate the part of proving theorems. I opted ...
-1
votes
2answers
73 views

Compute growth of function [closed]

Suppose that $p>0$ and $n>0$ is a natural number. How do I prove that $$ \sum_{k=1}^n k^p = 1^p + 2^p + \dots +n^p \sim \frac{1}{p+1}n^{p+1}=\Theta(n^{p+1})$$ for $n \rightarrow \infty$?
4
votes
1answer
213 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 ...
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, ...
179
votes
29answers
45k 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 ...
2
votes
0answers
23 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!
1
vote
1answer
42 views

How to understand the probablistic analysis of skiplist?

I've been studying the skiplist analysis from the open data structures book here: Open Data Structures I've understood the first 3 lemma's, (after looking at how they use indicator variables in the ...
1
vote
3answers
107 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)...
4
votes
1answer
203 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 ...
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, ...
4
votes
1answer
100 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. ...
14
votes
1answer
486 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 ...
0
votes
2answers
197 views

Tight bound on the number of divisors of n

The inner loop of this pseudocode runs only for the divisors of n for i=1 to n: if(n%i==0): for j=1 to n: Do something in constant time If I ...
4
votes
1answer
214 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 ...
2
votes
0answers
62 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 ...
0
votes
0answers
206 views

magnetic Disk Calculation

A magnetic disk has 1000 cylinders, 10 tracks per cylinder, 128 sectors per track, ...
-1
votes
2answers
123 views

how long will it take to execute a ten-stage pipeline

Suppose you design a computer with a ten-stage Pipeline to execute one instruction, with each stage taking 5nsec A)how long ...
2
votes
0answers
109 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 ...
5
votes
1answer
87 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 ...
34
votes
11answers
8k 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: ...
1
vote
0answers
150 views

Trouble understanding Break-Even Point for upgrade

Suppose the daytime processing load consists of 60% CPU activity and 40% disk activity. Your customers are complaining that the system is slow. After doing some research, you have learned that you can ...
0
votes
1answer
133 views

Proof by mathematical induction

Before we start, my textbook declares lgn as base two. I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even ...
1
vote
1answer
57 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 ...
0
votes
0answers
74 views

What is the underlying structure of problems?

We all the time write and talk about mathematical problems in plain English. For example, we define "the traveling salesman problem". But what is the actual, underlying structure of a "mathematical ...
11
votes
2answers
309 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 ...
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 ...
0
votes
1answer
273 views

“Regular languages over a common alphabet are closed under union.”

I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses. Suppose we have two regular languages, $L_1$ and $L_2$, with a common ...
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 ...
7
votes
2answers
933 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 ...
1
vote
2answers
161 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 ...
2
votes
0answers
33 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 ...
4
votes
1answer
268 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
3answers
217 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 ...