# Questions tagged [mathematical-foundations]

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

124 questions
Filter by
Sorted by
Tagged with
38 views

### Is the root function computationally equivalent to function application?

If a function type is representable by exponentiation, does it follow that function application is represented by the right inverse, roots? It would seem that roots consume a function's input to ...
5k views

### Could Gödel’s incompleteness theorem be circumvented with a quine?

As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness. Mainly because that proof would be part of mathematics too,...
• 225
37 views

### Reading list for mathematics and formal logic with missing truth values?

I would like a reading list of math and formal logic books which give a principled discussion of missing values. Textbooks on mathematics and formal logic - propositional and first-order and higher-...
• 163
41 views

### How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
• 168
1 vote
23 views

1 vote
31 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
289 views

### Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ? I don’t have specific topic that I care more about ...
32 views

### How to specify mutated types mathematically?

Say I have an object which I pass to a method, and the method returns that same object, just mutated. So it goes like this: ...
• 1,871
31 views

### Function notation/mapping for this type of functions?

In short, what is the proper function notation/mapping for this type of functions? From Wikipedia regarding maps: In the communities surrounding programming languages that treat functions as first-...
• 119
40 views

### Prove that for any finite k = 1, 2, 3 … PCPk is decidable

Let PCPk be a version of PCP where we can use at most k copies of each domino to create correspondences. Prove that for any finite k = 1, 2, 3 … PCPk is decidable. I know this kind of PCP is called ...
1 vote
20 views

### Proof the number of expected node in a binary using mathematical induction

The following algorithm constructs a binary tree. ...
• 73
28 views

### Papers on depth separations in neural networks

I am new to the domain of Machine learning. I have been asked to present a paper related to the mathematics behind the depth separations in Neural Networks (by Itay Safran, Ronen Eldan and Ohad Shamir)...
36 views

### A set that is not polynomial time enumerable

For a set $I\subseteq \Bbb N$, defined $s_{I}(n)=\min\{i\in I\mid i>n\}$. The set $I$ is called polynomial-time-enumerable if $s_I(n)$ is computable in $\mathsf{poly}(n)$ time. Most of the sets I ...
• 101
1 vote
46 views

### "The Annotated Turing" on listing all binary numbers between 0 and 1

In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote: These are binary numbers between 0 and 1, and (judging from the way we created these numbers) all ...
• 111
1k views

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 ...
• 215
286 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 ...
50 views

### Which topics of mathematics should I need to learn to be a good app developer?

I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
191 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 ...
1 vote
55 views

### A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
• 141
52 views

### Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

Problem Statement: Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many ...
1 vote
430 views

### What is the difference between a fraction and a float?

I understand any fraction to be a quotient of integers which isn't 0, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is ...
• 13
1 vote
66 views

### How was the σ function chosen to extend the perceptron?

I am just reading about perceptrons in more depth, and now onto Sigmoid Neurons. Some quotes: A small change in the weights or bias of any single perceptron in the network can sometimes cause the ...
• 1,871
299 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, ...
• 125
44 views

### How do you convert bits into a different alphabet?

I have forgotten how to do this. How do I figure out what the requirements are for a 128-bit string using a certain alphabet? That is to say, I want to generate a UUID (128-bit) value, using only the ...
• 1,871
1 vote
127 views

### Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement

While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim: Sets are as fundamental to computer science as they are to mathematics. Whereas ...
• 1,034
388 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 ...
277 views

### How is expected value in entropy derived?

I was self learning about entropy and came across this equation. $$H = - \sum p(x) \log p(x)$$ The equation for entropy in expected value,  H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
• 131
1 vote
142 views

### Prove little o with just the definition

I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation. Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am ...
• 11
57 views

### Where does the base come from in a subsequence count?

If sequence X has m symbols, then X has 2m possible subsequences. Where does the base (<...
• 320
60 views

### Big O Tires Question? [duplicate]

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.) What's the runtime of this code? ...
• 141
250 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 ...
• 216
36 views

### I don't understand formula meaning of computer vision Paper

I am master degree student at Computer Science Department. I started master degree at this year. Now I'm reading two papers about computer vision. Actually before time I didn't have experience about ...
1 vote
98 views

### How does the forget layer of an LSTM work?

Can someone explain the mathematical intuition behind the forget layer of an LSTM? So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), ...
52 views

### How are Complex Numbers and Complex Analysis used in CS? [closed]

The world is 3D and data of it is usually (as far as I know) represented and processed with real numbers. I've seen very few cases where complex numbers are used in programming and none when it comes ...
• 1,055
106 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 ...
• 121
1 vote
185 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 ...
• 385
2k 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 ...
• 1,352
62 views

### Can we see all of mathematics as an attempt to simplify computations?

This is a rather strong claim, and therefore likely to be incorrect, but hear me out. Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including ...
• 3,474
51 views

### Effective Procedures and P vs NP Problem

If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two ...
• 135
1 vote
108 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 ...
• 133
1 vote
71 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
71 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 ...
• 245
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 ...