# Questions tagged [mathematical-foundations]

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

110 questions
Filter by
Sorted by
Tagged with
13 views

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

The following algorithm constructs a binary tree. ...
24 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)...
21 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 ...
19 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 ...
821 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 ...
109 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 ...
44 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 ...
176 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 ...
44 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 ...
33 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 ...
43 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 ...
38 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 ...
116 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, ...
37 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 ...
64 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 ...
47 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 ...
23 views

96 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 ...
6k 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", "...
86 views

59 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 ...
81 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$?
470 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 ...