Functor laws and natural transformations in Haskell

I'm having a little trouble exactly what question you're asking, but I think it might help if we went through the connection between homomorphisms and free theorems.

But here's the executive summary of what I think you want to know:

The fmap laws are not redundant when you have free theorems. On the contrary, you need fmap to state the free theorem for any function that involves a Haskell Functor.
Specifically, if a function has the type of a natural transformation, its free theorem is the naturality condition expressed in terms of fmap.

First off, let's get a bit of intuition about what the parametricity theorem states. An informal way of stating it is this: For any function which has a "forall" in its type, that "forall" really does mean "for all types". The function cannot make any assumptions whatsoever about the type.

To explain what this means when we involve types with an algebra, we need the language of homomorphisms. So let's review what a homomorphism is. (Sorry if this is revision for you, but I think it's worth going through this.)

Let's consider monoids. A monoid is a set $M$ along with two operations $0_M$ and $+_M$ which obeys the laws:

$$\forall x \in M, x +_M 0_M = 0_M +_M x = x$$
$$\forall x,y,z \in M, x +_M (y +_M z) = (x +_M y) +_M z$$

A monoid homomorphism is a function between two monoids $f : M \rightarrow N$ which "respects" the two operations:

$$f(0_M) = 0_M$$
$$f(x +_M y) = f(x) +_N f(y)$$

In Haskell, we might represent monoids as a type class:

class Monoid m where
    mzero :: m
    mplus :: m -> m -> m

If M1 and M2 are instances of Monoid, a Monoid homomorphism f :: M1 -> M2 must obey the laws:

f mzero = mzero
f (mplus x y) = mplus (f x) (f y)

Remember that the monoid operations on the left-hand side of these "laws" are different from the monoid operations on the right-hand side. The left-hand side are the operations for M1 and the right-hand side are the operations for M2.

Now consider the following typeclass (which isn't the same as Haskell's Ord typeclass, but is close enough):

class Ordered a where
    lessThan :: a -> a -> Bool

Again, there are laws that any reasonable "less than" operator must obey. But what I want to concentrate on here is the Bool part.

What does it mean for a function to "respect" this algebra? It essentially means that the Bool has to be the same. That is, if A and B are both instances of Ordered, an Ordered homomorphism f :: A -> B must obey the law:

lessThan (f x) (f y) = lessThan x y

Think about what this means semantically: this law is stating that for any two elements, f doesn't change their relative ordering. That is what it means for f to "respect" the ordering algebra.

OK, now back to the parametricity theorem. The free theorem for the function:

sortBy :: forall a. (a -> a -> Bool) -> [a] -> [a]

is this, written out in a slightly fuller form:

for all f :: A -> B,
If lt :: A -> A -> Bool is a function such that
    for all x, y :: A, lt x y = lt (f x) (f y)
Then
    for all xs :: [A], sortBy lt . map f = map f . sortBy lt

We can say the same thing with type classes:

sort :: forall a. Ordered a => [a] -> [a]

The free theorem here is, essentially:

for all f :: A -> B,
if f is an Ordered homomorphism
then sort . map f = map f . sort

Which is, of course, just that f doesn't change the ordering of elements, then performing the substitution map f and then sorting is the same thing as sorting them performing the substitution.

The complication with Functor is that it's a constructor class, so the intuition about what a Functor homomorphism should be is a little less clear. But let's step back a moment and talk about category homomorphisms.

Categories are algebras just like any other. A category has two operations, $1$ and $\circ$, which satisfies the laws that you know and love. So a category homomorphism $F$ is a function which satisfies:

$$F(\hbox{id}) = \hbox{id}$$
$$F(g \circ f) = F(g) \circ F(f)$$

If you think of a functor between the "Haskell category" (objects are Haskell types, morphisms are Haskell functions) and a Haskell Functor category (objects are Haskell functors and morphisms are Haskell functions between these objects), then this is exactly the Functor laws.

fmap id = id
fmap (g . f) = fmap g . fmap f

Now here's the important part: The fmap operation is the homomorphism precondition that you need for free theorems involving Functor.

Consider, for example, something with the same type as fmap but isn't necessarily fmap:

instance Functor F where ...

somethingLikeFmap :: forall a b. (a -> b) -> (F a -> F b)

The free theorem for this function is:

if q . f = g . p,
then somethingLikeFmap q . fmap f = fmap g . somethingLikeFmap p

From this you can conclude a bunch of interesting things, such as that if somethingLikeFmap id = id then fmap = somethingLikeFmap. In particular, somethingLikeFmap can be characterised entirely by what it does with id.

This has to be the case. The parametricity theorem, which generates these free theorems, states the "forall" in a parametric type really does mean "for all types".

If the functor is a container-like type, for example, the function cannot make any decision about what to do based on the value of an element in the container. But it could do anything with the structure of the container which doesn't depend on the values in it.

somethingLikeMap1 f = reverse . map f
somethingLikeMap2 f = map f . tail
somethingLikeMap3 f = []

If a polymorphic function does has a way to make decisions based on the values (e.g. lessThan in the case of sort), then the free theorem states that this is the only way that it can make a decision about what to do, so if the mapping doesn't affect the decisions (e.g. the values returned by lessThan), then it doesn't affect the operation of the polymorphic function (e.g what sort does).

So this is why the fmap laws are not redundant with respect to free theorems: they define the homomorphism between the Haskell category and the (endo-) functor category that you need to state the free theorems.

Finally, what is the free theorem of a function which has the type of a natural transformation?

instance Functor F where ...
instance Functor G where ...

eta :: forall a. F a -> G a

It is:

fmap_G f . eta = eta . fmap_F f

This is exactly the naturality condition. This a good way to think about what's so "natural" about a natural transformation.


What is meant when we say that divergence is the only side-effect of the lambda-calculus?

I think it is better to speak of computational effects than side effects, as some of them are not really on the side but rather directly in your face.

Computational effects are aspects of a program which are not just "mathematical computing", i.e., not just internal processing of data: I/O, access to mutable memory, exceptions, etc. The notion is a bit open-ended and difficult to make completely precise (because people invent new ways of computing things -- in 1970 nobody would have thought to include quantum super-position into the list of possible side-effects). Nevertheless, any sort of interaction between a program and the external environment is usually counted as a compuational effect.

Is program divergence, i.e., running forever, a side effects? In a sense it is, because it definitely is a form of "interaction" with the external environment, albeit a very annoying and useless one. Waiting forever to find out the result of a computation has several side effects, such as a high electricity bill, death of one's pets, and the thermal death of the universe. There are also deeper theoretical reasons why divergence should be counted as a side effect, but you did not explicitly ask about that.

You stated that the pure simply-typed $\lambda$-calculus has only one computational effect, namely divergence. But this is not the case! In the simply-typed $\lambda$-calculus every program terminates! You have to pass to the untyped $\lambda$-calculus to get divergence.

You also ask how to implement computational effects in $\lambda$-calculus. There are two ways:

You can extend the calculus with new primitives, for example primitive operations print, read, etc. You then have to give an operational account of what these operations do. ML-style languages do this.
You can simulate effects using the calculus. For example, instead of actually printing things, you can collect the things that would get printed in a list (suitably implemented in $\lambda$-calculus). Most effects can be simulated in such a way. In this approach your language is still pure, but your programs look like they are using computational effects. Haskell does this.


Calculate execution time from linear speedup

The term you're looking for is called parallel efficiency, which is a measure of how efficiently an algorithm uses its parallel resources. And you are correct that it is:

E = parallel speedup / p

Where p is the number of processors (or cores).

Your equation for t(c_2) is still valid, when the parallel efficiency is the same for c_1 and c_2, as it's equivalent to:

t(c_1) / c_1 = t(c_2) / c_2

A parallel efficiency greater than one is truly possible. While it is observed sometimes, this is because of NUMA effects which accompany the access to more processors / cores (i.e., more of the problem fits in caches).

Also see:
https://computing.llnl.gov/tutorials/parallel_comp


About a pre-processing step for primal-dual weighted set cover problem

The goal is to give an $O(\log n)$ approximation algorithm, starting with an algorithm that is already an $O(\log n)$ approximation algorithm, and optimizing it further. Adding the low cost elements results in an approximation ratio of $1 + O(\log n) = O(\log n)$, since the total weight of sets we add is $\beta$, which is also an upper bound on the value of the optimal solution.


How to determine the dimensions of the bias vector in a Convolutional layer (tensor flow)?

No.  The bias vector should indeed have the same dimensions as the output vector (not the dimensions of the input).  In a neural network, after summing the weights times the inputs, the bias is added pointwise, then you apply the activation function (e.g., ReLu).  The equation for a single neuron is something like

$$y = f(\sum_i c_i x_i + c_b)$$

where $x_1,\dots,x_n$ are the inputs, $c_1,\dots,c_n$ are the weights on the inputs, $c_b$ is the bias, and $f$ is the activation function.  Notice how we have one bias number per neuron, i.e., per output.  (This equation gets modified a bit for convolutional neural networks but the relevant part still remains the same: we have one bias value per output.)


Have a look at the results from this years SAT 2013 competition. Based on these results, definitely give Lingeling a try. Plingeling is the parallel variant of it.

If you don't need to prove unsatisfiability (perhaps you know the instance is satisfiable, and you just need to know an assignment making it SAT), you could try local search methods, too.


Algorithm for executing a command against a million hosts

Assuming the hosts and network are reliable, and that the cost of sending a message from any machine to any other machine is the same, then you would use some sort of broadcast tree.  For example, if the machines are all numbered 0, ..., 7, then node 0 would send to node 4, 2, and 1, node 4 would send to nodes 6, and 5.  Node 2 would send to node 3. Node 6 would send to node 7.

Generalize that to $2^n$ nodes, and the total time is $O(n)$.  So with 220 nodes, node 0 would send about 20 messages, rather than 1 million.

As you make the assumptions weaker, the problem gets increasingly more difficult.

If the cost of sending messages is different for different pairs of machines, then you would want to do some kind of minimum spanning tree based algorithm, maybe.

If you don't know anything about the network as a whole, but each node knows something about its neighbors then you might use some kind of flooding algorithm.

If the network is not reliable (links can appear and disappear) then the problem gets quite difficult.  I think there are various ways of posing the problem as a Steiner tree problem, but now you are way outside my area of expertise.


What's the difference between phi and lambda in regular expression?

You need to distinguish between regular expression syntax and its interpretation aka semantics.

"$\lambda$" is a symbol representing the set that contains only the empty string $\{\varepsilon\}$).
"$\phi$"¹ is a symbol representing the empty set of strings $\emptyset = \{\}$.

