# Question
Title: Approximation factor preserving reduction
The definition of *approximation factor preserving reduction* from the book by Vijay V. Vazirani, page 365:

> Let $\Pi\_1$ and $\Pi\_2$ be two **minimization** problems, an approximation factor preserving reduction from $\Pi\_1$ to $\Pi\_2$ consists of two polynomial-time algorithms, $f$ and $g$, such that:
>
> * for **any** instance $I\_1$ of $\Pi\_1$, $I\_2 = f(I\_1)$ is an instance of $\Pi\_2$ such that $OPT\_{\Pi\_2}(I\_2) \leq OPT\_{\Pi\_1}(I\_1)$.
> * for **any** solution $t$ of $I\_2$ (constructed above), $s = g(I\_1, t)$ is a solution of $I\_1$ such that: $obj\_{\Pi\_1}(I\_1, s) \leq obj\_{\Pi\_2}(I\_2, t)$.

It is clear that this reduction preserves the approximation factor.

**QUESTION:** Since **any** solution of $I\_2$ shall have an objective value no less than that the objective value of the corresponding solution of $I\_1$, if the solution $t$ to $I\_2$ is optimal, that is, $obj\_{\Pi\_2}(I\_2, t) = OPT\_{\Pi\_2}(I\_2)$, **doesn't this imply that equality should always be satisfied on the first condition**? In other words, $OPT\_{\Pi\_2}(I\_2)$ can never be less than $OPT\_{\Pi\_1}(I\_1)$, or else, some solution of $I\_1$ will have an objective value less than its optimal (which yields a contradiction for a minimization problem).

I understand that we are mainly interested in optimization problems that are NP-hard, however, in this reduction, we did not specify that the solution of $I\_2$ should not be optimal.

In this book, the author gives several such reductions between different problems, however, **none** of those reductions were built upon the strict equality of the first condition.

# Answer
> 0 votes
That looks right. The only exception I can think of is problems where there isn't an optimal solution, but just a sequence of ever-better solutions converging to, but never attaining, some optimum. Though actually, even then, if the optima weren't the same, it should be possible to find some solution in between the optima, which would arrive at a contradiction. So it seems what you say should still hold, unless I'm also missing something.

---
Tags: algorithms, complexity-theory, optimization, np-complete, approximation
---


title: Headless Prolog?

text:
# Question
Title: Headless Prolog?
I've been playing around with prolog and realised something. You can do everything without predicate names.

e.g. Just change all predicates

$$a(b,c,d,e,..)$$

into

$$prop(a,b,c,d,e,..)$$

Where $prop$ is some character that you can use for all function names.

So $isRed(X)$ becomes $prop(isRed,X)$.

Which makes me wonder if there is any point to prolog having function heads? Couldn't everthing be done using lists? e.g. $loves(romeo,juliet)$ could just as easily be written $\[loves,romeo,juliet\]$ without loss of information.

Have I missed something or is there anything special about predicate function heads?

# Answer
> 1 votes
One issue is efficiency. Having different predicates means more efficient compilation. It also allows for separate compilation, using modules, which is important for even medium-sized programs. Additionally, using the WAM terminology, you will end up with a lot more choicepoints than you expect.

Modern compilers go to a lot of trouble to perform optimisations using type and mode inference (and annotations, if they are available). You lose all that when you give the compiler less information.

Another consideration is semantic, especially considering non-logical control such as the cut. Consider this:

```
p(X) :- q(X), !.
p(X) :- r(X), \+ s(X).

a(X) :- b(X).
a(X) :- c(X).

```

Here, the cut operator prunes choicepoints in the call to `p/1`. If you translated this into "headless" form:

```
pred(p,X) :- pred(q,X), !.
pred(p,X) :- pred(r,X), \+ pred(s,X).

pred(a,X) :- pred(b,X).
pred(a,X) :- pred(c,X).

```

Now, the cut operator prunes choicepoints in the call to `pred/2`. If you promise that you only ever call `pred/2` with the first argument bound to an atom, that's probably okay, but if you are doing higher-order programming, it may not behave as you expect.

---
Tags: prolog
---


