# Tag Info

## Hot answers tagged mathematical-foundations

225

Let me offer one reason and one misconception as an answer to your question. The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this: function MaximumWindow(A, n, w): using a sliding window, calculate (in O(n)) the sums of all ...

77

(I am probably risking a few downvotes here, as I have no time/interest to make this a proper answer, but I find the text quoted (and the rest of the article cited) below to be quite insightful, also considering they are written by a well-known mathematician. Perhaps I can improve the answer later.) The idea, which I suppose isn't particularly distinct from ...

55

Allow me to start by quoting E. W. Dijkstra: "Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians." (from EWD498) Although what Dijkstra meant with `programming' differs quite a bit from the current usage, there is still some merit in this quote. The other answers have ...

46

Lamport provides some ground for disagreement on prevalence of errors in proofs in How to write a proof (pages 8-9): Some twenty years ago, I decided to write a proof of the Schroeder-Bernstein theorem for an introductory mathematics class. The simplest proof I could find was in Kelley’s classic general topology text. Since Kelley was writing for a ...

45

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons. General recursive (i.e., $\mu$-recursive) functions are significantly less expressive than lambda calculi. Thus, they make a ...

43

Answer why was the data considered to be a discrete mathematical entity rather than a continuous one This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation. Note that "discrete" does not mean "integer" or something like that. "discrete" ...

39

One big difference is that programs typically are written to operate on inputs, whereas mathematical proofs generally start from a set of axioms and prior-known theorems. Sometimes you have to cover multiple corner cases to get a sufficiently general proof, but the cases and their resolution is explicitly enumerated and the scope of the result is implicitly ...

39

Fundamentally, a logic consists of two things. Syntax is a set of rules that determine what is and is not a formula. Semantics is a set of rules that determine what formulae are "true" and what are "false". To a model theorist, this is expressed by relating formulas to the mathematical structures that they're true in; to a proof theorist, truth corresponds ...

29

Computers represent a piece of data as a finite number of bits (zeros and ones) and the set of all finite bit strings is discrete. You can only work with, say, real numbers if you find some finite representation for them. For example, you can say "this data corresponds to the number $\pi$", but you cannot store all digits of $\pi$ in a computer. Hence, ...

25

They say the problem with computers is that they do exactly what you tell them. I think this might be one of the many reasons. Notice that, with a computer program, the writer (you) is smart but the reader (CPU) is dumb. But with a mathematical proof, the writer (you) is smart and the reader (reviewer) is also smart. This means you can never afford to get ...

23

One issue that I think was not addressed in Yuval's answer, is that it seems you are comparing different animals. Saying "the code is correct" is a semantic statement, you mean to say that the object described by your code satisfies certain properties, e.g. for every input $n$ it computes $n!$. This is indeed a hard task, and to answer it, one has to look ...

21

While fields such as computer science, mathematics and physics are relatively well-organized, Logic has a chaotic history. Its organization is really confusing so I think it's important to read some history to understand the dense structure of the field. The path you should choose will depend on your background and aims. What is a logic ? The traditional ...

19

So, there are many fields of math that are relevant to the Science of CS, but for programming specifically: Graph theory: this is the big one. Graphs and trees are everywhere. Networks, maps, paths in video games. Even things like solving a Rubiks cube can be modelled as a graph algorithm and solved with A*. Discrete math: aside from graph theory, knowing ...

18

Theoretical computer science is what theoretical computer scientists do; and mathematics is what mathematicians do. Other than that, there is no accepted definition of either. One might argue that theoretical computer science is a particular branch (or branches) of mathematics, influenced (at least originally) by the problem of efficient computation. Many ...

18

What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter? I believe that the primary reasons are idempotency (gives the same results for the same inputs) and immutability (doesn't change). What if a mathematical proof could give different ...

18

Here is a concrete encoding that can represent each symbol in less than 1 bit on average: First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111. I've not said what happens if there is ...

16

You don't need any math to write a Hello World or a very simple website. You will need to know some discrete mathematics and algorithm analysis to write a program that finds a route between two cities. You will need to know matrix transformations and quaternions to write a game engine. You will need to know a lot about all kinds of mathematical fields to ...

16

The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with probability $\tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't ...

13

The dot just means "such that"; it's often omitted. The difference between the two formulas is the difference between "everybody has a mother" and "there is somebody who is everybody's mother."

13

Let $\mathcal{D}$ be the following distribution over $\{A,B,C\}$: if $X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$. For each $n$ we can construct prefix codes $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ such that $$\lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{... 13 They represent continuous quantities with discrete approximations. Mostly, this is done with floating point, which is analogous to scientific notation. Essentially, they work with something like 1.xyz\times 10^k, with some appropriate number of decimal places (and in binary, rather than decimal). It's also possible to work with some irrational numbers ... 12 There's no contradiction, here. The first case defines the partial function g\colon \mathbb{N}\to\mathbb{N} given by$$g(n) = \begin{cases} x &\text{if $x\in\mathbb{N}$ and }x^2=n\\ \text{undefined} &\text{if no such $x$ exists.} \end{cases} As the text says, "the domain of $g$ is the set of perfect squares." The second case defines the ...

12

Your question is answered by the arithmetical hierarchy. The existence of an odd perfect number is a $\Sigma_1$ statement, and so you can test it using a $\Sigma_1$ machine, which halts iff the statement is true. The twin prime conjecture is a $\Pi_2$ statement, and so you can construct a TM with access to the halting oracle which halts iff the statement is ...

12

I agree with what Yuval has written. But also have a much simpler answer: In practice softwares engineers typically don't even try to check for correctness of their programs, they simply don't, they typically don't even write down the conditions that define when the program is correct. There are various reasons for it. One is that most software engineers ...

11

There are a lot of good answers already but there are still more reasons math and programming aren't the same. 1 Mathematical proofs tend to be much simpler than computer programs. Consider the first steps of a hypothetical proof: Let a be an integer Let b be an integer Let c = a+b So far the proof is fine. Let's turn that into the first ...

10

The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra. ...

10

Yes. The quantum Turing machine is a mathematical formalization of a computation model for a quantum computer. See also https://en.wikipedia.org/wiki/Quantum_computing#Developments and https://en.wikipedia.org/wiki/Quantum_complexity_theory and https://en.wikipedia.org/wiki/BQP.

10

I like Yuval's answer, but I wanted to riff off of it for a bit. One reason you might find it easier to write Math proofs might boil down to how platonic Math ontology is. To see what I mean, consider the following: Functions in Math are pure (the entire result of calling a function is completely encapsulated in the return value, which is deterministic and ...

9

A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or ...

9

I see two possible points of confusion in your question, and I will address them separately. What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union." "The union of $L_1,L_2$ is $\{x:x∈L_1∨x∈L_2\}$ Does this mean that, for any string $s∈L_1$, we also have $s∈L_2$?" What is "Closure Under Union"? Regular ...

Only top voted, non community-wiki answers of a minimum length are eligible