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
2 votes
1 answer
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 ...
user avatar
10 votes
4 answers
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,...
user avatar
2 votes
0 answers
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-...
user avatar
  • 163
0 votes
1 answer
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. ...
user avatar
  • 168
1 vote
0 answers
23 views

Finding square root of a gram matrix over the integers [closed]

Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
user avatar
2 votes
1 answer
32 views

Why is this mapping from binary to natural numbers surjective?

In my Lecture we came across something of importance for the Church-Turing-Thesis and i noticed one particular function, which confused me. Function: Let $bin(x)$ be the injective binary extension ...
user avatar
1 vote
0 answers
44 views

What algorithm is best for resource gathering in an RTS game in quickest time?

Though the concept can be for many RTS games but lets use the specific system of 'age of empires'. For simplicity one resource will be considered. Food. So in the game there are villagers who gather ...
user avatar
-1 votes
1 answer
50 views

What does x sign mean in functions

I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
user avatar
0 votes
1 answer
73 views

Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here. As highlighted by the lack of a 7*2^64/8 term it is not ...
user avatar
5 votes
1 answer
88 views

Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?

Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions? It is something which I have been unclear with for a while (from a ...
user avatar
0 votes
1 answer
43 views

Is a zero matrix nilpotent matrix?

Let a matrix $A=0$. Can I say $A$ is nilpotent? I am asking if the zero matrix is nilpotent or not. Nilpotent means that $A^k = 0$ for some $k$ that is a non-negative integer. When $k = 1$, $A^k = A = ...
user avatar
1 vote
1 answer
31 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
user avatar
2 votes
2 answers
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 ...
user avatar
2 votes
0 answers
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: ...
user avatar
  • 1,871
0 votes
0 answers
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-...
user avatar
  • 119
0 votes
0 answers
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 ...
user avatar
  • 1
1 vote
1 answer
20 views

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

The following algorithm constructs a binary tree. ...
user avatar
  • 73
0 votes
0 answers
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)...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 101
1 vote
1 answer
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 ...
user avatar
11 votes
1 answer
1k 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 ...
user avatar
5 votes
2 answers
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 ...
user avatar
-1 votes
3 answers
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 ...
user avatar
7 votes
1 answer
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
  • 141
0 votes
1 answer
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 ...
user avatar
  • 3
1 vote
1 answer
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 ...
user avatar
  • 13
1 vote
1 answer
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 ...
user avatar
  • 1,871
5 votes
3 answers
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, ...
user avatar
  • 125
0 votes
1 answer
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 ...
user avatar
  • 1,871
1 vote
1 answer
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
2 votes
1 answer
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)] = -\...
user avatar
  • 131
1 vote
3 answers
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 ...
user avatar
  • 11
0 votes
1 answer
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 (<...
user avatar
  • 320
0 votes
1 answer
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? ...
user avatar
  • 141
3 votes
1 answer
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 ...
user avatar
  • 216
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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), ...
user avatar
0 votes
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
  • 385
2 votes
2 answers
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 ...
user avatar
  • 1,352
0 votes
0 answers
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 ...
user avatar
  • 3,474
0 votes
1 answer
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 ...
user avatar
  • 135
1 vote
2 answers
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 ...
user avatar
  • 133
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 245
14 votes
3 answers
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 ...
user avatar
  • 143
1 vote
1 answer
76 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 ...
user avatar