# Question
Title: How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"?
I am reading about embedding/automation of modal logics in classical higher order logic (http://page.mi.fu-berlin.de/cbenzmueller/papers/C46.pdf) and Goedels proof of God's existence is prominent example here https://www.isa-afp.org/entries/GoedelGod.html (as encoded for Isabelle/HOL).

This embedding has embedding for Leibniz equality for individuals:

```
abbreviation mLeibeq :: "μ ⇒ μ ⇒ σ" (infixr "mL=" 90) where "x mL= y ≡ ∀(λφ. (φ x m→ φ y))"

```

and this type of euqality is used for the first axiom already:

```
A1a: "[∀(λΦ. P (λx. m¬ (Φ x)) m→ m¬ (P Φ))]"

```

which can be written without lambdas as:

```
A1a: ∀φ[P(¬φ)↔¬P(φ)]

```

My question is - how to understand the expression `∀(λφ. (φ x m→ φ y))`, because usually we have `∀x.P(x)`? I.e. universal quantifier expects the argument (`x`) and the predicate (`P(x)`), but this expression contains noone know what? is entire `(λφ. (φ x m→ φ y))` and argument `x` or Predicate `P(x)`? What can be omitted here, what is the convention used here?

# Answer
The $x$ in $\forall x . P(x)$ is *not* an argument. It is a *bound variable* indicating which variable the quantifer is ranging over.

Let us compare the situation to the definite integral, for concretness just from $0$ to $1$. Here is an example: $$\int\_0^1 x^2 + 3 x \\, dx$$ This is a very archaic way of writing mathematical expressions that mathematicians like to stick to. In general (and ignoring details about non-integrable functions) the definite integral is itself a function: it takes a function $f$ as an argument, such as $f(x) = x^2 + 3x$ and returns a number (the area under the curve). So we could simply write $I$ for "integrate from $0$ to $1$" and then the integral of $f$ is simply $$I(f)$$ (Or if you want to keep the integration bounds visible write $I\_0^1(f)$, but I won't). The argument $f$ need not be a symbol, it can be a complex expression: $$I(x \mapsto x^2 + 3 x)$$ Notice how "$dx$" above changed to "$x \mapsto$". In $\lambda$-calculus notation we would write this as $$I(\lambda x . x^2 + 3 x).$$ In archaic notation people sometimes feel uneasy about writing $$\int\_0^1 f$$ and so they end up always displaying $dx$ by writing $$\int\_0^1 f(x) \\, dx$$ even though there really is no need to do so, because $\int\_0^1$ is a *higher-order function* which maps real-valued functions to real numbers. If you want to make traditional mathematician feel uneasy you should write $$\int\_0^1 (x \mapsto x^2 + 3 x)$$ on their whiteboards

If this much is clear, then it should be easy to see that the universal quantifier $\forall$ is like integration, except that it takes a *propositional function* (one mapping into truth values instead of numbers) and returns a *truth value*. The archaic notation $$\forall x . (x^2 + 3 x \> -3)$$ can be changed, just like for integrals, to $$A(f).$$ Here $A$ is the universal quantifier, and $f$ its argument, which is a function mapping from a set to the truth values. An example of such a function is $f(x) = (x^2 + 3 x \> -3)$. And again, we can inline the complex expression to get $$A(\lambda x . (x^2 + 3 x \> -3))$$ Now just replace $A$ with $\forall$ for good old times sake: $$\forall(\lambda x . (x^2 + 3 x \> -3)).$$ This his how computers like it. The notation is general, so we can write just $\forall f$ instead of $\forall x . f(x)$, and it exposes $\forall$ for what it is: a *higher-order* function that maps propositional function to truth values.
> 8 votes

---
Tags: lambda-calculus, first-order-logic, modal-logic, higher-order-logic, isabelle
---


# Question
Title: What does it mean to "show algebraically" in propositional logic?
The biconditional operator $\iff$ of Propositional Logic can be defined by the identity

$p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$

Use the identity $(1.1)$ and identities from the list on page 2, to show algebraically that

$p \iff q \equiv (\lnot p \land \lnot q) \lor (q \land p)$

State which identity you are using at each step.

---

What does this question mean by asking to "show algebraically"? I have tried referring to my notes and online search but no luck with a definition! These propositions are already algebraic, are they not? Having some issues understanding the wording of the question. This is from a mock university test. I'm assuming it wants me to demonstrate using a truth table?

# Answer
Although you haven't posted any of the logical rules the problem statement refers to, it is reasonable to assume they are similar to those found in many standard logic textbooks. To prove your identity, I will make use of

$$ \begin{align} P \land Q & \equiv Q \land P, &\text{$\land$ commutativity} \\ P \land (Q \lor R) & \equiv (P \land Q) \lor (P \land R), &\text{$\land$ distribution} \\ P \land \lnot P & \equiv \bot &\text {(3)} \\ P \lor \bot &\equiv P, & \text{$\bot$ annihilation} \end{align} $$

where $\bot$ denotes falsehood. With that in mind

$$ \begin{align} p \iff q \equiv & \\ (\lnot p \lor q) \land (\lnot q \lor p) \equiv & & \text{By definition}\\ ((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land p) \equiv & &\text{By distribution of $\land$} \\ (\lnot q \land (\lnot p \lor q)) \lor (p \land (\lnot p \lor q)) \equiv & &\text{By commutativity of $\land$} \\ (\lnot q \land \lnot p \lor \lnot q \land q) \lor (p \land \lnot p \lor p \land q) \equiv & &\text{By distribution of $\land$} \\ (\lnot q \land \lnot p \lor \bot) \lor (\bot \lor p \land q) \equiv & &\text{By $(3)$} \\ (\lnot q \land \lnot p) \lor (p \land q) \equiv & &\text{By $\bot$ annihilation} \\ (\lnot p \land \lnot q) \lor (q \land p) \equiv & &\text{By commutativity of $\land$} \\ & &\square \end{align} $$

I've assumed throughout $\land$ to have higher precedence than $\lor$.
> 1 votes

---
Tags: boolean-algebra, propositional-logic
---


# Question
Title: Is it incorrect too say that this function problem cannot be in $FNP$?
Decision Problem: Is $2^k$ \+ $M$ NOT a prime?

$K$ and $M$ are our inputs represented as integers.

Function Variant: Output the result of $2^k$ \+ $m$

We can consider, $M$ = $0$.

Proof that calculating 2^n requires an exponential amount of digits as the result

## Question

Is it true that a non-deterministic machine cannot output $2^n$ (exponential) digits in polynomial time?

Does this mean that the problem is not in $FNP$?

# Answer
When we say that an algorithm runs in polynomial time, we mean that its running time is at most a polynomial of the length of the input. I assume the input is an integer $n$. The usual way to represent integers is in binary; then the integer $n$ requires $\lg n$ bits to represent. Therefore, a polynomial-time algorithm will have a running time that is at most $p(\lg n)$, where $p$ is some polynomial.

In each step of computation, the algorithm can output at most one item (e.g., $O(1)$ bits of output). So, an algorithm with polynomial running time $p(\lg n)$ can output at most $p(\lg n)$ digits of output, for some polynomial $p$. You can think of this as at most $(\lg n)^c$ digits of output, for some constant $c$ (the constant $c$ will depend on the algorithm).

Now, $2^n$ is asymptotically much larger than $(\lg n)^c$. So, no, a polynomial-time machine cannot $2^n$ digits, when given $n$ as input.

What if the machine is non-deterministic? The same is still true. Non-deterministic means that there are multiple possible branches that the computation could follow. But for each branch, it's still true that the length of the output can be no longer than the number of steps of computation. So, each branch of the non-deterministic computation is limited to outputting at most $(\lg n)^c$ digits.

You might be wondering, what is *the* output of a non-deterministic machine? Well, that's not a well-defined question. Instead, for a non-deterministic machine, we can talk about the set of possible outputs. If it is a polynomial-time machine, then there are a set of possible outputs, but they will all be polynomial in length. So, a string of $2^n$ digits cannot be among the set of possible outputs; it's too long.

I sense that you are somewhat new to computational complexity. I suggest that you try to avoid thinking about "function" complexity classes until you are really solid on the "decision" complexity classes. I find the decision classes easier to think about, and the function classes harder to think about.

Is the problem in FNP? Well, probably it will be most useful to refer to the definition of FNP. I'm out of time to look that up right now and check it carefully, but I expect you're going to find that the answer is 'no', because the definition requires (explicitly or implicitly) that the length of the output be at most a polynomial in the length of the input.
> 2 votes

---
Tags: np, nondeterminism
---


# Question
Title: Median of distribution with memory constraint
## Task

I want to **approximate the median of a given distribution** $D$ that I can sample from.

A simple algorithm for this, using $n$ samples, is:

```
samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

```

However, I am looking for an algorithm that **requires less than $O(n)$ space**.

## Ideas

I have looked into these algorithms:

* Median of medians: Needs $O(n)$ space, so it does not work for me.
* Randomized median: It seems like this could be easily generalized to an algorithm that uses $O(n^{3/4})$ space.

Are there any other algorithms that use less then $O(n)$ space that could solve my problem? In particular, I was thinking there may be an algorithm that uses $O(m)$ space by generating batches of samples from $D$ of size $m$...

## Details

* Ideally, I am looking for a reference to an algorithm that also includes analysis (success probability, expected runtime, etc).
* Actually, I need an algorithm to estimate $D$'s $p$-th percentile for a given $p$, but I am hoping most median-finding algorithms can be generalized to that.
* I would like to achieve the same accuracy as the simple algorithm shown above. One way to achieve this is by using an algorithm whose output distribution is the same as the sample algorithm (but maybe the new algorithm may fail in rare cases)

# Answer
Sure, you can definitely achieve this using a bit more running time. Here is a conceptually simple approach, which might not be optimal, but will get you started and is probably pretty good:

Use binary search to find an approximate median $m$. How do you know whether is candidate $m$ is too large or too small? Sample $n'$ times from the distribution, count how many times the samples are $\ge m$, and compare that count to $n'/2$. This can be done with $O(1)$ space.

Then the key question becomes: how do we choose $n'$, to control the probability of error? A simple approach is to choose $n'$ to be sufficiently bigger than $n$ that the probability of error in each iteration of binary search is $t$ smaller than the probability of error when using $n$ samples, where $t$ is the number of iterations of binary search needed to achieve the desired accuracy. Then, a union bound ensures that this will meet your accuracy conditions.

Unfortunately, your accuracy condition is a bit hard to work with, when we don't know anything about the distribution of data, as the accuracy of the sample median can be arbitrarily bad. For instance, consider a distribution that outputs $0$ with probability $(1-\epsilon)/2$ and $100$ with probability $(1+\epsilon)/2$. Then the sample median is about equally likely to be 0 or 100, whereas the distribution median is 100, so the average error of the sample median is about 50 (unless you're drawing $\gg 1/\epsilon^2$ samples). That's a particularly nasty distribution, and it's going to be hard to work with. But if you assume the distribution is approximately Gaussian (say) with standard deviation $\sigma$, then the error of the sample median, with $n$ samples, is roughly $1.25 \sigma/\sqrt{n}$. Thus, the above algorithm can be used where we set $t \approx \lg (\sqrt{n}/1.25)$ and we set $n' \approx n t^2$.

That's one simple approach. You can probably do better. You might like to look up streaming algorithms for computing the median, as they tackle the problem you're working with: given an unlimited number of samples from the distribution, but only a limited amount of space, what's the best estimate we can get for the median? For instance, here is one simple algorithm: the first layer repeatedly takes three samples and outputs the median of those three; the second layer repeatedly takes three numbers from the first layer and outputs the median of those three; and so on. After logarithmically number of layers, you get a reasonable approximation to the median. There's an entire literature on this subject, and you should be able to find lots more.
> 1 votes

---
Tags: algorithms, space-complexity, randomized-algorithms, randomness
---


# Question
Title: Why does memory data isn't organized in two or more lines?
I understand that computer memory data is sequential;
It is one long line organized in one or more *address/es*, each of which containing one or more fixed size *word/s* which contain raw data (in an initial manner, just offset value/s, I would assume).

Why does memory data isn't organized in two or more lines (why it's just one long line, or at least, so it would appear, via a user interface such as some *text editor*)?

# Answer
> 1 votes
The notion of a "line" is an abstraction we impose. Currently our memory works as follows: you provide an address to the memory module that you want to read, and it returns the value at that address; or if you want to update memory, you provide an address and the new value, and it overwrites the value at that address with the new value.

Why do we build memory that way? Well, the current way is simple and works, and can be implemented efficiently in circuits. If you wanted to consider some other alternative, you'd have to think about what are the benefits and what are the costs. I'm not clear on exactly how your counter-proposal would work, but I expect it would add complexity (which ultimately might add to the cost of implement the memory subsystem, and also might make the system harder to understand for programmers) without a benefit that would make it worthwhile. If you wanted to dive into this in more detail, you'd probably start by learning how RAM works at the circuit level. Our current RAM is highly optimized to minimize the number of gates needed, i.e., to minimize cost.

---
Tags: sequential-circuit
---


# Question
Title: Can lists be defined in a special way so that they contain things of different type?
In https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf it is written that

> A type $\tau$ list is the type of lists with elements of type $\tau$

Why must a list contain elements of the same type? Why can't it contain elements of different types? Is there a way of defining a list polymorphically in the typed lambda calculus, so that it takes elements of any type?

Can we then use the List monad on lists, defined polymorphically?

# Answer
> 4 votes
The short answer is that $\tau\ \text{list}$ is *defined* as a type constructor, along with rules for formation and elimination, and so we could similarly *define* a type constructor that allowed terms of different types to form a single "variably-typed list". However, lists cannot take different types in the definition given, simply because they are defined with respect to a single type. In either case, adding lists, or variably-typed lists, involves extending the simply-typed $\lambda$-calculus, as lists of *any* kind do not exist in the usual presentation.

If we have a slightly richer type system than the simply-typed $\lambda$-calculus, we can encode variably-typed lists using standard $\tau\ \text{list}$s.

* If we have a form of subtyping, we can store terms of different types, as long as they share a supertype. However, when we project elements out of the list, we can no longer tell specifically what type they were to begin with (this may be familiar from object-oriented programming), so this is a little limited.
* If we have dependent sum types (also called $\Sigma$-types) and a universe type $\mathcal U$ (i.e. a "type of types"), we can form the type $(\Sigma\_{A : \mathcal U} A)\ \text{list}$, whose elements are pairs consisting of a type $A$ and a term of that type.

Finally, I'll just note that polymorphism doesn't help us if we want heterogeneous lists: it just allows us to manipulate homogeneous lists for different $\tau$ more effectively. Polymorphic types have to be uniform in some sense, which is why we need dependency here instead.

---

To answer a follow-up question: if we have two variably-sorted lists using the dependent type approach, we can concatenate and flatten lists just as with ordinary lists.

* The $\mathrm{List}$ monad has an operation $\mathrm{join}$ (in the language of Haskell), so given a list of variably-typed lists, $$l = \[\[(A, a), (B, b)\], \[(C, c), (D, d)\]\] : (\Sigma\_{X : \mathcal U} X)\ \text{list list}$$ we can perform $\mathrm{join}$ to get a new list: $$\mathrm{join}(l) = \[(A, a), (B, b), (C, c), (D, d)\] : (\Sigma\_{X : \mathcal U} X)\ \text{list}$$
* Similarly, $\tau\ \text{list}$ can be equipped with a concatenation operation $+\\!+$, so given the two lists in the previous example, we can concatenate them for a similar result: $$\[(A, a), (B, b)\]\ {+\\!+}\ \[(C, c), (D, d)\] = \[(A, a), (B, b), (C, c), (D, d)\] : (\Sigma\_{X : \mathcal U} X)\ \text{list}$$

# Answer
> 2 votes
No, that's not possible, at least not in a useful way. Think about what the type of `head` would be. When every element has same type, `head` has the type $\tau \\; \mathsf{list} \to \tau$. Without that guarantee, there would be no way to write a coherent type for `head`. For the list type to be useful, we want to be able to draw useful conclusions about what the type of the output of `head` is; and that requires all elements of the list to have the same type.

I suppose you *could* define a "list" some other way, but it either wouldn't be useful (you couldn't reason about the type of values you get out of it with `head`) or it wouldn't correspond to something that computer scientists would call a "list".