The difference becomes apparent when you compute the interpretation $i$ of a regular expression:

$i(a\lambda) = i(a) \cdot i(\lambda) = \{ a \} \cdot \{ \varepsilon \} = \{a\}$

Note: I'm deliberately using $\varepsilon$ to denote the "real" empty string outside of a regular expression. Your source probably uses $\lambda$ for both; that obscures the fact that it's used in two different ways.
$i(a\phi) = i(a) \cdot i(\phi) = \{a\} \cdot \emptyset = \emptyset$.

If you don't follow that last line, revisit the definition of the concatenation of languages:

$\qquad\displaystyle A \cdot B = \{ a \cdot b \mid a \in A, b \in B\}$.

Do they really use $\phi$?


How can you construct 3-regular graphs with minimal diameter?

The interesting case is connected 3-regular graphs (otherwise the diameter is infinite). We can simply show that if $G$ is such a graph then $D(G)=\Omega\left(\log_2|V|\right)$, where $D(G)$ denotes the diameter of the graph $G$.

Suppose $D(G)=d$. Start at an arbitrary vertex $v\in V$ and begin counting the vertices of the graph by scanning $G$ using BFS originating at $v$. In the first step you encounter 3 vertices ($v$'s neighbors). If at the $i'th$ step you encountered $k$ new vertices, then at the $i+1$ step you will encounter at most $2k$ new vertices (you have three edges to choose from, but at least one will take you back to a vertex you have already met). After at most $d$ steps you will encounter all of $G$'s vertices. This yields the following inequality:

$|V|\le 1+\sum\limits_{i=1}^{d-1}3\cdot 2^{i-1}=1+3\cdot \left(2^{d-1}-1\right)$, hence $d=\Omega\left(\log_2|V|\right)$.

You can see from the above that if $G$ is a connected d-regular graph then $D(G)=\Omega\left(\log_{d-1}G\right)$.

To construct a graph which achieves this lower bound, think about binary trees, and find a way to fix the leaves (and root) in order to achieve 3-regularity.


A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

No, what you suggest would be meaningless. The Turing reduction is also polytime. For a proof, see Theorem 3.2 in Oded Goldreich's lecture notes.


Where did the terms memory pool and memory leak come from?

Yes, Computer Science.

Back in the days of the NASA/Apollo program (and possibly before), mainframe computers had wads of memory (like as much as 256 Mwords). To support multi-tasking, a program/task running on that mainframe had to specify how much memory was required to do its job, and the system would allocate that much - if possible - out of the "memory pool". This "pool" nomenclature  comes at a time when we had motor pools, secretarial pools, labor pools... nonspecific resources of a certain class; indeed, this working memory on a mainframe was not dedicated to a specific use (there are regions of mainframe memory that are not available to "normal" programs/tasks).

As the tasks run, they are supposed to only use what they ask for, and they are required to signal the system when the memory is no longer needed. Depending on efficiency concerns, they may ask for the memory a little at a time (it's nice for other tasks that you don't grab either everything available, or more than you need). Poorly developed programs have a nasty side-effect of not returning what was allocated to them. From the system's perspective, the available memory pool is getting smaller and smaller, hence the memory "leaks out". It doesn't go anywhere, but the net effect is that a program that needs a certain amount of memory to either load or run will have to wait until a better behaved program/task returns a sufficient part of the allocation - or the memory system is restarted.


Example of reduction such that it is not many-one reduction while it is not turing reduction

A simple example would be a reduction from e.g. $SAT$ to it's complement $\overline{SAT}$, which works as follows: given a formula $\varphi$, you can decide whether $\varphi$ is satisfiable by deciding whether $\varphi\in \overline{SAT}$, and then negating the answer. This is a Turing reduction, since you use an oracle for $\overline{SAT}$ to solve $SAT$.

A similar example can be constructed for HALT and it's complement, if you want decidability, rather than complexity.


This is a classical result of Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theorem 3.3 on page 188. The idea is to use crossing sequences: you show an upper bound $O(1)$ on the size of any crossing sequence, and then use an argument of Hennie, One-tape off-line Turing machine computations, Theorem 2 on page 561, to conclude that the language accepted by the machine is regular.


Why are inversions useful in computer science?

To analyse many algorithms, in particular for the all-important sorting problem, the characteristics of permutations are important measures. For instance, the number of inversions determines the number of data movements when running insertion sort.


I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I  found no proof in my very fast look at the relevant chapter.
Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted):

