Hot answers tagged

6

If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically. Some examples: Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable ...


2

Bounded loops terminate, unbounded (as in your example) don't necessarily terminate.


2

Given a non-negative integer $x$, let $|x|$ denote the number of ones in the binary representation of $x$. You can prove the claim by induction on $n$. The base case $n=0$ is trivially true. Consider then $n>0$. During the first iteration, the algorithm prints $n$ stars. The number $x$ of stars printed by the other iterations is exactly the number of ...


2

There is a definition, take a look at turing machines. It still is extremely complicated to work with, so it won't be perfect. But it sill does give a different definition of computation, that can be useful in constructing theorems, such as the time hierarchy theorem.


1

C and C++ are low-level languages that give the programmer precise control over the memory layout. Each object takes a constant amount of memory which is fully determined (on a given implementation) by its type. The sizeof operator lets programs know this size. An object may contain pointers. The data that the pointers points to, if any, is not part of the ...


1

We don't "require" loop invariants. They are a technique used when proving algorithm correctness. Lets take a look at a simple example of how loop invariants are useful: Consider the problem where we get an array $A$ and have to find the maximal value of it, i.e. compute $max(A)$. We created the following algorithm for the problem, and we want to ...


1

Loop invariants are crucial for showing an algorithm is correct (cf. proof by induction). For example, suppose you need to sort an array of distinct integers. One simple way to do it is by using selection sort. Why is selection sort correct, i.e., why does it actually solve the problem? If we understand intuitively why the algorithm works, we can also ...


1

Your first DFA is minimal. To see this, for each pair of states $q_i \neq q_j$ we need to come up with a word $w$ such that $\delta(q_i,w) \in F$ and $\delta(q_j,w) \notin F$, or vice versa, where $F$ is the set of accepting states. Here is such a list of words: $q_0,q_1$: $\delta(q_0,b) \notin F$ and $\delta(q_1,b) \in F$. $q_0,q_2$: $\delta(q_0,\epsilon) \...


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