# Answer
> 2 votes
You can't usefully define a type $\mathsf{list}$ that doesn't indicate the type of its elements. That doesn't mean that you can't have lists that contain things of different types: it's still a $\tau \\, \mathsf{list}$, but you can put the “contain things of different types” part in the $\tau$.

(These basic ideas were already in D.W. and varkor's answers. It's important to realize that these answers aren't contradictory! They're looking at different aspects of the bigger picture.)

If the type system lets you define a type $\mathsf{list}$ that can contain elements of any type, then consider the return type of a destructor like $\mathsf{head}$ or $\mathsf{nth}$, or the type of the function argument to $\mathsf{fold}$. You have no information on the type of the elements, so they would have to allow any type. This means that for example $\lambda x. \mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$ will not give you back a value of the same type as $x$ (or $x \\, \mathsf{option}$, so that $\mathsf{head}$ can return $\mathsf{None}$ on empty lists). But then what do you get back from $\mathsf{head}$?

* If $\mathsf{head}$ allows the caller to specify any return type, then the type system is pretty much useless, since it allows arbitrary coercions between types through $\lambda x. \mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$. It's useless for logic since the Curry-Howard correspondence maps an arbitrary coercion between types to having every proposition imply every other proposition, so you have an inconsistent logic.
* If not, then you can't get back a value of the original type through $\lambda x. \mathsf{head}(\mathsf{cons}(x, \mathsf{nil}))$. So you may be able to build lists, but you can't get elements out of them.

A real-life example which in fact demonstrates both behaviors above is early versions of Java, before it had generics. Java has both a static type system and a dynamic type system. In the static type system, any¹ value can be transparently coerced to `Object`, because `Object` is considered a supertype of everything. So you can put any value in a `List`. But what you get back out of it is the original value cast to `Object`, not the original value itself. In the dynamic type system, you can coerce any type to any other type, so in practice, to get a value out of a list, you coerce it to the desired type. But having coercions defeats the purpose of a type system. This problem is the main reason why Java acquired generics: they allow the language to have $\tau \\, \mathsf{list}$ instead of $\mathsf{list}$ (or in Java notation, `List<T>` instead of `List`).

Just because a list has a type of elements — $\tau \\, \mathsf{list}$ is a list of elements of type $\tau$ — doesn't mean that you can't arrange to put values of different types in the same list. Pretty much any language that allows defining a list type does it by allowing algebraic data type definitions, something like this: $$ \tau \\, \mathsf{list} ::= \mathsf{nil} \mid \mathsf{cons} \\: \tau \\: (\tau \\, \mathsf{list}) $$ Suppose you want to put both integers and strings in the same list. Define a type $$ U ::= \mathsf{I} \\: \mathsf{int} \mid \mathsf{S} \\: \mathsf{string} $$ Now $U \\, \mathsf{list}$ is the type of lists that can contain a mixture of integers and strings, e.g. $\[\mathsf{I}(3), \mathsf{S}(\texttt{"foo"}), \mathsf{I}(4)\]$.

You can make heterogeneous lists this way to the extent that the type system allows heterogeneous types. Note that “heterogeneous lists” isn't quite correct: the list itself is homogeneous: it's a list of elements of type $U$. The heterogeneity is in the type $U$. To put an element in the list, you apply a constructor of $U$ first. After you get an element out of the list, apply a destructor of $U$ to get the original value with its original type.

You can do this with any type that the language supports. If you want a completely heterogeneous list, you need a language that supports an “any” type. That's `Object` in Java, for example. Strongly typed can have an “any” type if they carry the necessary type information at runtime. Java does it all the time. Languages that are statically typed (such as OCaml and other ML dialects, Haskell, Clean, Swift or Rust) can do it with a $\mathsf{dyn}$ type whose runtime representation contains the type of the value. With such a type, $\mathsf{dyn} \\, \mathsf{list}$ is a list type that can contain a value of any type. This type coexists with other list types such as $\mathsf{int} \\, \mathsf{list}$ (where the list elements don't carry runtime type information).

A related approach to building heterogeneous data structures is existential types. Existential types let you package a type with a value of that type: $(\exists \tau : P(\tau). a)$ where $a$ is an expression of some type $T$ such that $P(T)$ is true. For example, $\mathsf{dyn}$ can be modeled as a special case where $P$ is true of all types (an unbounded existential). A common use for existential types is to say that $\tau$ is a record, module or class with some particular elements or methods, without giving all the details: existential types are a way to model abstract types. With a bounded existential, you can still do some useful things with the value even without runtime type information (e.g. you can call the methods that $P$ describes), but not get the original type. A list whose elements have an existential type $T\_E = (\exists \tau \ldots)$ can be seen as a heterogeneous list (because its elements have different “real” types), but it's still homogeneous in the sense that if you retrieve a value from the list, all you know is its package type $T\_E$.

If the language has dependent types, you can package a value with its type in a way that allows recovering the original value: $\mathsf{package} ::= \sum\_{\tau:\mathsf{TYPE}} \tau$ where $\mathsf{TYPE}$ is the type of types. This is a dependent sum type where the first component happens to be a type. The $\mathsf{package}$ type is a way to implement unbounded existentials in a dependently typed language. You can construct bounded existentials by adding constraints on $\tau$. Once again, you can build heterogeneous lists in the sense that a $\mathsf{package} \\, \mathsf{list}$ contains elements whose “real” types are different, but the list itself is homogeneous in the sense that each list element has the type $\mathsf{package}$. As with existential types, you can't extract a value from a list and directly recover its “real” type. It's possible to destruct a value of type $\mathsf{package}$ by applying the second-element projection, but all you know about the result is that its type is the first-element projection: $p : \mathsf{package} \vdash \pi\_2(p) : \pi\_1(p)$.

So far, we've seen that in a non-degenerate type system, lists are homogeneous. It's possible to build heterogeneous lists, but the list type constructor itself is homogeneous: the heterogeneity comes from the element type. In a language that has both algebraic datatypes and types that depend on an integer (or something isomorphic to the naturals), it is possible to define a truly heterogenenous list type. Given a type family $(T\_n)\_{n \in \mathbb{N}}$, you can define the type of lists whose $n$th element has the type $T\_n$. Here's such a definition in the language of the calculus of inductive constructions, specifically in Coq syntax. First, I define an example of a family of types indexed by an integer: `tuple A n` is the type of `n`-element tuples whose components all have the type `A`. To keep the definition simple, all tuples have an additional value `U` at the beginning of unit type. Then I define the inductive type `hlist_` which is parametrized by both a type family `T` and an integer `n`, which is a heterogeneous list whose `k`th element has the type `n + k`. The parameter `n` is necessary to keep the definition constructive. Finally I show some example terms of type `hlist (tuple bool)`, that is, lists whose `n`th element is an `nth`-element tuple of `bool` values (with `U` prepended).

```
Inductive unit : Type := U : unit.
Fixpoint tuple (A : Type) (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => (tuple A m) * A
  end.

Inductive hlist_ (T : nat -> Type) n :=
  | Hnil : hlist_ T n
  | Hcons : (T n) -> hlist_ T (S n) -> hlist_ T n.
Definition hlist T := hlist_ T 0.

Check (Hcons (tuple bool) 0 U (Hnil _ _) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hnil _ _)) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hcons _ 2 (U, true, true) (Hnil _ _))) : hlist (tuple bool)).

```

¹ <sub> Except for some primitive data types, actually, but that's not important here. When I say “any” about Java in this answer, I mean objects only, not primitive data types. </sub>

---
Tags: lambda-calculus, functional-programming, category-theory
---


# Question
Title: Schedule Optimization With Priority and Weighted Costs
I need an algorithm to determine the best itinerary for a series of events.

*Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each event is at a physical location thus it takes time to travel from event to event. It is not necessary to attend every event.*

*What itinerary will yield the largest total reward?*

Does anyone know if there is an existing algorithm for this or one that would be easily adapted? Given the similarity to the traveling salesman problem I am tempted to start with a weighted TSP solution and work from there.

# Answer
> 2 votes
We can construct a directed graph with events as vertices, where an event $E\_2$ has an incoming edge from another event $E\_1$ if starting from $E\_1$, we can arrive $E\_2$ in time to get its reward. The edge value is the time difference between the events.

For each vertex (event), we do a depth first search rooted at this vertex where on each iteration we add the value of the previous tree edge to the current tree edge and check to see if it is greater than the time associated with the current vertex. If it is then our considered sequence of events from the root vertex has just timed out.

```
var MaxReward = 0
var bestItinerary = []

f(graph):
  for vertex v in graph:
    _f(v, v.time, 0, [])

_f(v, curr_time, rewardSoFar):
  if time > v.time:
    if rewardSoFar > MaxReward:
      MaxReward = rewardSoFar
      bestItinerary = itinerarySoFar
  else
    rewardSoFar = rewardSoFar + v.reward
    itinerarySoFar.append(v)
    for edge, neighbor in v.getNeighbors:
      _f(neighbor, curr_time + edge.value, rewardSoFar, itinerarySoFar)

```

# Answer
> 0 votes
I figured out one solution to my problem.

I created a graph of all the events as nodes. I then drew directed edges from each event to all events which could be attended after (accounting for travel time). Thus every valid path through the graph is a valid order to visit events in chronological time. Each edge is weighted with the reward for the event it ends at.