$(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-deterministic because you don't know where the $WcW$ bit starts.
$W^RcW(a+b+c)^*$, where $W \in (a+b)^+$; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form $W^RcW$ and modify the accepting state to loop to itself on any of $a$, $b$ and $c$.
The trick here is that PDAs have to read input from left to right.


What memory locations will the CPU fetch instructions from with instruction length of 16bits

I too read the book. If Dr. Stallings has quoted this, the memory locations 301 and 302 must be referring to word-wise and not byte-wise locations.


Undirected graph with 12 edges and 6 vertices

You have 12 edges, so the sum of the vertex degree is 24. Then there are 6 degree-3 vertices taking away 18. Thus the best you can hope for are 3 vertices of degree 2. Thus you found the solution.


What is the most efficient way to compute factorials modulo a prime?

(This answer was initially posted by the asker jonaprieto inside the question.)

I remember Wilson's theorem, and I noticed little things:

In the above program, it is better if I write:
$$\begin{align}
(p-1)! &\equiv -1 &\pmod p\\
(p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\
(p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\
(p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\
\ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}}  &\pmod p\\
\end{align}$$

And you can find $(p-i)^{-1}$ because $\operatorname{gcd}(p, p-i) = 1$, so with the extended Euclidian algorithm you can find the value of $(p-i)^{-1}$, that is the inverse modulus.

You can view the same congruences too,  like to:
$$\begin{align*}
(p-5)! &\equiv (p-24)^{-1}&\pmod p\\
(p-4)! &\equiv (p+6)^{-1}&\pmod p\\
(p-3)! &\equiv (p-2)^{-1} &\pmod p\\
(p-2)! &\equiv 1&\pmod p\\
(p-1)! &\equiv -1&\pmod p\\
\end{align*}
$$
so, the sum is equal: $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$
and if you factorize in the beginning the factorials you get
$$ 8\cdot (-24)^{-1} \pmod p$$
And, voila, inverse modulus is more efficient than factorials.


Generating topological sequence from DAG with additional "not appearing before" constraints

Let's say the 2 nodes in question are node x and node y. If you want node x to not appear before node y, then, as Yuval Filmus mentioned in the comments, you want it to appear after y.
What does this mean?
If x is a predecessor of y, then the graph would not be valid, because by definition, a topological sort puts all predecessors before their childrens.
If x is not a predecessor of y, you could add an auxiliary edge from x to y. This ensures that x will definitely appear before y, again by definition of a topological sort.
Followup:
Adding an auxiliary edge may cause some problems, here are some possible solutions to resolve them
Shortest/longest path in weighted DAG: Just set the edge weight as 0
Shortest/longest path(number of edges used): Give all non-auxiliary edges value of 0, treat as SP/LP in weighted DAG


What is the difference between a scripting language and a normal programming language?

I think the difference has a lot more to do with the intended use of the language.

For example, Python is interpreted, and doesn't require compiling and linking, as is Prolog. I would classify both of these as programming languges.

Programming langauges are meant for writing software. They are designed to manage large projects. They can probably call programs, read files, etc., but might not be quite as good at that as a scripting language.

Scripting langauges aren't meant for large-scale software development. Their syntax, features, library, etc. are focused more around accomplishing small tasks quickly. This means they are sometimes more "hackish" than programming langauges, and might not have all of the same nice features. They're designed to make commonly performed tasks, like iterating through a bunch of files or performing sysadmin tasks, to be automated.

For example, Bash doesn't do arithmetic nicely, which would probably make writing large-scale software in it a nightmare.

As a kind of benchmark: I would never write a music player in perl, even though I probably could. Likewise, I would never try to use C++ to rename all the files in a given folder.

This line is becoming blurrier and blurrier. JavaScript, by definition a "scripting" langauge, is increasingly used to develop "web apps" which are more in the realm of software. Likewise, Python initially fit many of the traits of a scripting language but is seeing more and more sofware developed using Python as the primary platform.


Are nearly all natural numbers compressible?

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants).

Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The machine will first write the binary representation of $n$, and then use $O(1)$ states to convert it to its unary representation (that is, $1^n$); we will only describe the first phase.

The machine runs in $\log n/C$ rounds, maintaining a unary counter whose value at round $r$ is $1^r$ (after all the rounds finish, we erase the counter). At each round, we write $C$ bits of the binary representation of $n$. This is accomplished using $O(C2^C)$ states which implement adding $C$ bits (for which choice of $C$ bits), and $O(\log n/C)$ states for control (we use the unary counter to switch control to the correct state). This completes the description of the machine.

A machine with $S$ states on the binary tape alphabet has description size $O(S\log S)$. Hence we expect that the optimal answer be $O(\log n/\log\log n)$. Indeed, if we choose $C$ very carefully to be $\log (\log n/(\log\log n)^2)$, then the construction above gives a "busy beaver" machine with $O(\log n/\log\log n)$ states, which is optimal up to constants.

If the tape alphabet is allowed to grow with $n$, then $O(1)$ states suffice to output $1^n$: the alphabet will be of size $n + O(1)$, and we will use a certain cell as a counter. This construction shows that it is important to limit the tape alphabet.


To expand a bit on David's answer, you are confusing between the next two claims.

Claim 1 if $L_1,L_2$ are regular, then $L_1 \cap L_2$ is also regular.
(proof: construct the product DFA, e.g., here)

Claim 2 if $L_1$ is regular, but $L_2$ is not, then $L_1\cap L_2$ can be either regular or not-regular.
(proof: Let $L_2$ be some non-regular language. If $L_1=\Sigma^*$ then $L_1\cap L_2=L_2$ which is non-regular by its definition. On the other hand, if $L_1=\emptyset$ then $L_1\cap L_2=L_1=\emptyset$ which is regular)


Is there a model of computation based on discrete event dynamic systems?

Let's first look at what Wikipedia says:

the theory of computation is the branch of mathematics and computer science that deals with how efficiently problems can be solved on a model of computation;
a model of computation is a model which describes how a set of outputs are computed given a set of inputs; they can be classified into three categories:

Sequential models, including

Finite state machines
Pushdown automata
Turing Machines

Functional models, including

Lambda calculus
Recursive functions
Combinatory logic
Cellular automata
Abstract rewriting systems

Concurrent models, including

Kahn process networks
Petri nets
Synchronous Data Flow
Interaction nets

All of these are mathematical formalisms to model the behavior of discrete event systems.  To be more precise, for each of them, there is a whole family of related formalisms, and many more formalisms exist outside of these families, thousands or tens of thousands in all, ranging from very popular to very obscure.

You're looking for ones that are event-based. Flow-based models are often considered to be event-based: what flows in can be regarded as a stream of events. Furthermore, finite automata were conceived of as an event-based formalism: they were introduced in a memo titled ''Representation of Events in Nerve Nets and Finite Automata''. Concurrent modeling techniques (e.g. Kahn process networks, Petri nets, Communicating Sequential Processes) are often based on finite state machines or variants of that idea. Techniques based on communicating state machines operating in parallel are popular in industry. Their models consist of components passing messages, or events, or data items, to each other over channels. This is really flexible: you can use it for modeling events, or dataflow, or literal message passing, or the flow of abstract information in, let's say, some office workflow process.

You say you're looking for something other than flow-based models, something suitable for describing user interaction. I've worked with modeling technology for embedded systems that makes this distinction. It has two kinds of communication:

asynchronous: used for data flow processing or event flow processing where data or events flow in on a streams, have a bit of processing done, then flow out on another stream
synchronous: procedure calls: one party instigates communication and waits for the response, the other party responds; used for interaction where the volume of communication is low and the calling party needs a result to continue, for instance, user interaction

I think most proponents of concurrent modeling techniques will tell you they don't need to have synchronous communication in their technique because they can emulate it. For instance, this

is how you express a synchronous call in the Petri-net based process modeling tool I used to work on. As you can see, the circles represent states or conditions, but also data items, while the squares represent state transitions. Control flow and data flow are both expressed, but not distinguished within the modeling technique. But this is unusual: techniques based on communicating state machines do separate state changes (within the machines) from event/data passing (between the machines).

Furthermore, there's a movement in systems design and programming that says to avoid synchronous communication in the first place. Systems should be concurrent and event-based by design, all the waiting for replies on synchronous calls just holds up your components for no other reason than your own ineptness at design, synchronous calls are just mental laziness induced by having looked at inherently sequential systems for too long. This approach to interactive applications has gained a lot of traction in recent years.

So many people in this area will say you don't need separate modeling constructs for user interaction: a user input and output to the user are just communications, flowing on communication channels between two system components, one of which is the user. It's message passing and all you need is a message passing formalism.

An alternative to modeling I/O as messages within the system is to model inputs and outputs as properties of state transitions. For instance, this is done in Mealy machines and I/O automata. This is used for model-based testing: the expected behavior of the system is modelled using an I/O automaton and used to generate test cases that are then used to verify whether the actual system meets the specifications. This approach is really focused on interactive systems, not flow-based systems.

So there are many approaches to choose from; none of them can be said to be canonical, but approaches based on some form of state machines are the most popular, so if you'd insist on calling anything canonical, I'd say it's the state machine.


It's easiest to understand with a one-dimensional random walk.  After $n$ steps, the typical value for the distance from the origin is proportional to $\sqrt{n}$.  Thus, the more steps you take, the greater the typical distance from the origin.  For an analysis and explanation, see https://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk.  The math is well-developed in many standard places, so I'm not going to repeat it here.


Is matrix "adjoint-squaring" faster than general matrix multiplication?

It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".

Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:

$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$

$\mathfrak{F}(A - B) = AA^\dagger + BB^\dagger - A B^\dagger - B A^\dagger$

$\mathfrak{F}(A + i B) = AA^\dagger + BB^\dagger - i A B^\dagger + i B A^\dagger$

Thinking in terms of the basis $[x, y, z, t] \rightarrow x AA^\dagger + y BB^\dagger + z A B^\dagger + t B A^\dagger$, those three adjoint-squarings give us $p=[1, 1, 1, 1]$ and $q=[1,1,-1,-1]$ and $r=[1,1,-i,i]$ respectively. From that we want to recover the product $[0,0,1,0] \rightarrow AB^\dagger$. A bit of work will show that the linear combination $\frac{1-i}{4}p - \frac{1+i}{4}q + \frac{i}{2} r$ is exactly what we need.

Therefore we can compute the product $U \cdot V$ via $\mathfrak{F}$ by evaluating:

$$U \cdot V = \frac{1-i}{4} \mathfrak{F}(U + V^\dagger) - \frac{1+i}{4} \mathfrak{F}(U - V^\dagger) + \frac{i}{2} \mathfrak{F}(U + i V^\dagger)$$

Since the most expensive step of this reduction is the adjoint-squaring (it's certainly not the adding, conjugating, transposing, subtracting, or scaling), and the adjoint-squaring function $\mathfrak{F}$ is only used a constant number of times (3 times), general multiplication is no more asymptotically expensive than adjoint-squaring.

(Related: Is matrix squaring asymptotically faster? Nope. With a much simpler proof.)


You are actually wrong. I'll give you a hint for the grammar of $L_1$. Rewrite it as $a^p b^r b^q c^{s-t} c^t d^t d^q e^r e^p$. Although I have no idea how the case $s = 0, q = 0$ (thus $q+t < 0$) is supposed to work.

For $L_2$ there is an implicit comparison $r \leq q+r$. Take $p = q = 0$ so that the string is $b^rc^sd^re^s$. You should be able to apply the lemma here easily.


Size of decision tree and depth of decision tree

The depth of a decision tree is the length of the longest path from a root to a leaf.

The size of a decision tree is the number of nodes in the tree.

Note that if each node of the decision tree makes a binary decision, the size can be as large as $2^{d+1}-1$, where $d$ is the depth.  If some nodes have more than 2 children (e.g., they make a ternary decision instead of a binary decision), then the size can be even larger.  So, a size of 7650 is not unreasonable, if some nodes make binary decisions and some make ternary or multi-way decisions.


Help with Linear recurrence relation with balanced partition

Looks like I learned it by myself in a different way than my teacher teaches it, and that is why I never heard of "balanced partition".

Apparently it means that a problem is divided in more sub problems (kind of like quick sort as I said), and when we have this condition where T(n/b) and b>=2, we use the "balanced partition" method.

I learned it in a different way, by getting Theta as f(n) and looking for p and k, where Theta(n^k * log^p(n)) , after that I have different cases, like in the following picture, my teacher teaches in a different way and that is why i got confused, because in English there is no "balanced partition" therm.


Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

This 2 definitions, of course, are not equivalent, when $g$ have $0$ subseuquence i.e. when $\exists n_k \in \mathbb{N}, n_{k+1}>n_k , k\in \mathbb{N}$ such that $g(n_k)=0$. In this case, assuming, that $\frac{0}{0}$ have no sense as well as $\frac{a}{0}, a \ne 0$, then $\frac{f(n_k)}{g(n_k)}$ is not defined, while definition with quantifiers have no problem.
This is why, imho, first should be taken as base definition and second considered only in appropriate situations and why I count your question important.
If such subsequence does not exist, then your proof is correct.


"interesting" is very subjective.

You could try Brian's Brain or Brian's Seeds, both of which I find interesting.
http://en.wikipedia.org/wiki/Seeds_%28cellular_automaton%29

While they are designed for an infinite plane, you could wrap your 4x10 grid at the top and bottom presenting a theoretical sphere instead of a plane.

As a interesting thought, you could start with Langton's ant and then add a swarm to the ant, then chose a random element of the swarm to take over control for the next X iterations.


Your class $C_{1,\epsilon}$ is the same as RP. It is clear that everything in $C_{1,\epsilon}$ is in RP. In the other direction, take an RP algorithm for a problem, and amplify its success probability to be $1-\delta$. Now modify it to toss coins and reject with probability $\epsilon$ (or some constant $c > \epsilon$) and only then run. If $\delta$ is small enough, then the overall success probability in the Yes case will be arbitrarily close to $1-\epsilon$.

The same argument shows that $C_{2,\epsilon}=coRP$, and so $C_{1\epsilon} \cap C_{2\epsilon} = ZPP$.


Proof that AND-OR graph decision problem is NP-hard

Hint: given an instance of set cover problem, build an AND-OR graph whose terminal nodes represent elements and whose OR nodes represent sets.


What is the name of this problem in Computer Vision?

This seems to be exactly scene description as described, for example, in Timor Kadir's thesis:

  Broadly speaking, the aim of scene description is to arrive at a set of descriptions of a real world scene which sufficiently capture the component parts of the scene, their positions, poses, motions and interactions. (p. 3)


Counting the number of N-dimensional coprime integer vectors

For $N=2$, the problem is easy: count the number of non-coprime pairs, by expressing it as a union over all possible values for their common divisor.  In particular, a pair $(x_1,x_2)$ is not coprime if there exists a $d>1$ such that $d|x_1$ and $d|x_2$; for fixed $d$, it's easy to count the number of such pairs, so now just sum over all possible values of $d$.

For $N=3$, you could try using the following characterization:

$\gcd(x_1,x_2,x_3)=1$ iff either (a) $\gcd(x_1,x_2)=1$, or (b) $\gcd(x_1,x_2)>1$ (so define $d=\gcd(x_1,x_2)$) and $\gcd(d,x_3)=1$.

These two conditions are mutually exclusive, so you can count the number of type-(a) triples and the number of type-(b) triples and then sum those two numbers, to get the number of co-prime triples.

You can count the number of triples of type-(a) quickly (by reducing to the $N=2$ case).  You can also count the number of triples of type-(b) quickly, by summing over all possible values of $d$ (for fixed $d$, the number of type-(b) tuples with a particular value of $d$ reduces to a smaller version of your problem with $N=2$ and a smaller value of $K$).

I think you can probably see how to generalize this to larger $N$, giving you a recursive algorithm to solve your problem for general $N$.  I'll let you work out the details.


Least number of guesses needed to determine all unknown subsets of a set

A simple algorithm may be:

Loop on:

take the next unassigned element Ei and create a new set Si assigning Ei to it.
loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, assign j it to Si.

In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...


Membership problem for context sensitive languages PSPACE-complete

I'm assuming that the context-sensitive language is given to you as a context-sensitive grammar. Summarizing the Wikipedia article, here is how to show that the word problem for context-sensitive grammars is $\mathsf{PSPACE}$-complete.

First, we show that the word problem is in $\mathsf{PSPACE}$. The productions in a context-sensitive grammar cannot decrease the size of the word. Therefore, given a context-sensitive grammar $G$ and a word $w$, we can repeatedly apply productions in reverse, in the hope of eventually reaching the starting symbol $S$. We also keep a counter, and give up after $|\Sigma|^{|w|}$ steps (this ensures that the machine always halts), where $\Sigma$ contains both terminals and non-terminals; the size of this counter is $|w| \log |\Sigma| = O(n\log n)$ (here $n$ is the input size). This puts the word problem in $\mathsf{NSPACE}(O(n\log n)) \subseteq \mathsf{NPSPACE} = \mathsf{PSPACE}$, using Savitch's theorem.

In the other direction, Kuroda showed how to convert a linear bounded automaton (that is, a machine in $\mathsf{NSPACE}(n)$) to a context-sensitive grammar in such a way that the LBA accepts a word iff the CSG accepts it. Given a language $L \in \mathsf{SPACE}(p(n))$, we consider the language $L' = \{x\#^{p(|x|)} : x \in L \}$ obtained by padding $L$, and note that $L' \in \mathsf{NSPACE}(n)$. Kuroda's theorem gives an equivalent context-sensitive grammar $G'$. In order to check whether $x \in L$, we first compute $x' = x\#^{p(x)}$, and then check whether $G'$ accepts $x'$. This gives a polynomial time reduction from any language in $\mathsf{PSPACE}$ to the word problem for context-sensitive grammars, and so the latter is $\mathsf{PSPACE}$-complete.


What is a suitable data structure in this scenario?

Depending on how limited the memory is, the best choice for 1 could be a sorted array: Binary search is fast, insertions and deletions are rare and memory overhead is negligible.

For number 2 a (unsorted) singly linked list is better than a doubly linked one, since we (presumably) don't perform any operations that benefit from the backlinks and thus can save the memory (and maintenance time) required for them.

For number 3, unless the hash function and data don't play nicely with each other, the hash table will likely be faster than a tree. If the load factor does not get too low, it will also be more space efficient, since a binary tree with $n$ keys needs $\sim 2n$ pointers.


For the correct/sensible interpretation, $(ab)^*(cbb^*)^*$, I will list the states and its corresponding regular expressions below; you can figure out the transitions between the states.

$q_{0}$: $(ab)^*$, start state
$q_{1}$: $(ab)^*a$
$q_{2}$: $(ab)^*(cbb^*)^*c$
$q_{3}$: $(ab)^*(cbb^*)^*$, accepting state
$q_{4}$: for all other strings, rejecting state/dead-end state

For the incorrect/unlikely interpretation, where $(cb^n)^*$ means all words like the empty word, $cb^n$, $cb^ncb^n$ and $cb^ncb^n\cdots cb^n$ for some $n\ge1$, the corresponding language is not regular since its intersection with the language with regular expression $cb^*cb^*$, $\{cb^ncb^n\mid n\ge1\}$ is not a regular language. So there is no FSA for that language.


Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$

One example would be the hierarchy defined by blind counter automata.
A blind $k$-counter automaton has access to $k$ counters for which

there is an increment and a decrement instruction (and no zero-test),
a run is accepting if in the end, all counters are zero, and
during a run, the counters are allowed to be negative.

Let $\mathcal{B}_k$ denote the class of languages accepted by blind
$k$-counter automata. Then $L_{k}\in \mathcal{B}_{k-1}$: while you
read $a_1$'s, you increment all $k-1$ counters simultaneously; then each of the remaining $k-1$ letter blocks decreases one of the counters.

On the other hand, one has $L_{k}\notin\mathcal{B}_{k-2}$.
This can be shown, for example, using Theorem 6.4 in Fernau and
Stiebe's paper on valence
automata/grammars. This pumping lemma allows, in a blind $\ell$-counter automaton, the simultaneous repetition of $\le\ell+1$
non-empty factors. Hence, if we had $L_k\in\mathcal{B}_{k-2}$, we could repeat $\le k-1$ factors, which can span at most $k-1$ distinct letters
in a word $a_1^*\cdots a_k^*$. Hence, we could pump up powers of some $a_i$'s
without touching at least one letter $a_j$, which clearly leads out of
the language. In Fernau and Stiebe's paper, the class $\mathcal{B}_k$ is
denoted $\mathscr{L}(\mathrm{Val},\mathrm{Reg},\mathbb{Z}^k)$.


how does the program change the clock speed of the processor?

This is different for any processor. You should consider going to the Intel, ARM and AMD websites and looking for the right manuals. That’s what I would do if I had to answer the question, and that’s what I recommend you should do.


As we have on both sides of equality sets, then it should be prove correspondingly i.e we need to show, that $\Theta(n^2) \subset \Theta(n^2+1)$ and $ \Theta(n^2+1)\subset \Theta(n^2) $. Let's start with first:
Assume $f \in \Theta(n^2)$. This means, that for some constants $A_1, A_2 \gt 0$ holds
$$A_1 n^2 \leqslant f(n) \leqslant A_2 n^2$$.
To obtain inequalities for $\Theta(n^2+1)$ we need
$$B_1 (n^2+1) \leqslant f(n) \leqslant B_2 (n^2+1)$$
It's easy to see, that it's enough to take $B_2 = A_2$ for right hand and $0<B_1 \leqslant \frac{A_1}{2}\leqslant \frac{A_1 n^2}{n^2+1}$ for left hand,  as $A_2>0$.


Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular?

In $\{wxw^R|w,x\in\{0,1\}^+\}$, we're free to choose $x$ to be any non-empty sequence, including all but the first and last characters of $wxw^R$. So we might as well limit $w$ to be a single symbol; it won't change anything.

So $L$ is exactly the same as $L' = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$ which is evidently regular.

Here's a more formal proof, in case the above was too telegraphic. Suppose we have

$$L = \{wxw^R|w,x\in\{0,1\}^+\}$$

Now:

$$\{0,1\}^+ \equiv \{0,1\} \cup \{aw | a \in \{0,1\} \land w \in \{0,1\}^+$$

which just says that $w^+$ is either exactly one symbol or one symbol concatenated with $w^+$. Also observe that if $a$ is a symbol and $w$ is a sequence of symbols, then $a^R\equiv a$ and $(aw)^R\equiv w^Ra$. So we can rewrite $L$ as a union:

$$L = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\} \cup \{awxw^Ra|a\in\{0,1\}\land w,x\in\{0,1\}^+\}$$

Now, looking at the two sets in that union, we can see that

$$\{awxw^Ra|a\in\{0,1\}\land w,x\in\{0,1\}^+\} \subset \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$$

because

$$\{wxw^R|w,x\in\{0,1\}^+\} \subset \{0,1\}^+$$

and since for any sets $A$ and $B$

$$B \subset A \implies A = A \cup B$$

We can simplify the definition of $L$ to

$$L = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$$

which is clearly a regular language.


One way to interpret this as that it's indicating that points that are nearby in feature space are likely to have the same labels.  So, a classifier that takes this into account might do well.

Based on that, you might try a $k$-nearest neighbor classifier.  Basically, you classify each test point by finding the $k$ most similar labelled samples, and then using some kind of voting scheme among the corresponding $k$ labels.  I anticipate this might give quite good results.

Alternatively, another way to use this is to use some kind of active learning algorithm to help you choose a small subset of the 10000 samples to manually label, with the goal of choosing those smartly so those additional labels help improve the performance of your classifier as much as possible.  One standard approach is to train a classifier on the labelled instances, apply it to all the remaining instances, pick out the 20 instances that the classifier is least confident on, manually label those 20 instances, add them to the training set, and repeat.  In your situation, a possible approach is to train a classifier on the labelled instances, apply it to all the remaining instances, from each cluster randomly sample a few instances whose predicted label disagrees with the majority label for that cluster, manually label all those instances, add them to the training set, and repeat.  Or, you could train both a normal classifier and a $k$-nearest-neighbor classifier on the labelled samples, apply them to all remaining instances, find ones where the two classifiers disagree on their prediction, randomly sample 20 of them (possibly using a farthest-first heuristic to maximize their diversity), manually label them, and add them to the training set and repeat.

You might need to experiment a bit to see what works best.


Converting (math) problems to SAT instances

Chapter 2 of the SAT Handbook (by Steven Prestwich) covers how to turn discrete decision problems into CNF, in some depth.  (Unfortunately, I don't think there is a draft version online -- probably best to consult your local library.)  Several of the other references cited in Magnus Björk's quirky overview Successful SAT Encoding Techniques are also useful.

If your problems are continuous, or you are especially interested in systems of inequalities, then other kinds of solvers are more likely to be useful.  As Kyle points out, SMT solvers (such as Z3, Yices, or OpenSMT) might be useful, although traditionally SMT theories tend to be focused on verification of computer software, so SMT solvers usually have great support for things like expressions involving intervals of integers, but may perform poorly on injectivity constraints.  For problems that are naturally expressed as systems of inequalities, CPLEX is the one to beat (it used to be available for academic use for free, and it might still be).  For some combinatorial decision problems (like finding packings of rectangles into a square), constraint solvers such as Minion outperform SAT solvers and are often easier to use.


I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation.  I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," _IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005.

The table lookup is indexed with the $m$ most-significant bits from the input, $x$, and returns three coefficients, $c_0$, $c_1$, $c_2$.  The final result is produced by evaluating $c_0 + c_1 x + c_2 x^2$.  The coefficients for each range of $x$ are chosen to minimize the maximum error from the target function over that range.

So that the unit can be fully pipelined to produce one result per cycle the unit contains a special squaring unit and two booth-encoded wallace-tree multipliers.  For each special function they choose the number of table entries ($2^m$) so that the polynomial evaluation will give them a single-precision IEEE FP answer correct to within a couple of units in the last place.


Kolmogorov complexity of a sequence of prime numbers

Since we can generate $p_n$ given $n$, $K(p_n) \leq K(n) + O(1) \leq \log_2 n + O(1)$. The prime number theorem implies that $p_n = \Theta(n\ln n)$, and so $\log_2(p_n) = \log_2 n + \log_2\log_2 n \pm O(1)$. You take it from here.


Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?

Probabilistic "functions" are not even functions in the classical sense of the term "function", that is, they do not assign to each member of the domain a specific member of the range. They are not even partial functions.  So the requirement of the Blum axioms that the complexity functions be computable cannot be satisfied.

Specifically, for a TM $M$ with input $x$, the Blum axioms require an algorithm that for input $(M,x,n)$ decides if $\Phi(M,x)=n$, where $\Phi$ is the complexity measure.  But if $\Phi(M,x)$ is a probabilistic function, then it cannot be computed by an algorithm, and there also can be no algorithm as required by the axioms.

We could, however, define a complexity measure differently on probabilistic models, allowing a random variable, which is after all, a kind of function.  Then various properties of the r.v. -- mean, median, standard deviation, etc -- could well qualify as complexity measures, and you could develop the theory from there, in the probabilistic/statistical realm.

So, although Blum measures are somewhat out of favor, except for the classic space and time measures, there's no inherent reason the basic idea can't be extended in ways like this.


What is the average size of a jump in a binary tree?

Consider a binary search tree with layers $0,\ldots,h$, where layer $\ell$ contains $2^\ell$ nodes. The left child of a node $x$ is located next to it (at distance 1). If $x$ is at layer $\ell$, then its left subtree contain $2^{h-\ell}-1$ nodes, and so the right child of $x$ is at distance $2^{h-\ell}$. These observations are illustrated in the figure:

Here $h = 3$, and the root ($\ell = 0$) has a left child at distance $1$ and a right child at distance $2^{h-\ell} = 8$.

We will calculate the average size of a jump in a random root-to-leaf path. This corresponds to searching for a random leaf.

The expected jump at level $\ell$ is thus $\frac{1+2^{h-\ell}}{2}$. Since there are $h$ jumps overall (at levels $0$ to $h-1$), the average jump is
$$
\frac{1}{h} \sum_{\ell=0}^{h-1} \frac{1+2^{h-\ell}}{2} =
\frac{1}{2} + \frac{1 + \cdots + 2^{h-1}}{h} =
\frac{1}{2} + \frac{2^h-1}{h}.
$$
Since the number of nodes in the tree is $n := 2^{h+1}-1$, the average jump is $\Theta(n/\log n)$. The same holds for the number of leaves $m := 2^h$.


Here is a rough idea how to solve this. You compare $f(x)$ and $f(y)$ character by character. Your tape is devided into 4 pieces. The first one is for simulating  $f(x)$ the second one for $f(y)$, then you have two parts, one that counts which character of $x$ you are currently computig, and another $O(\log n)$ area that helps you to navigate. Now the programm looks like this

Determine $|x|$ and $|y|$ (store it in binary!)  and check if there are the same.
Compute the first character of $f(x)$ by simulating it on your machine. Store the output in a TM-state. Pause the Computation of $f(x)$.
Walk $|x|+1$ step to the right.
Simulate $f(y)$ until you get the first character, check if it coincides with the start of $f(x)$, if no reject, otherwise continue.
Walk $|x|$ steps left.
Repeat the steps 2.-5. until you check $f(x)=f(y)$ completely.


Context Free Grammar: at least 2 1's, at most 2 0's

Hint

If $L_{i j}$ is the language with at least $i$ $1$s and at most $j$ $0$s

$$\begin{align}
L_{2 2} &= 1 \, L_{1 2} \, | \,?\\
... \\
L_{0 0} &= \,?
\end{align}$$

Edited to answer the correct question.


Is NP-hard closed against cartesian product with arbitrary languages?

$L_1 \times L_2$ is NP-hard.

Proof: Let $L$ be a language in NP, let $f$ be a reduction of $L$ to $L_1$ and let $w_2$ be in $L_2$. Define $g(x) = (f(x), w_2)$. Now $g$ is a polynomial time many-to-one reduction of $L$ to $L_1 \times L_2$ because clearly:

$x \in L \quad \Longleftrightarrow\quad (f(x), w_2) \in L_1\times L_2$


Yes.

Let $c_0 = 0$ and $c_i = \sum_{j=1}^i a_i$, (which can be done in linear time).  Now the problem becomes -- find $0\le i < k\le n$ such that for all $i\le j<k$ we have $c_i\le c_j \le c_k$ that maximizes $k-i$.  This can be found in a single sweep. (I'll let you work out the details.)

For the problem actually asked:  We want the longest subsequence that begins and ends with 1 and each of the prefix and suffix sums is nonnegative.  First note that all $a_i=1$ are included as including it will only increase the prefix and suffix sums.  In particular $b_1=a_1$ and $b_k=a_n$.  We can construct $(b)$ in two passes.  First pass from $i=1$ to $n$ selecting every $a_i$ such that either $a_i = 1$ or $a_i=-1$ and the prefix condition is not violated in our subsequence (we are greedily selecting everything subject to the prefix condition).  Now pass backwards through the subsequence discarding elements that violate the suffix condition.

Note that since all of the $a_i=1$ are in $(b)$ the sum of $(b)$ is just the count of $a_i=b_j=1$ minus the count of the $b_j=-1$ and so is twice the count of $a_i=1$ minus the length of $(b)$, a function of the length.  So any other subsequence satisfying the conditions having the same length will have the same sum.


Is it possible to modify dijkstra algorithm in order to get the longest path?

Longest path is basically the Hamiltonian Cycle problem or the Traveling Salesman Problem, and it is NP-hard. So no, and if you find a way, then ${\rm \mathbf{P=NP}}$.

The existence or non-existence of an algorithm to find the largest path, in polynomial time, is essentially part of the largest open problem in all of CS (and probably in math).

Incidentally, the Bellman–Ford algorithm can handle negative weights, so long as they don't form a cycle; in which case, if it encounters one (ie. if the cycle is reachable from the source), it would run forever, running 'round and 'round the cycle, accumulating a "shorter" and "shorter" path. Of course, it can detect this, and terminate, and is thus useful for detecting such cycles.


Algorithm to search substring in a circular string?

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string.  The source string must be concatenated at least once.

Then perform a simple (non-circular) search on that temporary string.


Does this Turing Machine M decide the language of polynomials?

The problem with this algorithm is that it never terminates when the polynomial has no integer roots. Its semantics are:

If the input polynomial is in $L$, the machine halts and answers YES.
If the input polynomial is not in $L$, the machine never halts.

The semantics we are after are a bit different:

If the input polynomial is in $L$, the machine halts and answers YES.
If the input polynomial is not in $L$, the machine halts and answers NO.


Where do you exactly use data structures?

This is a broad question but will attempt to answer.

From my understanding of your question, you have billions of strings which you want to use for autocomplete.

The way most typical autocomplete examples work is you load the entire set of strings into memory and build a trie. That works well for small datasets like the list of countries, or a small list of tags.

Searching for how google implements its autocomplete doesn't return any results, but that would be sort of what you're asking I'd think.

What I imagine is slow in your current implementation is, you have billions of rows in your database, with a column containing the string of interest. Then you are just doing a LIKE search to match substrings. So it has to scan every string in the billions of records, which is very slow.

The (typical relational) database won't offer you much support here.

One solution to this problem is to use a "full text search database" such as Lucene. The problem this solves is indexing. Another related index that might help is an inverted index. An inverted index might use a B+tree for indexing the terms (words perhaps) in documents (or strings in your case). But this just means it will match individual terms/words, not complete sentences or exact substring matches like the LIKE query will do.

So you have to decide how you want your autocomplete to work. If they can search for exact strings in the text, then the best solution is probably to create a gigantic trie for all the strings. If the trie doesn't fit into main memory, as probably is your case, then you could potentially try creating a string b-tree data structure instead of a trie. This is better as an on-disk data structure. If instead they can search for tokens/terms/words like a keyword search, then you can use an inverted index B-tree, such as with Lucene. Either way you will need another data structure on top of the relational database, and probably one that efficiently works with a file system.


Looking for an algorithm to find a shortest path in a special graph

The "state" of a traversal (after visiting $k$ edges) is the set of $k$ edges that you've traversed so far, in the order they were traversed.  You can now use any method for exploring this state space: e.g., BFS; or A*, if you have a suitable heuristic.

In other words, we define a new graph $G'$ where each vertex of $G'$ is a possible state of a traversal (after visiting some number of edges), and where there is an edge $u \to v$ if starting from state $u$ it is possible to add one edge to the end to reach state $v$.  Then you do BFS in $G'$.  You don't need to build up $G'$ explicitly before doing BFS; the graph can be represented implicitly (where each time you reach a state $u$, you can compute all possible next-states reachable from $u$ in a single step).

If BFS takes too much memory, you can use techniques from explicit-state model checking.  This will reduce the space consumption but not the memory usage.

None of this avoids the fact that, for arbitrary functions $f,g$, the running time of these algorithms might all be exponential in the worst case, because you might need to explore an exponentially-sized state space.  I suspect the only hope to do better is to take advantage of knowledge of some particular structure in $f,g$.


Is this problem that's similar to integer linear programming also an NP-complete problem?

Your problem is solvable in polynomial time.

Your problem is equivalent to ILP with difference constraints, i.e., every linear inequality has the form $x_j - x_i \ge c_{i,j}$.  (Why?  Set $x_i = v_1 + \dots + v_i$; then $v_{i+1} + \dots + v_j = x_j - x_i$.)

Such a system of inequalities can be solved with shortest-path algorithms.  In particular, if we didn't have the restriction to integer values, this becomes the standard problem of solving a system of difference constraints.  You can solve this by creating a graph with one vertex per variable and one edge per constraints, and finding shortest paths using Bellman-Ford.  See, e.g., Algorithms: Difference Constraints, Decide whether a set of inequalities is solvable, http://videolectures.net/mit6046jf05_demaine_lec18/, or a good textbook (I think this is described in CLRS).

As stated, those algorithms don't take into account the restriction to integer solutions.  But if you examine how shortest path algorithms work, if all of the constants are integers, then the solution will be an integer solution as well.  So, that ensures you get an integer solution.

Lastly, the requirement that $v_1 + \dots + v_n = c$ is equivalent to $x_n = c$, which can be handled using the shortest paths algorithm.  In particular, find a solution; then if $x_n \ne c$, then set $c' = c - x_n$ and add the constant $c'$ to all variables; the result will be another solution that satisfies all the inequalities, and also satisfies the equality $x_n = c$.

Finally, once you've solved to find a solution for the $x$'s, you can recover a solution for the $v$'s by setting $v_i = x_i - x_{i-1}$.

One catch is that this solution might not be all positive.  To handle this, I suggest adding the inequalities $x_i - x_{i-1} \ge 0$ before solving.  That will then meet all of your needs.


If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?

Let's attempt to prove your original statement, that if $f(n) = O(g(n))$ then $\log f(n) = O(\log g(n))$.
According to the definition, there exist $C,N>0$ such that if $n \geq N$ then $f(n) \leq Cg(n)$. Taking the logarithm of both sides, if $n \geq N$ then
$$ \log f(n) \leq \log C + \log g(n). $$
Is this enough to imply that $\log f(n)= O(\log g(n))$? Not in general. For example, $2 = O(1)$ but $\log 2 \neq O(\log 1)$. However, it suffices to assume that $g(n) \geq 2$ for all $n \geq N$, since this implies that
$$
\log f(n) \leq \log C + \log g(n) \leq (\log C + 1) \log g(n),
$$
using $\log g(n) \geq 1$.
Now back to your case. Since $\log \lfloor f(n) \rfloor \leq \log f(n)$, it suffices to show that $\log f(n) = O(\log \lfloor g(n) \rfloor)$. For this, it suffices to show that $\log g(n) = O(\log \lfloor g(n) \rfloor)$. Indeed, recall that by assumption, $g(n) \geq 2$ for all $n \geq N$. We will show that if $x \geq 2$ then $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Therefore $\log g(n) = O(\log \lfloor g(n)\rfloor)$.
It remains to show that $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Let $\rho(x) = \frac{\log x}{\log \lfloor x \rfloor}$. Our goal is to show that $\rho(x) \leq \frac{\log 3}{\log 2}$ for all $x \geq 2$. Fixing $\lfloor x \rfloor = m$, it is clear that $\rho(x) \leq \frac{\log (m+1)}{\log m}$, hence it suffices to show that $\frac{\log(m+1)}{\log m} \leq \frac{\log 3}{\log 2}$ for all integer $m \geq 2$. This can be shown in various ways. For example, the function $\frac{\log(x+1)}{\log x}$ is decreasing for $x \geq 2$ by calculus: its derivate is
$$
\frac{x\log x - (x+1)\log(x+1)}{x(x+1)\log^2 x},
$$
which is clearly negative for $x \geq 1$ (since $x\log x$ is increasing – its derivative is $\log x + 1$).


Terminologies of "Process calculus" and "Process algebra"

To my knowledge the two terms do not have a formal established definition and are often used interchangeably.

There are different characteristics associated to each however, as @Dave already pointed out. I'll try to elaborate a bit further.

In both cases you start by introducing the syntax of a language for expressing (concurrent) systems. This introduces what the basic "combinators" (constructs) for assembling systems together are.
The real distinction comes when you start to specify their semantics.

The process calculi approach is calculational in the sense that you focus on the reduction semantics, i.e. what are the steps a system can perform when executing it. This operational view helps a lot when using these languages for simulation for example.
The chief notion in this case is the concept of "observation": what can you observe about the evolution of a system? Using this idea one can determine when two systems are equivalent. The technical word for this concept is bisimilarity. Then, in some situations, you find that processes which are bisimilar can be interchanged in any context without altering the behaviour of the system overall. This is the approach Milner and his collaborators took in defining many calculi such as CCS and π-calculus.

The algebraic view instead avoids specifying a model for the semantics directly and opts for a more axiomatic view: a series of laws (equations between expressions of the language) establish which processes have the same behaviours. The focus is in proving equivalences and enriching the calculus with different combinators. Even the "execution" of a system is expressed as an equivalence between a system and a (simpler expression used as a) specification (see the step laws for CSP for instance).
The equivalence between two systems is established by using the laws instead of referring to a particular model for their behaviour. The chief concept in this context is the one of refinement. This approach is the basis of the work of Hoare and his collaborators in defining CSP and its variants.

That said, most of the languages mentioned have being studied with a mixture of these approaches so the distinction is more about the specific method used in a specific construction rather than about a language as a whole.


Looking for a set implementation with small memory footprint

Joe's answer is extremely good, and gives you all the important keywords.

You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain asymptotic complexity both over the universe size and the number of elements stored. If either one of these is relatively constant, then a lot of the complexity goes away.

If the collection is semi-static (that is, inserts are rare, or at least low-volume), then it's certainly worth considering an easy-to-implement static data structure (Sadakane's sdarray is a fine choice) in conjunction with an update cache. Basically, you record updates in a traditional data structure (e.g. B-tree, trie, hash table), and periodically bulk-update the "main" data structure. This is a very popular technique in information retrieval, since inverted indexes have many advantages for searching but are hard to update in-place. If this is the case, please let me know in a comment and I'll amend this answer to give you some pointers.

If inserts are more frequent, then I suggest succinct hashing. The basic idea is straightforward enough to explain here, so I will do so.

So the basic information theoretic result is that if you're storing $n$ elements from a universe of $u$ items, and there is no other information (e.g. no correlation between the elements) then you need $\log {u \choose n} + O(1)$ bits to store it. (All logarithms are base-2 unless otherwise specified.) You need this many bits. There is no way around it.

Now some terminology:

If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(1)$ bits of space, we call this an implicit data structure.
If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(\log {u \choose n}) = (1 + O(1)) \log {u \choose n}$ bits of space, we call this a compact data structure. Note that in practice this means that the relative overhead (relative to the theoretical minimum) is within a constant. It could be 5% overhead, or 10% overhead, or 10 times overhead.
If you have a data structure which can store the data and support your operations in $\log {u \choose n} + o(\log {u \choose n}) = (1 + o(1)) \log {u \choose n}$ bits of space, we call this a succinct data structure.

The difference between succinct and compact is the difference between little-oh and big-oh. Ignoring the absolute-value thing for a moment...

$g(n) = O(f(n))$ means that there exists a constant $c$ and a number $n_0$ such that for all $n > n_0$, $g(n) < c \cdot f(n)$.
$g(n) = o(f(n))$ means that for all constants $c$ there exists a number $n_0$ such that for all $n > n_0$, $g(n) < c \cdot f(n)$.

Informally, big-oh and little-oh are both "within a constant factor", but with big-oh the constant is chosen for you (by the algorithm designer, the CPU manufacturer, the laws of physics or whatever), but with little-oh you pick the constant yourself and it can be as small as you like. To put it another way, with succinct data structures, the relative overhead gets arbitrarily small as the size of the problem increases.

Of course, the size of the problem may have to get huge to realise the relative overhead that you want, but you can't have everything.

OK, with that under our belts, let's put some numbers on the problem. Let's supposed that keys are $n$-bit integers (so the universe size is $2^n$), and we want to store $2^m$ of these integers. Let's suppose that we can magically arrange an idealised hash table with full occupancy and no wastage, so that we need exactly $2^m$ hash slots.

A lookup operation would hash the $n$-bit key, mask off $m$ bits to find the hash slots, and then check to see if the value in the table matched the key. So far, so good.

Such a hash table uses $n 2^m$ bits. Can we do better than this?

Suppose that the hash function $h$ is invertible. Then we don't have to store the whole key in each hash slot. The location of the hash slot gives you $m$ bits of the hash value, so if you only stored the $n-m$ remaining bits, you can reconstruct the key from those two pieces of information (the hash slot location and the value stored there). So you would only need $(n - m) 2^m$ bits of storage.

If $2^m$ is small compared with $2^n$, Stirling's approximation and a little arithmetic (proof is an exercise!) reveals that:

$$(n - m) 2^m = \log {2^n \choose 2^m} + o\left(\log {2^n \choose 2^m}\right)$$

So this data structure is succinct.

However, there are two catches.

The first catch is constructing "good" invertible hash functions. Fortunately, this is much easier than it looks; cryptographers make invertible functions all the time, only they call them "cyphers". You could, for example, base a hash function on a Feistel network, which is a straightforward way to construct an invertible hash functions from non-invertible hash functions.

The second catch is that real hash tables are not ideal, thanks to the Birthday paradox. So you'd want to use a more sophisticated type of hash table which gets you closer to full occupancy with no spilling. Cuckoo hashing is perfect for this, as it lets you get arbitrarily close to ideal in theory, and quite close in practice.

Cuckoo hashing does require multiple hash functions, and it requires that values in hash slots be tagged with which hash function was used. So if you use four hash functions, for example, you need to store an additional two bits in each hash slot. This is still succinct as $m$ grows, so it's not a problem in practice, and still beats storing whole keys.

Oh, you might also want to look at van Emde Boas trees.

MORE THOUGHTS

If $n$ is somewhere around $\frac{u}{2}$, then $\log {u \choose n }$ is approximately $u$, so (once again) assuming that there is no further correlation between the values, you basically can't do any better than a bit vector. You will note that the hashing solution above does effectively degenerate to that case (you end up storing one bit per hash slot), but it's cheaper just to use the key as the address rather than using a hash function.

If $n$ is very close to $u$, all of the succinct data structures literature advises you to to invert the sense of the dictionary. Store the values that don't occur in the set. However, now you effectively have to support the delete operation, and to maintain succinct behaviour you also need to be able to shrink the data structure as more elements get "added". Expanding a hash table is a well-understood operation, but contracting it is not.


You can't. As shown by Brown and Tarjan on the first page of "A Fast Merging Algorithm", merging two sequences with overlapping ranges has a worst-case bound of $\Theta (m \lg (n/m))$ comparisons.


How can I combine my interests for pure mathematics and computer science in college?

Math is heavily used in both computer security, machine learning and AI.

Computer Security, such as encryption and related fields is all about finding math that makes it impossible to retrieve information without being the intended recipient.  With quantum computing possibility being a reality within the next 10 - 20 years there is a lot of work needed to come up with new ways of securing data.  Number theory is very relevant here.
Machine learning is heavily based on statistics.  new algo's with better capability of prediction is always relevant, and a very hot topic.
AI, while strictly an area of machine learning, are typically resolving to other areas of of learning than typical stats.  Any advancements in this areas will be done by people with strong math background.


How to sort a large list of elements where everything is sorted but k elements?

Here is an $O(k \log k + n)$ Algorithm. Assuming we are dealing with an ascending order. We assume $A$ is a linked list, an hence removing elements can be done in constant time. Given an array instead, we can preprocess it in linear time building a linked-list out of it.

Let A be a given list of n elements.
Let B be an empty array.
For x in A do
- Let y be the element following x.
- As long as y < x then
- - Add x to B.
- - Add y to B.
- - Remove x from A.
- - Remove y from A.
- - If x was the first element,
- - - then break from the inner loop.
- - Set x to the previous element of x.
- - Set y to the following element of y.
Sort B with any efficient sorting algorithm.
Unify A and B in the array C efficiently.
Return the array C.

If an element $x$ is greater than the following element $y$, then at least on of them must be one of the $k$ elements, because else they must be sorted. Hence, we do not remove more than $2k$ elements from $A$. Since with each visit of the inner-loop except for the last one, we remove two elements from the array, and since we do not remove in total more than $2k$ elements, the total number of visits of the inner loop is at most $2k+n$. The size of $B$ is at most $2k$, since it only has the elements removed from $A$. Using quick-sort, we can sort $B$ in running time $O(k \log k)$ (note that $B$ is an array and not a list). Unifying two sorted arrays/lists in a new sorted list can be achieved in linear time using sliding-window.
The total running time is $O(n + 2k + k \log k + n + k) = O(k \log k + n)$.


Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

If a decision tree has at least $m$ leaves then its height is at least $\log_2 m$. It is the height that bounds the number of comparisons rather than the number of leaves. In your case there are $(n/k)!^k$ leaves, and so $\Omega(\log[(n/k)!^k]) = \Omega(n\log(n/k))$ comparisons.


On complete problems for $P/poly$ and $BPP$

There are no $P/Poly$ complete languages (relative to polynomial time or even computable reductions).

Suppose for the purpose of contradiction that there exists some language $L$ which is complete for $P/Poly$. In that case the mapping $f:P/Poly\rightarrow \mathbb{N}$, which maps any language in $P/Poly$ to its corresponding reduction to $L$ (we refer to the encoding of this reduction as a natural number), is an injection from $P/Poly$ to the natural numbers. This of course leads to a contradiction, since $P/Poly$ is of cardinality $2^{\aleph_0}$.

In light of Ricky Demer's comment, we should note that since computable reductions are of no use to $P/Poly$, one needs to introduce the notion of non-uniform reductions. One example is projection reductions.

A family of boolean functions $f_n(x_1,...,x_n)$ is said to be projection reducible to the family $g_n(y_1,...,y_n)$ if for all $n\in\mathbb{N}$ there exists some $m\le p(n)$ with polynomial $p$, and a rewiring of $g$'s inputs, $\sigma:\left\{y_1,...,y_m\right\}\rightarrow\left\{0,1,x_1,\overline{x_1},...,x_n,{\overline{x_n}}\right\}$, such that $f_n(x_1,...,x_n)=g_m\left(\sigma(y_1),...,\sigma(y_m)\right)$. Intuitively, this means that given a circuit for $g$ (perhaps with polynomialy more inputs), we can compute $f$ just be rewiring the inputs accordingly. We denote this by $f\le_{proj} g$.

Note that if $g\in P/Poly$ and $f\le_{proj} g$ then $f\in P/Poly$, the advice for input $x$ would be the rewiring $\sigma$, together with the $m(|x|)$ inputs circuit for $g$.

The following is a (very) short sketch of the proof that the circuit value problem, $CVP$, which takes as input a circuit $\mathcal{C}$ and input $x$, and asks whether $\mathcal{C}(x)=1$ is $P/Poly$ hard under such reductions. Given $L\in P/Poly$, let $\mathcal{C}_n$ be the polynomial circuit family for $L$. For any string $x$, You can hardwire $\mathcal{C}_{|x|}$ as input to $CVP$ (using the constants $0/1$), and use the rest of the variables to input $x$.


In what cases is graph rewriting not enough to avoid duplicate work?

Consider this program:

f (m : Nat) x y = (x, if H(m,m) then x else y)

my_f = f my_number
my_f hard harder

where H(x,x) returns True if Turing machine number x halts on input x and False otherwise. Detecting duplicate work (always) would mean solving the halting problem, no matter whether you want to do the analysis statically or dynamically.

Hence, no method can be complete.


JavaScript and Python are both interpretive languages (as opposed to compiled languages like Java) with JavaScript being (mostly) a client-side language and Python a server-side language.

You would do well to learn them both, especially JavaScript.


Distinguishing between side-by-side liquid streams

I would suggest looking into standard methods for image processing.  You could use the Hough transform to detect circles.  You could potentially use morphological transforms and the watershed algorithm to smooth out and remove noise and detect boundaries between the regions.


what does "reduce A problem to B problem in polynomial time" mean?

There are several types of reductions, the most common of which are many-one reductions and oracle reductions.

A many-one reduction from $A$ to $B$ is a computable function $f$ mapping strings to strings such that $x \in A$ iff $f(x) \in B$.

An oracle reduction from $A$ to $B$ is a computable function $f$ which has access to a $B$-oracle, and satisfies $f(x) = 1$ iff $x \in A$. That is, $f$ decides membership in $A$. The machine has a mechanism for accessing the oracle. When the oracle is presented a string $y$, it tells the program whether $y \in B$ or not.

Every many-one reduction $f$ can be formulated as an oracle reduction: the oracle reduction first computes $f(x)$, then asks the oracle whether $f(x) \in B$, and outputs the oracle's answer.

In the theory of NP-completeness, we always use many-one reductions. Reducing a problem A to a problem B in time $T(n)$ means giving a many-one reduction from A to B which runs in time $T(n)$. In particular, reducing A to B in polynomial time means reducing A to B in time $O(n^k)$ for some fixed $k$.

In your particular case it is hard to tell which kind of reduction is meant, since your problems are not decision problems. Perhaps some restricted kind of linear time oracle reduction, say one accessing the oracle only once. It's also not clear what computation model you should use. Under some computation models you can solve problem A in linear time, and so such a reduction trivially exists (it never asks the oracle anything).


Are all finite strings over some infinite alphabet countable?

If the alphabet is uncountable then the set of all possible finite strings is uncountable. If you allow infinite length strings then by the diagonalization argument the set is also uncountable.

Assume the alphabet is countable and strings have finite length. Let's assign to each alphabet symbol a natural number, i.e., each symbol corresponds to a natural number and denote a string by a sequence of numbers. For example, if $a$ corresponds to $2$, $b$ to $5$, and $c$ to $11$ then $aabcb$ would be denoted by $2 \ 2 \ 5 \ 11 \ 5$ (I separate them by a single space to avoid confusion). We will prove that the set of all strings is countable.

We group every string of length $n$ whose individual symbols sum to $k$ into the set $C_{n,k}$. For example $000 \in C_{3,0}$, $1192 \in C_{4,13}$, and $1\ 13 \ 3 \ 1 \in C_{4,18}$. For each pair $\langle n,k \rangle$, $C_{n,k}$ is clearly finite and hence is countable. Furthermore, any string $a_1\dots a_n$ does belong to $C_{n,k}$, where $k=a_1+\dots +a_n$ which means every string is included in some set $C_{n,k}$. Since the set of all possible pairs $\langle n,k \rangle$ is countable the union of all possible $C_{n,k}$, i.e, $\bigcup_{\langle n,k \rangle \in N\times N}{C_{n,k}}$ is also countable.


This is probably an awful approach to fitting points and prediction.

There's no reason to expect that a PRNG will do a good job at fitting points.  Interpolation is effective because we think that not all curves are equally likely.  Some kind of Occam's razor applies: all else being equal, the "simpler" the curve, the more likely that it is as a plausible model.

Thus, linear regression is useful precisely because not all curve shapes are possible; only straight lines.  Empirically, straight lines occur more often than crazy-wiggly shapes.  Similarly, polynomial regression is useful because a low-order polynomial is more likely than a high-order polynomial.

Now consider the following approach: try to fit the data you already have to an arbitrary function (with no restrictions on the function or the shape of the curve; all functions are valid/legal models).  Well, that'll be an absolutely terrible approach at prediction.  You'll be able to find a function that exactly fits all of the data you already have, but (most likely) it will be absolutely useless at predicting values you haven't seen -- it'll be absolutely useless at generalization / prediction.  Essentially, you'll have massively overfitted the data set.

Now a PRNG is designed to behave like a true-random generator.  In other words, all sequences of outputs are supposed to be equally likely (or, at least, you can't tell the difference).  Fitting your data to a true-random generator will be useless at prediction/generalization.  For the same reason, fitting your data to a PRNG is likely to be useless at prediction/generalization.

You should probably read about the "no free lunch" theorems for machine learning and prediction: https://en.wikipedia.org/wiki/No_free_lunch_theorem, http://www.aihorizon.com/essays/generalai/no_free_lunch_machine_learning.htm, http://no-free-lunch.org/.  To be effective at prediction, the learning technique must embed some bias about what hypotheses/models are more likely.  A true-random generator has no bias and thus is useless.  A PRNG behaves like a true-random generator and thus will probably be useless (or, to the extent it has bias, its bias is towards distributions that are very unlikely to appear in nature).


Connected Components - Linear Decision Trees

Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ which is entirely in $S$ (this is known as path-connectedness). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence class of this relation. This generalizes the graphical definition which is more familiar to this audience.


Why is the type ∀t.t un-inhabited in System F?

The simplest proof is giving a model where types are interpreted as propositions, and terms as proofs, then observing that $\forall \alpha.\alpha$ is interpreted as the false proposition, so any $\cdot \vdash t : \forall \alpha.\alpha$ would be a proof of falsehood. It is important to remember that $\forall \alpha.\alpha$ is only uninhabited for sure in the empty context $\cdot$, in other contexts it may be trivially inhabited.

Concretely, first interpret each $A$ type with $n$ free type variables in the following way:

$$
\begin{alignat*}{2}
& [\![ A ]\!] && : \mathsf{Bool}^n \to \mathsf{Bool}\\
& [\![ \alpha ]\!]\,\gamma && := \text{$\alpha$-th component of $\gamma$}\\
& [\![ A \to B ]\!]\,\gamma && := [\![ A ]\!]\,\gamma \Rightarrow [\![ B ]\!]\,\gamma\\
& [\![ \forall \alpha.\,B]\!]\,\gamma && := [\![B]\!]\,(\mathsf{true},\,\gamma)\,\land\,[\![B]\!]\,(\mathsf{false},\,\gamma)
\end{alignat*}
$$

Interpret every typing context $\Gamma$ with $n$ free type variables as:

$$
\begin{alignat*}{2}
  & [\![\Gamma]\!] : \mathsf{Bool}^n\to \mathsf{Bool}\\
  & [\![\Gamma]\!]\,\gamma := \bigwedge\limits_{A\,\in\,\Gamma}\,[\![A]\!]\,\gamma
\end{alignat*}
$$

Then show for each $\Gamma \vdash t : A$ term, that for each truth valuation $\gamma : \mathsf{Bool}^n$, if $[\![\Gamma]\!]\,\gamma = \mathsf{true}$, then $[\![A]\!]\,\gamma = \mathsf{true}$. This can be done by induction on terms.

Now, $[\![\forall \alpha.\alpha]\!]$ with no free type variables evaluates to $\mathsf{false}$, since it's $\mathsf{true}$ when $\alpha$ is instantiated to $\mathsf{true}$, and $\mathsf{false}$ when it's instantiated to $\mathsf{false}$, and the conjunction of these is $\mathsf{false}$. Assuming $\cdot\vdash t : \forall \alpha.\alpha$, we have by the previous result that $[\![\forall \alpha.\alpha]\!]$ is $\mathsf{true}$, a contradiction, hence there is no $\cdot\vdash t : \forall \alpha.\alpha$.


Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?

Assuming you mean "polynomial in the size of the binary representation of K and M", then it is extremely unlikely, but proving that it is impossible will also be very difficult.
There are polynomial time algorithms for checking primality, but they would be applied to a number whose size is K, which is a lot bigger than checking a number whose size is the same as the size of K.


Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

For non-negative weights $0$ is a lower bound and thus sufficient. For arbitrary weights you can binary search in $[l,u]$, for a lower bound $l=\sum_{a\in A\mid d_a<0} d_a$ and an upper bound $u=\sum_{a\in A\mid d_a>0} d_a$ on the length of any simple path.


textbook on the human brain for computer scientists/machine learning professionals?

There is no "textbook" on this. However, there is a book! It is How to Create a Mind by Raymond Kurzweil, the director of engineering at Google. Excellent book that explains the brain from a computer-science perspective. It goes into a lot of detail.

Check out the intro sound bytes on Audible.

For a closer to the metal (i.e. actual implementations of models of the brain), check out Cognitive Architectures, such as ACT-R, Soar, CLARION, ICARUS, EPIC, LIDA, etc. Here is a survey.


Can a Turing Machine tell if an input string is a description of itself?

The answer is yes, and this is a standard application of the recursion theorem - the slogan for this theorem being, "you can assume at the beginning of your construction that you know what the index of the construction will be at the end."

Let me outline how it is applied in this case:

You have a description of the machine you want, with a "gap" - a point where you want to insert the code for the machine itself. This really defines a family of machines, where we have $M_k$ being the version where we stick in the number "$k$."

The process of building $M_k$, given $k$, is recursive; that is, the function sending $k$ to the index for $M_k$ is recursive.

Now on the face of it, that doesn't help since we just get an infinite regress: $M_0$ has index $5$, $M_5$ has index $17$, $M_{17}$ has index $2$, ... However, the recursion theorem lets us catch our tail. Let $f$ be the recursive function mentioned above, which sends $k$ to the index for $M_k$. Then by the recursion theorem, we get a fixed point for $f$: some $c$ such that the machine with index $c$ behaves identically to the machine with index $f(c)$.

But this means exactly that the machine $M_c$ - whose index is $f(c)$ - behaves as if it was given its own index! (Intuitively, it "thinks" it has index $c$, and that's good enough: index $c$ and index $f(c)$ are "the same.")


N-Grams - how to predict further into the future and how far can we predict?

There's no simple answer to "how far into the future can you predict?".  Obviously, the further you go, the less your ability to predict.  For English text, I would expect that ability to predict would decrease rapidly.

You asked if there's a better wya to do this.  You can of course consider a generalization of $n$-grams where you use the characters at positions $i-n+1,i-n+2,\dots,i-1,i$ to predict the character at position $i+k$ (instead of predicting the character at position $i+1$), for any fixed $k$.  This will probably perform worse the larger $k$ is.

You might also be interested in skipgrams.


The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case).

In this model, given a graph you would like to write one linear program, changing whose objective function gives you the right matching corresponding to any weight function on the given graph. This requirement results in the restriction that the feasible region of such an LP must project down to the matching polytope. The lower bound is not immediately applicable if you provide different LPs for different weights, or you use the objective function in a non-trivial way. (Note that in this model, we use the weights on the edges as the objective function without any modification)

Allowing different LPs for different weights obviously breaks the result: First solve the weighted problem and then produce a trivial LP whose feasible region contains exactly one point (the answer). This LP would trivially have small size.

Now, you can argue similarly that allowing weights to be manipulated arbitrarily allows you to "cheat" and write small LPs too.

The discussion about P-completeness of Linear Programming becomes interesting if you ask the following.

Q: Can you use Linear Programming to solve the matching problem in a "black box" fashion "with minimal extra computation"?

The answer in this case is yes, and the extra computation turns out to be just encoding the input graph in a trivial way as the objective function (by essentially taking the characteristic vector of edges with encoding digits +/-1 instead of 0/1). This extra computation seems reasonable and so the LP encoding of the matching problem in this case seems interesting. The LP in this case turns out to be of small size precisely because matching is in P and Linear Programming is P-complete.


If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive

Fixing $y$ in $R(x,y)$ results in a special case of the problem "whether $\langle x,y \rangle \in R$", and hence the latter should be no more harder than the general problem of deciding if $\langle x,y \rangle \in R$. So, intuitively if $R(x,y)$ is a recursive relation then $R(x,y_0)$ should also be recursive for some fixed $y_0$.

Formally, recall that a relation $R(x,y)$ is recursive if its characteristic function

$$ c_R(x,y) =  \begin{cases}
      1  & \text{ if } \langle x,y \rangle \in R \\
      0 & \text{ if } \langle x,y \rangle \notin R
\end{cases}
$$
is recursive.

Now assume that $R(x,y)$ is recursive. Then $c_R(x,y)$ is also recursive. Let $M(x,y)$ be a TM computing $c_R(x,y)$. For a fixed $y_0$ our new TM $M'(x)$ will take $x$, call $M(x, y_0)$ and return its value. Since $M(x,y)$ computes a recursive function (always returns $0$ or $1$), $M'(x)$ also computes a recursive function, namely $c_R(x,y_0)$. Thus $R(x,y_0)$ is recursive.


Exactly why the time taken by 'memory reads', is not considered while calculating time complexity of an algorithm?

People don't usually refer to the hard drive as "memory" though the term "external memory" is common in this area of the literature. As far as disk accesses are concerned, they are taken into account in the analysis of algorithms that are explicitly written to access disk. Some of the more popular models are the two-level external memory model, the parallel disk model, and the cache-oblivious model. There are also hierarchical memory models. Algorithms and Data Structures for External Memory particularly chapter 2 describes the parallel disk model in detail, briefly describes other external memory models, and provides pointers into the literature. Some of these ideas and results go back about half a century.


Proving some subsets of a regular languages to be regular languages

a) Proving NOPREFIX(L) is regular :
The idea is simple , for a string w ∈ NOPREFIX(L) , w must be in L , and no proper prefix of w is in L
So , if we have a DFA M for L , we run string w on M , changing M a bit ,  if M enters the accept state before the end of the input , then a proper prefix of w is accepted by L and so we reject , if not and we reach an accept state just by the end input we accept , of course if by the end of w we don't enter an accept state we reject since w is not in L an so not in NOPREFIX(L)
Now you may want to try constructing M' based on the above explanation , then check your answer
Proof :
Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOPREFIX(L) as follows :
Q' = Q
for r ∈ Q' , a ∈ Σ
δ'(r,a) = δ(r,a) , if r is not in F
δ'(r,a) = ∅  , if r  ∈ F
q0' = q0'
F' = F
Hopefully you can see how changes in δ' achieve our purpose , M' simulates M , till it reaches an accept state , if the input ends we accept ( note that w is not a proper prefix of w) since w ∈ L , and we did not encounter any accepted proper prefixes , but if we enter an accept state and the input is not yet finished we reject since this means that we encountered an accepted proper prefix
b) Proving  NOEXTEND(L) is regular
This is an easier one , for a string w ∈ NOEXTEND(L) , we need to make sure that no string wx ∈ L , x ∈ Σ^+ , so for w not to be a proper prefix of a string in L ,we need to make sure that no symbols could be added to w to form a string in L ,
Once again you may want to try M' that recognises NOEXTEND(L)
Proof :
Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOEXTEND(L) as follows :
Q' = Q
δ' = δ
q0' = q0'
F' = { q| there is no path from q to an accept state in F)
M' works exactly as M , when the string end we consider the  final state we reached q , if there is a path from q to any accept state in F ( the accept states of M) , then we reject since this means we can extend w by x to reach a string wx ∈ L , with x being the string of symbols on the path from q to accept state   , and thus w is a proper prefix of some string wx ∈ L , if there is no path from q to an accept state so w cannot be extended to form a string in L and thus we accept


Are there any CS-trees named after flora-trees?

Robert Tarjan defines the palm tree in "Depth-first search and linear graph algorithms" (1972):

  Let $P$ be a directed graph of two disjoint edge sets, denoted
  $v \rightarrow w$ and $v \overset{-}{\rightarrow} w$ respectively. If $P$
  satisfies the following properties:

  The subgraph $T$ containing the edges $v \rightarrow w$ is a
   spanning tree of $P$;
  Each edge not in $T$ connects a vertex with one of its ancestors in
   $T$.  The edges $v \overset{-}{\rightarrow} w$ are called the fronds of $P$.

e.g.,

He goes on to prove that the directed graph generated by a depth-first search of a connected graph is a palm tree.

In Collective Tree Spanners and Routing in AT-free Related Graphs, Dragan, Yan, and Corneil  construct a specific spanning tree that they call a willow-tree.


You may not be able to completely specify formally in a tractable way
the semantics of your functions, depending on what they are. But doing
some of the work, even incompletely may help you significantly with
optimizing your programs, since it may be enough to establish whatever
properties are needed for optimization.

The first thing you want to do is to type your functions. For this,
you probably want some kind of polymorphic typing (see ML or CAML),
using type variables, as some of the base types you operate on will be
left open.

Most of these function take several arguments, and (following the
discussion in comments with @Jake) you may want to consider what would
be a convenient order, and more to the point, whether you want them
curried (or currified) or not.

For example, if we note [a] the type for a list of elements of type
a, then you can define the function map as:

a function of two arguments, the first being a function from a to
b, and the second a list in [a], and returning a list in [b], i.e.
map: (a→b)×[a] →[b]
a function of one argument which is a function from a to
b, and returns a specialized mapping function that maps lists in [a]
to lists in [b], as specified by the argument to map, i.e.
map: (a→b) →([a]→[b])

The latter is a curried version of the former. They give you the
same computing power, but the curried one may be more convenient for
optimization (just my intuition) as it decomposes structures.

Then the kind of information that you may need may depend on the kind
of optimizations you intend to implement. Many types of optimizations
("strength reduction" is a typical example) may require knowing
algebraic properties of your functions. But that may also depend on
the algebraic properties of the types or type constructors used, such
as the existence of "identity element" with respect to some
operations (such as the empty list). I doubt your specification/formalization problem can be restricted to just your second order functions.

Typically, a relation such as:

head (map (f,l))= f(head(l)) may be very useful for some
 optimizations.

or more trivially:

map(f,[]) = [] where [] denote the empty list.

I do not recall all the literature on these issues. But you may want
to look at abstract data types, formal algebras, and the algebraic
techniques used in optimization.

There are probably other properties, less algebraic, that you may be
interested in defining and using.

An important aspect is also whether your function are purely
functional, or whether they have side effects. A map function could
possibly destroy the list given as argument, the result reusing the
same memory locations.