Questions tagged [mathematical-foundations]
Questions about the relation of (subfields of) computer science to the relevant mathematical foundations and their application.
129
questions
1
vote
0
answers
37
views
Quines that output functions of code and input
A Quine is a (non-empty) program that takes no inputs and returns its own source code as the output. For a function f: strings * 'a -> 'b, define an f-Quine as a program P that takes an input x ...
0
votes
1
answer
88
views
Is "Bitwise Complement Operator" (~ tilde) distributive?
To be more precise, Is ~(a+b) = ~a + ~b? Here, "~" bitwise NOT operator.
I ran into this question while thinking about ...
- 1
1
vote
2
answers
62
views
Division by zero in APL: assign return value 0 or 1
Recently I began learning a couple array based programming languages: Dyalog APL and BQN. And I cam across this peculiar manner in which division by zero is handled in Dyalog APL. Using the in-built ...
- 113
0
votes
2
answers
80
views
How to represent a point cloud in the pseudocode of an algorithm?
I am writing a scientific paper in which I describe some algorithms (using pseudocode) that have point clouds as inputs. In these algorithms, I need a mathematical structure to represent a point cloud....
-1
votes
1
answer
35
views
How to show invariance under additive and multiplicative illumination changes
The task is to "Show that the transformation f -> ((ln fx)x, (ln fy)y) is invariant under additive and multiplicative illumination changes."
From my lecture notes, for ((ln f)x, (ln f)y), ...
- 1
2
votes
1
answer
68
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 ...
- 21
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,...
- 225
2
votes
0
answers
40
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
0
votes
1
answer
45
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.
...
- 178
1
vote
0
answers
29
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 \...
- 11
2
votes
1
answer
63
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 ...
- 25
1
vote
0
answers
121
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 ...
-1
votes
1
answer
51
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?
0
votes
1
answer
93
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 ...
5
votes
1
answer
98
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 ...
0
votes
1
answer
53
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 = ...
1
vote
1
answer
50
views
Efficient cardinality of set overlap relation
Assume that we have a set S of sets s.
Every pair (s,s') in ...
- 177
2
votes
2
answers
557
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 ...
- 23
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:
...
- 2,103
0
votes
0
answers
40
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
0
votes
0
answers
50
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
1
vote
1
answer
21
views
Proof the number of expected node in a binary using mathematical induction
The following algorithm constructs a binary tree.
...
- 73
0
votes
0
answers
29
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)...
- 1
0
votes
0
answers
55
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
1
answer
60
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
10
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 ...
- 213
8
votes
2
answers
426
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 ...
- 317
-1
votes
3
answers
52
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 ...
7
votes
1
answer
200
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 ...
- 71
1
vote
2
answers
64
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
0
votes
1
answer
57
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 ...
- 3
1
vote
1
answer
830
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
1
answer
81
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 ...
- 2,103
5
votes
3
answers
474
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
0
votes
1
answer
45
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 ...
- 2,103
0
votes
1
answer
155
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,042
3
votes
2
answers
672
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
1
answer
644
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
3
answers
157
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
0
votes
1
answer
75
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
0
votes
1
answer
67
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
3
votes
1
answer
487
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
0
votes
0
answers
39
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
1
answer
117
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), ...
- 91
0
votes
1
answer
62
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,111
2
votes
0
answers
123
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
2
answers
313
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
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 ...
- 1,362
0
votes
0
answers
69
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,492
0
votes
1
answer
55
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