As of May 31, 2023, we have updated our Code of Conduct.

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
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 ...
Pooya Farshim's user avatar
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 ...
siv2r's user avatar
  • 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 ...
oliverjones's user avatar
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....
claydergc's user avatar
-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), ...
Autumn's user avatar
  • 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 ...
montokapro's 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,...
Evi1M4chine's user avatar
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-...
JRC's user avatar
  • 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. ...
A Paul's user avatar
  • 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 \...
Chao Sun's user avatar
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 ...
Mark Lauer's user avatar
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 ...
Uchiha Madara's user avatar
-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?
Thanuja Dilhan's user avatar
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 ...
Adriaan Jacobs's user avatar
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 ...
Danish A. Alvi's user avatar
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 = ...
user133085's user avatar
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 ...
Radio Controlled's user avatar
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 ...
Thuraya Otto's 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: ...
Lance's user avatar
  • 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-...
JDoeDoe's user avatar
  • 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 ...
wheat's user avatar
  • 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. ...
Www's user avatar
  • 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)...
Mariam 's user avatar
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 ...
QED's user avatar
  • 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 ...
Anton Jebrak's user avatar
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 ...
user267839's user avatar
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 ...
thoughtpolice's user avatar
-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 ...
Ansar Ali Akash's user avatar
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 ...
Lisramic's user avatar
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 ...
M.N.Raia's user avatar
  • 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 ...
BK1603's user avatar
  • 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 ...
guest's user avatar
  • 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 ...
Lance's user avatar
  • 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, ...
user37344's user avatar
  • 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 ...
Lance's user avatar
  • 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 ...
Abhishek Ghosh's user avatar
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 ...
Physical Mathematics's user avatar
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)] = -\...
Eka's user avatar
  • 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 ...
Ferdan's user avatar
  • 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 (<...
52d6c6af's user avatar
  • 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? ...
Garrett's user avatar
  • 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 ...
0x777C's user avatar
  • 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 ...
seungho hyun's user avatar
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), ...
user8714896's user avatar
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 ...
ChocolateOverflow's user avatar
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 ...
Jim Pivarski's user avatar
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 ...
MarkokraM's 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 ...
evil_potato's user avatar
  • 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 ...
user56834's user avatar
  • 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 ...
Ajax's user avatar
  • 135