With this graph the time component is removed from the problem and I can use standard graph traversal algorithms to find the longest/heaviest path.

---
Tags: algorithms, graphs, dynamic-programming, traveling-salesman
---


title: Monte Carlo: what is a seed?

text:
# Question
Title: Monte Carlo: what is a seed?
I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried finding out what a seed is online, but I only seem to get results about 'why you should/shouldn't use a fixed seed', and unfortunately they have left me none the wiser as to what a seed actually is.

What is *seed* in this context?

# Answer
The seed is an initial number of the pseudorandom number generator(PRNG) which is in fact fully deterministic. It returns a sequence of numbers that looks random enough for many purposes, but always generates the same sequence for given value.

In order to make simulation non-repeatable (returning always the same value) they advice different initial value for every simulation (this is what non-fixed seed means).

Image taken from here
> 2 votes

# Answer
The other way to think of a seed is that it allows you to get the same string or random numbers for different runs. If you are building an algorithm, sometimes being able to repeat how you got to a place is very useful. It allows you to debug equations and logic.
> 0 votes

---
Tags: pseudo-random-generators, monte-carlo
---


# Question
Title: Is all data stored in computers stored as machine code?
I know that the most basic (and least abstract) code for programming is machine code (with binary of `0s` and `1s` being the typical machine code).

I also know that computers can save data even if they are turned off, by different types of *computer memory* (storage device memory, RAM and other computer system devices which can "remember" some data).

**Is all data stored in computers ("all data remembered in a given computer memory") stored as machine code?**
Is what's saved in a computer's "memory" (and becoming actually effective by electrical current correctly distributed to the computer system) just binary machine code in the sense that if I could read and understand that data directly without an operating system interfacing it for me it should appear in my mind as machine code, or rather, is it something else?

# Answer
I wouldn't put it that way. What is stored in memory is bits. It's just data in binary form.

Humans might then label some of those bits as "machine code" because we intend or expect it to be executed; or because it will be executed. That's a matter of interpretation we apply. The memory module just sees a bunch of bits. It just sees some data and has no knowledge of what the meaning or intended purpose of that data will be.

Memory is not limited to storing executable code. Computers also store other data in memory. For instance, your computer might store a copy of an email, or a picture or photograph you took. Those aren't code, but they can be stored in memory.

It may be helpful to think that the memory can be used to store data or can be used to store code -- but there is nothing in the computer architecture that enforces any distinction between the two. From the perspective of the memory module, it is just bits.
> 2 votes

# Answer
It is sometimes regarded just the other way round. We have storage for data, everything is data in first place. Machine code is data which is meant to be read into a processor's execution pipeline. So the distinction is a semantic one.

This has become somewhat ambiguous nowadays, where we have stuff like true-type fonts, which are perceived as data, but when you look closely, form a turing-complete system.
Similarly, it is not wrong to define the data that constitutes some of the popular document formats, as programs. The PDF is a good example. But it is not quite machine code; rather it is an interpreted piece of software, several layers of abstraction away from the hardware.

The premise of your question would mostly have been true for the predecessor of computers, the loom. There, the machine code was encoded as a pattern which actually, physically represented the pattern the machine was supposed to generate from that data.

More practically speaking, real-world operating system kernels have mechanisms to distinguish between data and executable code very clearly, also for security reasons. First, there is the concept of segments in program files, which can be marked code, or data, but not both. Crazy programming patterns like self-modifying code are mostly no longer possible on modern systems, because code segments are write-protected. Second, there are concepts like data execution protection (DEP) that prevent accidental attempts to direct the processors' instruction pointers to areas of memory that, by declaration, contain data.
> 0 votes

---
Tags: memory-hardware
---


# Question
Title: Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing through a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain whose stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?

# Answer
Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state. You want to find order within the disorder. Now, Metropolis and Simulated Annealing are slightly different things. Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode. What simulated annealing does is focus the Metropolis to find the absolute minimum.

So in annealing you start at a high temperature, which means basically that anything is possible. Think of quantum tunneling. The most improbable thing can happen when temperatures are very high. So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise. As you cool you focus on just what makes sense so that jumps are made only when they are better.

At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only. In the end you should have a good idea of the optimal solution.
> 1 votes

---
Tags: optimization, probability-theory, information-theory, probabilistic-algorithms, markov-chains
---


title: Universal Turing Machine algorithm

text:
# Question
Title: Universal Turing Machine algorithm
First, I learned this based on these facts:

1. Turing machine (*TM*) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q\_0,F\rangle$.
2. Any computation rules that can use to simulate any possible *TM* is called Turing-Complete.
3. Universal *TM* (*UTM*) is TM that is Turing-Complete.

Then, the question begins:

* If we have 7-tuple Notation of any **U** that is *UTM*, Is there an algorithm to find initial tape content **P** that **U** to simulate any *TM* **T** with any **I** input(s)? If it exists, Does it based on each **U** or pattern of **U**? If it does, give me some example(s)? If it does, explain the algorithm?
* Since all possible computations can be done with *TM*, Is there an algorithm to make *TM* simulate any algorithm **P** written in any language? If it exists, give me some example(s)?
* If both questions above exist the algorithm, Why don't we just make a single *UTM* **U** and use it to program itself then do every possible computation?

# Answer
> 1 votes
With regards too your first question I would take a different easier to understand route. Firstly you should note that most programming languages are (theoretically) Turing-Complete (which implied that for a program written in some programming language like C or Python you could transform it into a TM or vice versa).

I'm sure that you heard of the concept "interpreter". It's a program that takes a script as input and runs it (e.g. the python interpreter). You can probably write a simple interpreter yourself (great tutorial).

Now notice that your interpreter could be converted to a TM which takes programs as inputs and runs them, thus you *could* construct a UTM, and the input would be e.g. a python script.

With regards to your second question: as I mentioned most programming languages used today are (theoretically) Turing-Complete meaning that you could transform any Turing-Machine too a program in this language. The straight forward approach, which works in most object oriented languages is just to model a Turing-Machine (using e.g. a string as tape and an int to remember where on the tape your head is and so on...simple example). Algorithms that convert one program from one language to another are called transpilers.

I think I don't fully understand your last question. Of course you could plug a UTM into itself. It's like writing a python interpreter in python. The "problem" is that simulation comes at a cost. Generally if you simulate a UTM on a UTM the complexity of some operations increases.

---
Tags: algorithms, turing-machines, computer-architecture, turing-completeness
---


title: Is escaping a concept in CS?

text:
# Question
Title: Is escaping a concept in CS?
I understand "escaping data" as making an exception when matching data; for example, if a program can't match data wrapped in some character/s (such as single and/or double quotes) without an exception, than we make an exception when "escaping" such character/s to be matched.

**Is escaping a concept in CS?**
Is it "part of how any computer would work" or just a technical implementation in human-developed programming languages?

# Answer
> 1 votes
Escaping characters is part of an abstraction, most commonly pertaining to programming languages. Computer architectures, specifically at the sub-ISA level, don't know anything about it.

# Answer
> 1 votes
Yes, escaping is used in various contexts in CS. It is one possible solution that is used to address a particular problem. It's not something that would necessarily be part of "how any computer would work", and it's not the only possible solution; there are other ways to allow inclusion of quotes inside a quoted string without using escaping.

For more, see https://en.wikipedia.org/wiki/Escape\_character and https://en.wikipedia.org/wiki/Delimiter#Delimiter\_collision.

---
Tags: context-sensitive
---


# Question
Title: Are C standard library functions considered part of C programming language
Do we consider functions like printf part of C language even if it's not a keyword in it.

# Answer
The “C programming language“ is defined by a document that defines the syntax and the semantics of programs, *and* the C standard library. So both are part of the “C programming language”.

However, in CS the term “language” is used in a different way, as a set of strings. You can define a language based purely on the syntax In the C Standard document - that allows you to distinguish between strings that are formally in the language and those that are not, but you still have no clue what a program would do.

You can also incorporate some semantic rules, so that for example int a\[-10\] or int i = "String" are not considered to be part of the language.
> 4 votes

# Answer
Yes, absolutely.

For a start, they are the same document. The C programming language standard incorporates the standard library.

But even more than this, a C compiler is allowed to generate calls to the C standard library. This is obvious in the case of C++ (e.g. `std::unexpected`), but even in C, a compiler is free to compile a large struct assignment as a call to `memcpy` if it wants to. Most C compilers have a way to turn this off.
> 2 votes

---
Tags: programming-languages, c
---


# Question
Title: how to deal with mismatched tag bits in cache
I was reading a textbook which describe general organization of cache as:

Then an exercise is, given `m=32`, `C = 1024`, `B = 8`,`E = 4`, `S = 32`, so `s = 5`, `b = 3`, therefore `t = 32-5-3 = 24`

I am a little bit confused here, since `E = 4`, we only need 2 bits to differentiate it, so `t` should be 2, if `t` is 24, isn't that we waste 22 bits?

# Answer
For every cache set, there are $2^t$ blocks that can *potentially* be stored in there. However, only $E$ of them are *actually* stored at any particular time - typically, these would be the "most recently used" ones.

Incidentally, the whole reason for storing the tags themselves inside the cache is to be able to tell *which ones* are currently cached. The block's tag is not the "index" of a cache line, it's a $t$-bit identifier which is literally *compared* against every tag in the set in order to check whether this block is available or not.
> 0 votes

---
Tags: cache
---


# Question
Title: How to know if time complexity is O(n+m) or O(n*m)
I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n\*m

Is the time complexity of the following algo **O(n+m) or O(n\*m)**

Can you please point me to a resource that can give some sample examples of code patterns for different variations of time complexity?

For example:

```
for(String str : strs) {
   char[] charArray = str.toCharArray();
   Array.sort(charArray); //ignoring the TC of this one, which would be nLogn in java
   System.out.println("sorted: "+ new String(charArray));
}

```

# Answer
> 0 votes
Read The Algorithm Design Manual.

For this specific question, refer **Section 2.5**.

Basically you need to count the number of atomic operations your algorithm is performing.

---
Tags: algorithms, time-complexity, asymptotics, big-o-notation
---


# Question
Title: Multi-dimensional Knapsack with Minimum Value constraints for Dimensions
In MDK, we have a vector $W = \\{W\_1, W\_2, ..., W\_d\\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.

I want to add a conditional constraint: $V = {V\_1, V\_2, ..., V\_d}$, where each $i$-th dimension in the knapsack must have a value sum greater than threshold $V\_i$. I am not so much concerned with the total value sum.

I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem *harder* than MKD and therefore is NP-hard. But clearly this doesn't constitute a formal proof.

# Answer
> 0 votes
Your intuition is right on. If I understand correctly, when $V\_1=\cdots=V\_d=0$, then your problem becomes exactly the ordinary knapsack problem. So, the knapsack problem is a special case of your problem. That means that your problem is at least as hard as the knapsack problem, i.e., your problem is NP-hard.

You can prove this formally by exhibiting a reduction that converts a knapsack problem to an instance of your problem by setting $V\_1=\cdots=V\_d=0$; thus any algorithm that can solve your problem can be used to solve the knapsack problem, too.

---
Tags: np-complete, np-hard, partitions, subset-sum
---


# Question
Title: Validity of Algorithm for Testing Two Floating Point Numbers
This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I would like feedback as to what might be wrong with it.

The idea is to take the quotient of two floating point numbers and compare it to one. This eliminates the difficulty of choosing a value for epsilon. I have tested it extensively and am happy with the results. Here is a sample implementation in Java.

public class DoubleEquals
{
    public static final double  EPSILON = 1e-14;

    public static boolean equals( double param1, double param2 )
    {
        // Accounts for 0, +/-INFINITY;
        // if both values are NaN the result will be false
        boolean result  = param1 == param2;
        if ( !result )
        {
            double quot = param1 / param2;
            result = quot > 0 && (1 - quot) < EPSILON;
        }

        return result;
    }
}
```

# Answer
> 2 votes
There is one method to compare floating point numbers for equality, which is both very simple and correct: You use the equality (==) operator.

There is another method to compare whether floating point numbers are identical, which unlike the equality operator would find that -0 and +0 are not the same, and that NaNs with the same bit pattern are the same: Use memcmp. (Don't do this if your compiler stores 80 bit long double into 128 bits).

What you are talking about is the question: "Are these two numbers so close together that their difference could be due to rounding errors alone", and another question would be "Are these two numbers so close together that we don't care that they are different".

Swift has decided to put an operator for the latter into its standard library. This considers floating numbers with an n bit mantissa "as good as equal" if the difference is at most the last n/2 bits.

So first don't call your function "equals", because that is a lie. Call it "almostEqual" or something like that. Then make sure that it returns true without failure whenever x == y, that almostEqual (x, y) == almostEqual (y, x) for all pairs x, y, and that it returns the same result if you scale x, y both by the same power of two (unless this produces overflow or underflow).

Be aware that you cannot guarantee that almostEqual(x,y) and almostEqual(y,z) implies almostEqual(x,z). This also implies that you cannot make it compatible with any hash function.

# Answer
> 0 votes
That solution would be improved by ditching the fixed epsilon in favor of 1 or 2 ULPs. See the Java docs for:

public static double ulp(double d)

A second suggestion: implement a single precision version and test with double to convince yourself the algorithm is valid.

---
Tags: floating-point, numerical-algorithms, numerical-analysis
---


# Question
Title: What programming language should I use to run physics simulations of CO2 being absorbed by different materials?
I want to model the absorption of CO2 with multiple different materials such as cement, limestone, wood, etc? I know Matlab is capable of these types of physics simulation according to this research paper: Research Paper, however, I am not sure if Python or another programming language could complete this task easier.

# Answer
> 1 votes
That depends on a lot of factors, mostly on available software for the task (you *don't* want to do the whole job yourself, if it is already done, or there are pieces you can combine with little effort, use that), in second line on how detailed your model (and it's computing requirements) is might force the use of inconvenient but efficient languages/packages.

This is probably a question better asked elsewhere, perhaps on a physics or chemistry forum (for the modelling aspects, and possibly for software alternatives in common use), or (given much more detailed requirements and specifications) on a forum on programming.

# Answer
> 1 votes
I used to work on software that did something very similar, on geological scales (think carbon sequestration). My advice is very similar to that of vonbrand.

As others have noted, we don't really do programming language recommendations here. This group also isn't the main source of experts on this kind of programming; that would be scicomp.SE.

But don't just post your question as-is there, either. Do your homework first.

You want to consider how you are going to model the materials (1D, 2D, or 3D? regular grid? simplicial complex?) and the equations that you are going to solve (presumably involving some elliptic or parabolic PDEs) first. Then consider what sorts of techniques might solve those equations. Then look at what libraries are available.

For example, algebraic multigrid methods are very popular for diffusion-type equations that arise from physical systems, but you definitely wouldn't want to write one by yourself. There are some good ones available (MATLAB probably has one, and I think LLNL open sourced theirs). Also look around on sources like GAMS and see what's available.

---
Tags: programming-languages, python
---


# Question
Title: Correct application of the CFL Pumping Lemma
I came across this question about showing that the language $L = \\{w \epsilon \\{a, b, c\\}^\*: n\_a(w) + n\_b(w) = n\_c(w)\\}$ is context-free but not linear in the book by Peter Linz. That is easily doable by the separate pumping lemma for linear languages (as given in Linz's book), but my question is different.

Evidently this is a CFL, and a pushdown automaton can be constructed for it. But if I apply the pumping lemma for CFLs, I find that I'm able to pump strings that don't belong to the language, which would mean that the language is not a CFL. Clearly I'm doing something wrong.

Going by the "game-like" format given in Linz, say you pick $w = a^mb^mc^{2m}$, $|w| \ge m$. The adversary can choose a number of decompositions $w = uvxyz$, they can look like -:

* $v = a^k, y = a^l$: The case where $|vxy|$ is contained within the $a$'s of the string. Pump $i = 0$, and then $w\_0 = a^{m – (k + l)}b^mc^{2m}$ cannot be in the language since the equality no longer holds.
* $v = a^k, y = b^l$: The case where $v$ is in the $a$ section, $x$ spans across the $a$'s and $b$'s, and $y$ is in the $b$ section. Again, pump $i = 0$. $w\_0 = a^{m – k}b^{m – l}c^{2m}$ cannot be in the language.

There are more cases like these. Where am I going wrong in the application of the CFL PL?

# Answer
The pumping lemma for CFL states that if $L$ is a CFL, there exists a constant $N \ge 1$ such that for all $\omega \in L$ with $\lvert \omega \rvert \ge N$ there is a division $\sigma = u v w x y$ with $\lvert v w x \rvert \le N$ and $v x \ne \varepsilon$ such that $u v^k w x^k y \in L$ for all $k \ge 0$.

(The pumping lemma for regular languages is similar, the discussion below applies with minor changes).

You want to prove by contradiction that $L$ is not a CFL. So you assume $L$ is a CFL, and get a contradiction to the lemma. This means, in detail:

* As $L$ is a CFL, it satisfies the lemma. In particular, there is a constant $N$ such that...
* As the lemma states *all* long strings in $L$ can be divided, you are free to pick one that is easy to work with.
* The lemma states there is *some* division of $\omega$ such that.... for *all* $k \ge 0$...; to contradict the lemma you have to prove *no* division works. In practice, you take a given division of your $\omega$ (*any* division) and for it pick some $k$ for it that doesn't give a string in the language. You might need to divide this into cases.

What happens for strings that don't belong to the language, or are shorter than $N$, is completely irrelevant. It might be that some strings can be pumped, that some values of $k$ work for all strings, ... What is crucial is that for *one* string $\omega$ (the one you picked) *no* division works with *one* value of $k$ (again, the one you picked). As the lemma asserts it works for *all* long enough strings, with *some* division for *all* $k$, one counterexample is enough. Infinite examples prove nothing.
> 1 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Remove vertices until no edges are left

text:
# Question
Title: Remove vertices until no edges are left
Given an undirected graph G(V,E), find the minimum number of vertices to remove so that the Edge Set of the graph becomes empty.

In other words: If we remove one vertex we remove that vertex along with all edges connected to that vertex. Find the minimum number of vertices to remove so that there are no edges left in G after their removal.

# Answer
It sounds like you found the answer yourself, you are describing Vertex Cover, which in many ways are very similar to Independent Set, both problems are NP-complete.

The relation to Independent Set is that in a graph $G = (V,E)$, a set $S$ is a minimal vertex cover if and only if $V \setminus S$ is a maximal independent set.

If you know that Independent Set is NP-complete, then it follows that Vertex Cover is NP-complete too.

In other words, you are also looking for a maximum Independent Set.

**Vertex cover**. Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at most $k$ such that all edges in $G$ are incident to a vertex in $S$?

**Independent set**. Given a graph $G = (V,E)$ and an integer $k$, does there exist a set $S \subseteq V$ of size at least $k$ such that the *induced graph* $G\[S\]$ has no edges?
> 3 votes

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the hashtable)

# Answer
> 1 votes
Assume you have strings that you hash to a 64 bit hashcode. Since the number of possible strings is unlimited, it is guaranteed possible to have n strings that all have the same hashcode. Think about what your hashtable will do in that case.

---
Tags: time-complexity, asymptotics, arrays, hash, big-o-notation
---


# Question
Title: what is the relevance of computability when applying diagonallization?
When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter?

Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?

Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?

Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable? Something seems wrong here.

In general, what are the catches when doing diagonalization pertaining to computability?

# Answer
There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove:

* that there is no surjection from a set to its powerset
* that the real numbers cannot be enumerated
* that the computable real numbers cannot be computably enumerated
* that the Halting oracle does not exist
* etc.

In its most general form it is known as Lawvere's fixed-point theorem.

You ask what happens if you diagonalize against the rational numbers. You did not specify in what form the rationals are given, I am assuming you mean their decimal expansions. The diagonalization will produce a real number which is not a member of the enumeration (this real may be rational or irrational, depending on what enumeration you started with). If you start with a non-computable enumeration, the result may be non-computable. If you start with a computable enumeration, you will get a computable result, because diagonalization preserves computability.

Likewise, if you take a computable enumeration of computable real numbers (given as infinite sequences of digits), the result of diagonalization will be a computable real number which is not a member of the starting enumeration.
> 5 votes

# Answer
I am not sure how to answer the general question, but for the specific ones:

> Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?

Why not just an irrational number?

> Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?

For the set of all computable numbers yes.

> Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable?

It's clearly computable thus proving you can't have a computable enumeration of all computable real numbers.
> 2 votes

---
Tags: computability, proof-techniques
---


# Question
Title: 2d cellular automata Wolfram binary codes
This is a similar question to How 2d cellular automata rules works? However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular automata forms: https://www.wolframscience.com/nks/p173--cellular-automata/ I cannot find any reference anywhere that explains how to change between a real number and a growth rule. In 1d, the situation is well documented, such as here: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html but in 2d the exact mapping of bits is nowhere to be found. I'd really like to make a program, so that I can for instance enter the number 465 and it will draw the pattern 465 from the Wolfram book. The other stack exchange answer I linked to above provides a possible binary mapping, however the method given there does not produce the same numbers as in the Wolfram reference. The binary value of 465 is 111010001 which does not help me at all. This particular shape is based on adding a cell when exactly one neighbor is currently occupied, so shouldn't we expect to have 4 1's in a row, one for each of the four neighbors? And to make this even more confusing, the last two digits seem to be swapped from the description given on the Wolfram page itself... It seems clear from the other Stack Overflow answer that there is not just one possible binary mapping but many, however given that there already exists a guide with pictures referenced by rule numbers I would really like to actually be able to use those specific rule numbers. Thanks.

# Answer
> 2 votes
The description given on the page you linked to is correct:

> "In each case the base 2 digit sequence for the code number specifies the rule as follows. The last digit specifies what color the center cell should be if all its neighbors were white on the previous step, and it too was white. The second-to-last digit specifies what happens if all the neighbors are white, but the center cell itself is black. And each earlier digit then specifies what should happen if progressively more neighbors are black. (Compare page 60.)"

What you might be missing is that, if the rule number is odd, the empty lattice is unstable since white cells surrounded by other white cells will spontaneously turn black. Specifically, any rules whose number is congruent to 1 modulo 4 (i.e. whose binary form ends in 01), like 465, are "strobing", i.e. the empty lattice will alternate between all white and all black in each successive generation.

In particular, this means that rule 465 *cannot* correspond to "adding a cell when exactly one neighbor is currently occupied". (That would presumably be rule 686, or 1010101110 in binary.)

Instead, as you correctly note, 465 equals 111010001 in binary. Written in five groups of two bits each, that gives 01-11-01-00-01. In each of these groups the rightmost bit in group $k$ (numbered right-to-left from 0 to 4) is 1 if a white cell with $k$ black neighbors will turn black in the next generation, and the leftmost bit is 1 if a black cells with $k$ black neighbors will stay black.

This means that, under this rule, a white cell will turn black if it has 0, 2, 3 or 4 black neighbors (since the rightmost bit is 1 in groups 0, 2, 3 and 4 counting from the right) and a black cell will stay black if it has exactly 3 black neighbors (since the leftmost bit is 1 only in group 3).

And indeed, simulating this rule for 22 generations, starting from one black pixel on a white background, produces an image matching the one on the linked page.

---

Ps. It turns out that rule 465 is the "strobing equivalent" of the state-symmetric rule 558 = 010001011102, which differs from rule 686 by exactly one bit and can be described as "add a cell when exactly one neighbor is occupied, remove a cell when exactly one neighbor is empty".

Started from a single cell, it seems that rules 558 and 686 evolve identically, since from this starting point they apparently never generate a live cell with exactly three live neighbors. Thus, on even-numbered generations, the strobing rule 465 also looks identical to both of them.

---
Tags: binary, cellular-automata
---


# Question
Title: An efficient way of calculating ((p*q)) where p and q are prime
Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $q-1$?

Obviously, if $p$ and $q$ do not equal two, $p-1$ and $q-1$ are even and consequently their prime factorization is entirely different from the prime factorization of $p$ and $q$. Therefore I assume that no such shortcut exists.

Do I overlook something?

# Answer
> 2 votes
No, not efficiently, not in general. Suppose $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are prime. Then factoring $pq$ is believed to be hard. (Indeed, these primes are known as safe primes, and factoring a product of two safe primes is believed to be hard.) However we have

$$\varphi(\varphi(pq))=\varphi(4p'q')=2\varphi(p')\varphi(q')=2(p'-1)(q'-1).$$

If you could compute $\varphi(\varphi(pq))$ from $pq$ efficiently for $p,q$ of this form, then you could factor $pq$ efficiently for $p,q$ of this form. The reduction works as follows. Consider the quadratic function $f$ given by

$$f(x)=(x-p')(x-q')=x^2 -(p'+q') + p'q'.$$

We can compute the coefficients of $f$, as

$$p'+q'=\[pq-2\varphi(\varphi(pq))+3\]/4$$ $$p'q'=\[pq+2\varphi(\varphi(pq))-5\]/8$$

so you can use the quadratic formula to solve for the roots of $f$ and recover $p',q'$. From this the factorization of $pq$ can be recovered.

So, no, you are not overlooking anything. There is likely no efficient way to compute $\varphi(\varphi(pq))$ for arbitrary numbers $pq$ (unless factoring is easy).

---
Tags: discrete-mathematics
---


# Question
Title: Is "Solving two-variable quadratic polynomials over the Integers" is an NP-Complete Problem?
On this Wikipedia article, they claim that given $A, B, C \geq 0, \\; \in \mathbb{Z}$, deciding whether there exist $x, \\,y \geq 0, \\, \in \mathbb{Z}$ such that $Ax^2+By-C=0$ is NP-complete?

Given by how easy I can solve some (with nothing but Wolfram), it doesn't seem right. I'm sure it's either written incorrectly or I'm just misunderstanding something.

# Answer
> 8 votes
As you noted, solving that Diophantine equation is not complicated, mathematically.

All is needed is to find the necessary remainders $r$ of $x$ modulo $B$ such that $Ax^2-C$ is a multiple of $B$, then all integer solutions are of the form $x=Bn+r$ and $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.

One way to find the remainders $r$ is to

1. factor $B=\prod\_i q\_i^{a\_i}$, where $q\_i$ are different primes,
2. solve the congruences $Ax^2-C\equiv 0\pmod{q\_i}$, which in the worst case have two solutions $\pm t\_i$,
3. lift these solutions to solutions $\pm\theta\_i$ of $Ax^2-C\equiv 0\pmod{q\_i^{a\_i}}$ and
4. glue these solutions, using the Chinese Remainder Theorem to get a solution of $Ax^2-C\equiv0\pmod{B}$. Note all the $\pm$ choices.

Factoring $B$ is possibly hard, but maybe it isn't. My **outdated** knowledge is that nobody knows. Also maybe it is also possible to find the remainders $r$ without factoring $B$. What the proof that I saw exploits to conclude that the problem is NP-complete is the decision that still remains to be made.

The original decision problem becomes checking if one of the choices of $\pm$ is such that the interval $x\geq0$, in other words $n\geq -r/B$, intersects (and intersection contains an integer) the interval where $n$ is such that $y\geq0$. Compared to the bit size of $(A,B,C)$ there can be many remainders $r$ to test. I will not quantify this claim. Let the proof of its NP-completeness give evidence of it.

In Moore and Mertens' *The Nature of Computation*, section 5.4.4 there is a reduction (with parts left as exercises) of the SUBSET SUM decision problem to this decision problem (let's call it QDE).

---

Let me sketch their argument just to get a taste of how the input to SUBSET SUM is encoded in the input to QDE and how the choices of $\pm$ correspond to the subsets that one can consider in SUBSET SUM. Maybe I or someone else can expand the details later.

SUBSET SUM gets a set (or maybe a multi-set) $X=\\{x\_1,x\_2,\ldots x\_n\\}\subset\mathbb{N}$ and $t\in \mathbb{N}$ and asks if there is a subset $Y\subset X$ such that the sum of its elements is $t$. If one defines $S=2t-\sum\_{k=1}^{n}x\_k$ then SUBSET SUM is equivalent to the existence of $\sigma\_i\in\\{-1,1\\}$ such that $$S=\sum\_{k=1}^{n}\sigma\_kx\_k$$

> Here we have already choices of subsets encoded as choices of $\pm$.

Taking $m$ such that $2^m\>\sum\_{k=1}^{n}x\_k$ this equation is equivalent to $$S\equiv \sum\_{k=1}^{n}\sigma\_kx\_k\pmod{2^m}$$ If we choose $q\_1,q\_2,...,q\_n$ relatively prime odd numbers (the first odd primes suffice), the Chinese Remainder theorem ensures that there are $\theta\_1,\theta\_2,\ldots,\theta\_n$ such that

$$ \begin{align} \theta\_k&\equiv x\_k\pmod{2^m}\\\ \theta\_i&\equiv0\pmod{\prod\_{k=1,k\neq i}^{n}q\_k^m}\\\ \theta\_k&\not\equiv0\pmod{q\_k} \end{align} $$

> The $\theta\_i$ will be, for the QDE problem to be created, the solutions $\theta\_i$ that we mentioned at the beginning.

The first group of these congruences imply that SUBSET SUM is equivalent to $$S\equiv \sum\_{k=1}^{n}\sigma\_k\theta\_k\pmod{2^m}\qquad\qquad(\*)$$

> Now they build the quadratic equation, which solubility is equivalent to the solubility of this congruence.

They define $H=\sum\_{k=1}^n\theta\_k$ and $K=\prod\_{k=1}^{n}q\_k^m$. Observe that any $x$ of the form $$x=\sum\_{k=1}^{n}\sigma\_k\theta\_k$$ satisfies $$H^2-x^2\equiv0\pmod{K}$$

Then, through a pair of exercises, they argue why there are choices for picking $q\_i$ and a $\lambda\_1$ large enough such that $2H\<K$, and $|t|\<H$, and ensuring that $(\*)$ has a solution **if and only if** the Quadratic Diophantine Equation

$$\underbrace{(\lambda\_12^{m+1}+K)}\_{A}x^2+\underbrace{2^{m+1}K}\_{B}y-\underbrace{(\lambda\_12^{m+1}H^2-KS^2)}\_C=0$$

has a solution $x,y\geq0$.

Notice how this equation re-writes as

$$\lambda\_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$

The choices made in the technical details are such that when there is a solution $x,y\geq0$ for this equation it is always the case that $H^2-x^2$ is already known to be a multiple of $K$ and $S^2-x^2=(S+x)(S-x)$ a multiple of $2^{m+1}$.

---
Tags: np-complete
---


# Question
Title: Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$
> In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real).
>
> Can we use this machine to sort an array in $O(n)$?

I don't know how can I approach these type of questions which have a wrong statement as given. I know if the machine also partitions the array when finding the median, we can sort the array in $O(n)$ using $T(n) = 2T(n/2) + O(\sqrt{n})$.

But the question didn't say anything about partitioning. So if we assume that it doesn't change the array in any way and just finds the median, Can we use this machine to sort the array in $O(n)$ or not?

# Answer
We don't have to merge two sorted arrays, if we can simply compute the median information and store it in an auxilliary array; by definition, a median of an array $A\[l...r\]$ is the element in $A\[(l+r)/2\]$ when $A$ is in sorted order. Given this definition, we can simply use mergesort-style divide and conquer, while keeping track of another array $A'$ with medians of subarrays of $A$; in the end, $A'$ will be the sorted version of $A$:

**Procedure** Median-Merge-Sort($A,l,r,A'$) {

1. If $r-l\<2$ then manually update $A'\[l...r\]$ and return; $\leftarrow$ Basecase.
2. Let $m:=$Median($A,l,r$); $\leftarrow$ Compute a median in $O(\sqrt{n})$-time using the oracle.
3. Let $A'\[(l+r)/2\]:=m$;
4. Median-Merge-Sort($A,l,(l+r)/2,A'$);
5. Median-Merge-Sort($A,(l+r)/2+1,r,A'$);

}

The overall running time is $T(n)=2T(n/2)+O(\sqrt{n})$, which solves to $O(n)$ using master's theorem. This also tells us we cannot have a median-finder working in $O(\sqrt{n})$ on the comparison model, otherwise we can sort in linear time, which violates the sorting lower bound on the comparison model.
> -1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, ordering
---


# Question
Title: Does P = NP in Cellular Automata of Hyperbolic Spaces?
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does `P = NP` according to these books/papers?

Some excerpts from the paper:

> It is well known that if we have binary trees at our disposal “for free”, it is possible to solve NP-problems in polynomial time, see \[14, 5\]. However, it is not immediate to implement binary tree algorithms in the pentagrid, and the goal of this section is to indicate how one can proceed.

From my understanding, the P = NP problem is looking for polynomial-time algorithms to solve complicated problems. From my cursory glance through the books and papers, it seems to suggest that he has solved the problem. What am I missing?

Here is another paper, titled *In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream*.

# Answer
> 7 votes
The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P\_T$ and $NP\_T$ from now on. The paper introduces a new theoretical computation machine $H$ that has associated classes $P\_H$ (runs in polynomial time on the hyperbolic cellular automaton) and $NP\_H$ (runs in non-deterministic polynomial time on the hyperbolic cellular automaton).

The first step in this paper is a proof that the 3SAT problem, a well known $NP\_T$-complete problem, can be solved in polynomial time on this machine, i.e. this problem lies in $P\_H$. Next, they show any polynomial time reduction on a Turing machine can be performed in polynomial time on their hyperbolic automaton. Since 3SAT is $NP\_T$-complete, any $NP\_T$ instance can be reduced to a 3SAT instance in polynomial time (on $T$ by definition, so also on $H$ by their lemma) and then be solved by solving 3SAT in poly-time, both on the hyperbolic automaton. In other words, the main result of this paper (Theorem 1) can be written as $NP\_T \subseteq P\_H$ in our notation. This does not give a solution to the P vs. NP problem, because that would need to relate the classes $NP\_T$ and $P\_T$.

Note that the authors include some remarks on the P vs. NP problem in section 4.2, where they claim their result is evidence for P$\neq$NP (!):

> A third direction consists of the new light shed on the P=NP question in the ordinary settings. As the hyperbolic space has properties which are very different from the properties of the euclidean space, in particular, it has many more directions, would not that be a hint favorable to prove that P$\neq$NP in euclidean conditions? It seems that for the last ten years the works in the field of complexity incline people to believe more in P$\neq$NP. Apparently, the present result also belongs to that trend.

---
Tags: complexity-theory, automata, p-vs-np, cellular-automata
---


# Question
Title: Why is abstraction in lambda calculus called abstraction?
The term abstraction as I understand it, is used in many different contexts, but has one essential meaning, namely that it refers to the “general properties of some class of objects that doesn’t rely on their details”. For example, abstraction in programming is e.g. interfaces that allow you to constrain a set of objects without specifying certain implementation details.

But in lambda calculus, I don’t see what “function abstraction” has to do with something like “independence of details”. It seems to me like “function application” or “argument substitution” makes more sense.

Am I missing something?

Ps. Note that I have only read an introductory chapter of a book on lambda calculus.

# Answer
> 5 votes
Abstraction in the context of lambda calculi means turning some part of a term into a variable. Let's do an example. Consider the following terms (which use a notation richer than pure lambda calculus):

* $1 + 2$
* $\sin^2(\varphi) + \cos^2(\varphi)$
* $\frac1{n + 1}t^{n + 1} + C$

They have one thing in common. They all are built from smaller terms using $+$. Now, if we want to abstract away from the details and focus on the general common property of these terms, we just turn everything that is not $+$ into variables and end up with $\lambda x.\lambda y.x + y$, a function abstraction (if that is the name your introductory text uses; I am more familiar with the name "lambda abstraction").

# Answer
> 0 votes
A key result from lambda calculus is that to perform arbitrary computation all you need are anonymous functions. These anonymous functions are called abstractions, and the way you use them is by applying them to arguments, which are also other anonymous functions. So why are they called abstractions, or in other words, what are they abstracted from? Other such functions. So it just means that functions are detached and separate from one another. In fact, the word abstract comes from latin abstractus, which literally means drawn away.

---
Tags: lambda-calculus
---


title: Semantics of E and A operators in CTL*

text:
# Question
Title: Semantics of E and A operators in CTL*
I'm referring to a book where E and A were defined in text as follows

> The formula $A \phi$ states that all the executions out of the current state satisfy property $\phi$ whereas $E\phi$ states that from the current state, there exists and execution satisfying $\phi$

And formally, they were defined as

> $\sigma, i \models E\phi $ iff there exists as $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ and $\sigma', i \models phi$ $\sigma, i \models A\phi $ iff for all $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$, we have $\sigma', i \models phi$

$\sigma(i)$ was previously defined to be the ith state of an execution $\sigma$.

Here's where my confusion lies. Doesn't $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ imply that the executions $\sigma$ and $\sigma'$ have both the same start and end state, therefore $\sigma', i \models \phi$ is same as $\sigma, i \models \phi$? That seems to be wrong.

# Answer
> 1 votes
I believe it means that $\sigma,\sigma$ should share the same prefix up to position $i$. Then the quantification ranges over all possible extensions of this prefix from state $\sigma(i) = \sigma(i)'$.

# Answer
> -1 votes
I think you misinterpret the expression $$\sigma(0) \cdots \sigma(i) = \sigma'(0) \cdots \sigma'(i')$$ and I agree that it is written in an unintuitive way.

The author means that $\sigma(i) = \sigma'(0)$ and that the final path is $$\sigma(0) \cdots \sigma(i) \\; \sigma'(0) \cdots \sigma'(i').$$

The equality ensures that the path $\sigma'$ *starts* where $\sigma$ ends.

Are you sure there isn't a prime on the $i$?

---
Tags: temporal-logic, computation-tree-logic
---


title: convergence rate of newton's method

text:
# Question
Title: convergence rate of newton's method
So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced that the speed of this algorithm can be more than quadratic, however I'm wondering when this happens, since in the demonstration used by him to explain the quadratic case, there is no evidence about the "more than quadratic"

Using Taylor and Lagrange
$f(\xi)=f(x\_n)+f'(x\_n)(\xi-x\_n)+\frac{f''(z\_n)}{2}(\xi-x\_n)^2$

$-\frac{f(x\_n)}{f'(x\_n)}=\xi-x\_n+\frac{f''(z\_n)}{2f'(x\_n)}(\xi-x\_n)^2$

$x\_{n+1}-x\_n=\xi-x\_n+\frac{f''(z\_n)}{2f'(x\_n)}(\xi-x\_n)^2$

$e\_{n+1}=\left|x\_{n+1}-\xi\right|=c\_ne\_n^2 \quad \text{with} \quad c\_n=\frac{1}{2}\frac{\left|f''(z\_n)\right|}{\left|f'(x\_n)\right|}$

Can someone please tell me when (example) the order of the convergence is cubic, and why?=

# Answer
Since you asked specifically about cubic, consider $f(x)=x+x^3$.

The Newton iteration would be $$x\_{n+1}=x\_n-\frac{f(x\_n)}{f'(x\_n)}=x\_n-\frac{x\_n+x\_n^3}{1+3x\_n^2}=\frac{2x\_n^3}{1+3x\_n^2}$$

It converges to the root $x=0$. So, for $1-3|x\_n|^2\>1/2$,

$$\epsilon\_{n+1}=|x\_{n+1}-0|=\frac{2|x\_n|^3}{|1+3x\_n^2|}\leq \frac{2|x\_n|^3}{1-3|x\_n|^2}\leq 4|x\_n-0|^3=4\epsilon\_n^3$$
> 2 votes

# Answer
Look at your expression for the error, and extend the base series one more term: If $f''(\xi) = 0$, the convergence is (at least) cubic.
> 1 votes

---
Tags: numerical-algorithms
---


# Question
Title: Communication between hardware components
We know that each component has different frequencies, but what happens when a fast component directly comunicates with a slow one?

# Answer
I think what you're asking is how two machines or components, which run at different clock speeds/phases, can communicate. The short answer is that the receiver synchronises to the sender.

In low-speed communication channels (e.g. I²C), this can be achieved with an explicit clock line. Essentially, the sender has a separate wire that is the transmission clock. This is also generally the way that things work with parallel busses (e.g. where you send 8 bits over 8 wires plus a clock).

This doesn't work as well at high speed, because a small difference in the lengths of two wires can cause signals to arrive at different times. It also doesn't work over channels where there you don't or can't have more than one "wire", such as radio.

If you only have one "signal" (be it a single pair of wires, single radio frequency, or what have you), you are in the domain of line coding.

In that case, the receiver can synchronise by looking for edges in the source signal. There is an agreed-upon clock rate, which neither end can reproduce perfectly. But if the sender sends the message `00101001`, for example, every time the bit flips from `0` to `1` or `1` to `0`, that is something that the receiver can synchronise to.

Exactly how to synchronise clocks is a question for electronics engineers, who can explain techniques like phase-locked loops to you better than I can. It's a little subtle because the receiver can detect edges, but ideally wants to take its sample from the half-way point between the leading edge and the trailing edge, so there has to be some kind of delay involved.

But what if there are no edges? If the transmitter wants to send a whole bunch of zeroes, how does the receiver synchronise then?

The way around this is to design a code which does have transitions. RS-232, for example, specifies that each byte begins with a start bit, and ends with one or more stop bits, and there is a zero between the two frames, so every byte effectively has the bits "101" between bytes.

Medium-speed channels where retransmission is not an option (e.g. digital broadcast, satellite/spacecraft communication, or recording media such as optical disks) will often use error-correcting codes to achieve the same effect. Not only do you get error correction, the extra redundancy gives plenty of opportunity for clock synchronisation.

And then, you get into physical problems to do with the fact that you're communicating over physical wires or physical radio signals.

Over wires, for example, it's desirable to design a code with approximately the same number of 0 bits and 1 bits, a property known as DC balance. Real pairs of wires will act like a capacitor at high speed, and so if you have (say) more 1's than 0's, they will retain a charge and hence resist sending 1's. An example of a code designed for this is 8b/10b, which is used in a lot of modern high-speed serial communications such as HDMI, SATA, Gigabit Ethernet, and USB 3.0.

See this question from electronics.SE for further details.

Radio communication (e.g. Wi-Fi and cellular telephony) has its own problems that I can't really cover here, even if I understood it all. You have to protect against the Doppler effect, destructive interference caused by reflections, and so on.
> 2 votes

# Answer
> what happens when a fast component directly comunicates with a slow one?

They must both be able to communicate and the same speed, regardless if it an async or sync type channel.

Consider the channel capacity as the block rate on average or burst mode. In any event each side must either acknowledge ready or not (eg DTR DSR) or (ACK NAK) unless it is something of lower value then it may not and just stream it and hope the recipient can keep up without errors E.g. streaming Video, UDP.

I have a 1Gbps ethernet connection to router, but only 100 /5 Mbps modem so the channel capacity is limited by the thruput limitations of the weakest channel and host which is often somewhere on the web.

A slow firestick might be able to stream HDMI video at a Gbps video speed yet never be able to process video internally at that speed.

## Buffers

To enhance byte thruput, the penalty is latency but the benefit is slack time to load each word. E.g. DS1 digital audio might have 1 byte buffer for low fixed latency per repeater even if MUX’d from 1.544 Mbps to OC96. Whereas a UART usually has 16 byte buffer for Rx to handle interrupts without buffer over-run flag being set.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: 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 output of that perceptron to completely flip, say from 0 to 1..... That makes it difficult to see how to gradually modify the weights and biases so that the network gets closer to the desired behaviour. **Perhaps there's some clever way of getting around this problem.** But it's not immediately obvious how we can get a network of perceptrons to learn. **We can overcome this problem by introducing a new type of artificial neuron called a sigmoid neuron.** Sigmoid neurons are similar to perceptrons, but modified so that small changes in their weights and bias cause only a small change in their output. *That's the crucial fact which will allow a network of sigmoid neurons to learn.*
>
> Just like a perceptron, the sigmoid neuron has weights for each input, $w1,w2,…$, and an overall bias, b. But the output is not 0 or 1. Instead, it's $σ(w⋅x+b)$, where σ is called the sigmoid function and is defined by: $σ(z)≡\frac{1}{1+e^{−z}}$.
>
> If σ had in fact been a step function, then the sigmoid neuron would be a perceptron, since the output would be 1 or 0 depending on whether w⋅x+b was positive or negative. By using the actual σ function we get, as already implied above, a smoothed out perceptron. The smoothness of σ means that small changes Δwj in the weights and Δb in the bias will produce a small change Δoutput in the output from the neuron. In fact, calculus tells us that Δoutput is well approximated by:
>
> $$Δoutput≈∑\_j\frac{∂output}{∂w\_j}Δw\_j+\frac{∂output}{∂b}Δb$$
>
> *Don't panic if you're not comfortable with partial derivatives!*
>
> **Δoutput is a linear function of the changes $Δw\_j$ and $Δb$ in the weights and bias.** This linearity makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output. So while sigmoid neurons have much of the same qualitative behaviour as perceptrons, they make it much easier to figure out how changing the weights and biases will change the output.
>
> In fact, later in the book we will occasionally consider neurons where the output is f(w⋅x+b) for some other activation function f(⋅). The main thing that changes when we use a different activation function is that the particular values for the partial derivatives in Equation (5) change. It turns out that when we compute those partial derivatives later, **using σ will simplify the algebra**, simply because exponentials have lovely properties when differentiated. In any case, σ is commonly-used in work on neural nets, and is the activation function we'll use most often in this book. \[END\]

The first part of my question is, how did they know to pick this "sigmoid shaped" function/equation in the first place? How did they know to pick this one over every other curved or not-curved function? Is that just standard practice for these types of problems in Math class? If I were to try and explain why the sigmoid function was chosen, I would say "because it means you can make small changes to the input correspond to small changes to the output." But how? I don't follow the partial derivative math and don't have a background in partial derivatives (and neither does my audience). Knowing why and how th esigma function was chosen would help demystify why neural networks work.

*Unfortunately the partial derivatives weren't explained (maybe they will be somewhere else).*

The second part of my question is, How is $Δoutput$ a "linear function"? Why not just a flat slope instead of the sigmoid shape. Why does it have to be so fancy? How does "using σ will simplify the algebra"? Where can I find research papers on the original thinking behind this, or if you know the answer then how can you explain why using sigma will simplify the algebra? This seems like an important part of the explanation on why we are using sigma functions in the first place, so having a laymans explanation would really help.

# Answer
# Answer to first part

The function in the question is called the logistic function. Sometimes it is also called "the" sigmoid function, but some authors use sigmoid to just mean any s-shaped function.

There are a wide variety of activation functions used in practice in neural networks, sigmoid and otherwise. The logistic function is one of the more common ones, because both the logistic function and its derivative are defined for all real inputs, can be written as short expressions in terms of elementary functions, and can be computed efficiently using standard library functions in most programming languages. (This is unlike the step function used as the activation function for a classic perceptron—the derivative of the step function is undefined at the discontinuity.) Another widely-used activation function that has these properties is $\tanh$. There is really no strong reason to prefer one over the other when initially presenting sigmoid neurons. You can pretty much pick any function you learn how to differentiate in a Calculus 1 class and that has a sigmoid shape with asymptotes at $\pm\infty$. They have slightly different performance characteristics in training, but that is not very relevant for an initial explanation.

It is unfortunately very difficult to explain backpropagation without understanding partial derivatives, since backpropagation is literally just gradient descent where the gradient is computed by automatic differentiation. I would recommend watching 3Blue1Brown's excellent series of YouTube videos on how backpropagation works: part 1, part 2, and especially part 3 and part 4.

You mention an audience in the question. If you are going to be presenting this material, I would seriously consider referring your audience to the 4 videos linked above, at least as references. They certainly provide a better explanation than I could give in a lecture.

# Answer to second part

The reason for not using a linear function is that a neural network with all linear activation functions is a linear combination of linear functions, and is therefore itself a linear function. So using a linear activation function misses the entire point of training a neural network; you could get the same result faster by doing a least-squares fit of a linear function to the data.

To oversimplify only slightly: a neural network with a linear activation function is just the "fit trendline" feature in Excel.

By contrast, there is a universal approximation theorem that says that, for sufficiently nice *nonlinear* activation functions, any function can be approximated well by using enough neurons.

The universal approximation theorem was not discovered for many years after when neural networks were first invented, so it was not a motivating factor in their invention. Early neural network research was mainly inspired by biological neurons (the kind in your brain) and control theory.

While the universal approximation theorem says that a *sufficently large* neural network has the *potential* to approximate any function well, the actual reason why the standard method of training neural networks (stochastic gradient descent backpropagation) performs so well in practice is still poorly understood and an active area of research.
> 5 votes

---
Tags: neural-networks, mathematical-foundations
---