if (λ x . x x) has a type, then is the type system inconsistent? If a type system can assign a type to λ x . x x, or to the non-terminating (λx . x x) (λ x . x x), then is that system inconsistent as a consequence? Is every type under that system inhabited? Can you prove false?

Certainly, assigning a type to $\lambda x. x\ x$ is not enough for inconsistency: in system $F$, we can derive
$$ \lambda x.x\ x:(\forall X.X)\rightarrow (\forall X.X)$$

in a pretty straightforward way (this is a good exercise!). However, $(\lambda x.x\ x)(\lambda x.x\ x)$ cannot be well typed in this system, assuming $\omega$-consistency of 2nd order arithmetic, as this implies that all such well-typed terms are normalizing.

Furthermore, system $F$ is consistent. This follows from either normalization, as one can show that any term of type $\forall X.X$ cannot have a normal form, or a much simpler argument, in which each type is assigned a set, either $\varnothing$ or $\{\varnothing\}$ and it can be shown that all derivable types are assigned $\{\varnothing\}$, and $\forall X.X$ is assigned $\varnothing$ (and is therefore not derivable).

The latter argument can be carried out in first-order arithmetic. The fact that $\lambda x.x\ x$ can be well-typed in a consistent system can be seen as somewhat disturbing, and is a consequence of the systems' impredicativity. It shouldn't come as a surprise that some people question the trustworthiness of impredicative systems of logic. However, no inconsistencies have been found so far in such systems.

On the other hand, to be able to make the more general assertion that $(\lambda x.x\ x)(\lambda x.x\ x)$ cannot be well-typed in a consistent system, you need to have enough "logical structure" in your type system to be able to clearly define consistency. Then you need to show that a term without a head normal form (like the one above) can have any type, which is also not obvious!

More details can be found in my answer to a related question: https://cstheory.stackexchange.com/a/31321/3984


Simulate a regular Turing Machine with one that cannot write blanks Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?

To simulate a Turing machine $M$ that can write blanks with a Turing machine $M'$ that can't, just give $M'$ an extra character in its alphabet. Whenever $M$ writes a blank, $M'$ writes this new character and, whenever $M'$ sees the blank or the new character, it does what $M$ would do if it saw the blank.


What mathmatical model shall be used for describing P2P processes interaction? I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three logic applications and 2xN heavy calculation applications. There are external web clients, which connect to logic applications, but for now, we do not care for them. Therefore, server side connected applications:

They interact via heavily extended proprietary ZeroMQ analog middleware - so there is a finite set of communication patterns between applications.
There is a protocol (Protobuf based) via which applications encode messages. Different types of messages are sent on same communication channels (for example 10 types of requests with 10 types of responses for each Request-Reply channel)

I wonder if there is a mathematical model in terms of which I can describe my Peer to peer services system. Of course, I need a model that can be useful: one that after its creation I would be capable to gain some new knowledge about properties of my distributed application.

I looked at a few

Petri networks and they can provide reachability, liveness
Queueing theory, which generally seems to lead to Stochastic Petri Nets

After few days of research, my small brain collapsed because I need a Colored Hierarchical Stochastic Petri Net and all I would get from it would be reachability and liveness of components and connections may be also maximal/normal messages passing volumes.

To create such model timing, message type’s interaction and publishing stats would be required as well as directions of message streams. Computational logic can stay as a black box.

So I wonder - is there any other mathematical model which could provide more data on system behavior in terms of prediction/reasoning, what data it would require?

If you're looking for a single model that describes all relevant aspects of your system, you'll have a hard time. And building the model will take as much effort as implementing the system itself, if not more. Therefore, break the system down into different aspects, and consider different modelling techniques for each. Examples for aspects might be:

The protocol between two of the peers. This could detect deadlocks or pointless messages in the protocol.
Repeat for every combination of two types of peers.
Behavior of a single peer as it connects with different types of peers.
Could there be problems if a message from peer type X comes in while processing another message from peer type Y?
Behavior of the network as peers come and go. Will it stay connected?
Here, you'd just model "peer connects" and "peer disconnects", rather than the sequence of messages for connecting and disconnecting.
Performance depending on the number of peers of each type.
...


What is the relation between parsing languages and checking languages? I have looked at a number of textbooks on computability theory. They typically have the following form:

Define a language class (regular, context-free, context-sensitive, recursively enumerable)
Define an automaton that recognizes the class (finite automaton, pushdown automaton, linear-bounded automaton, turing machine)

However, another fundamental question is how to parse a language. I have not found an treatment of parsing as a computational problem in these textbooks.

Is there a simple relation between an automaton that recognizes a language, and an automaton that parses the language (and outputs a parse tree)?

There is a simple relation between the two problems, but it goes in only one side: if you can parse, then you can recognize. Indeed, if you run the parser and it outputs failure, then the input is not in the language; if the parser produces a parse tree, the input is in the language.

Note, however, that a parser and a recognizer are not only solving different problems, but are also given different specs. A recognizer is given a language in some abstract form. In contrast, a parser is given a grammar, which not only implicitly defines a language, but also instructs the parser how to convert a valid input into a parse tree. Since the same language can have many equivalent grammars, it's not clear what it even means to convert a recognizer to a parser – what grammar should the parser use?

Why are recognizers interesting, then? Precisely because of the one-sided connection, which states that a parser can be converted to a recognizer. This relation implies that if your language is hard to recognize, then you won't be able to parse it (using a certain class of algorithms).


What does a faster algorithm mean in theoretical computer science? If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?

  Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?

No, an algorithm running in time $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is not necessarily considered an improvement. For example, suppose that $f(n) = n$ and $g(n) = 1/n$. Then $O(f(n)/g(n)) = O(n^2)$ is a worse time bound than $O(f(n)) = O(n)$.

In order to improve upon an algorithm running in time $f(n)$, you need to come up with an algorithm running in time $o(f(n))$, that is, in time $g(n)$ for some function $g(n) = o(f(n))$.

If all you know is that an algorithm runs in time $O(f(n))$, then it is not clear whether an algorithm running in time $O(g(n))$ is an improvement, whatever $f(n),g(n)$ are. This is because big O is only an upper bound on the running time. Instead, it is common to consider the worst-case time complexity, and to estimate it as a big $\Theta$ rather than just as a big $O$.


How does one make an unambiguous context-free grammar for arithmetic expressions? Say I have a context-free grammar defined by the following rule.

$$
\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x
$$

This grammar is ambiguous since, for instance, I can generate the string $x + x \times x$ via more than 1 leftmost derivation.

How could I make this grammar unambiguous? Should I make sure that no $\langle EXPR\rangle + \langle EXPR\rangle$ is evaluated after a $\langle EXPR\rangle \times \langle EXPR\rangle$ as such:

$$
\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle MUL\_EXPR\rangle \times \langle MUL\_EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\
\langle MUL\_EXPR \rangle \rightarrow \langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\
$$

Indeed you made a step to resolve ambiguity, but your solution does not give a fully unmabiguous grammar yet. The string $x+x+x$ can be parsed in two different ways, like $x + [x+x]$ or like $[x+x]+x$, where the brackets indicate parses. As far as I see your solution resolves semantical ambiguities (it fixes the relative order of + and x) but not the syntactical ambiguity. So obtaining an umambiguous grammar is not the only goal for an example like this: we want to respect meaning (here operator precedence). (Perhaps there is more official terminology for that)

Your example is a familiar one, and is used in wikipedia/Syntax diagram:

<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"

Probably you will know that not every grammar has an unambiguous equivalent, so no general approach is possible.


Calculating the information density of an encoding system How do I calculate the information density of an encoding system?

This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major paper on encoding data in DNA after Church's). All of them mention the information density of their encoding system, which I understand to be given in units along the lines of bits or bytes per nucleotide.

From looking around on the internet and asking around in the hbar (the Physics chat) I understand the absolute basics: that one creates a model that gives the probability distribution over the possible messages in your system (say, English, or ASCII) and then from there calculate the average information density of a message using that distribution.

Unfortunately, as a complete beginner, I don't know how to do any of those things. I'd like to understand that process and in the end be able to do my own calculations. Any resources would be helpful, of course, but I was advised to ask this question here.

Tl;dr: how do you calculate the information density of a system?

When people talk about information density in this context, they probably mean that the information density is

$$\text{density} = {n \over m}$$

where $m$ is the number of nucleotides needed to encode $n$ bits.  Here the assumption is that the $n$ bits come from the uniform random distribution (i.e., all $2^n$ possibilities are equally likely).  Implicitly, we are taking $n$ to be very large, or taking the limiting value of the density as $n \to \infty$.

So, think of it this way.  Imagine we had $n = $ 1 million bits.  How many nucleotides would the encoding scheme need, to encode those 1 million bits, on average?  Call that $m$.  Now divide $n$ by $m$; that's your information density.

The way to figure out the average number of nucleotides needed to encode a one-million-bit input will depend on the particular encoding scheme.


Removing identical variables in CFG Unit Productions Productions of the form A-> A are removed immediately, but what if the production is of the form A -> AA?

example:
A -> AA | a

In you example the production A->AA can not be removed. If that production is removed then the language described by the grammar will change. But in case of a production like A->A, the removal will not affect the language described by the Grammar.


How does a dual core microprocessors run so many programs? I have a laptop with Intel dual core and it runs, the OS windows, and many application from Opera, age of empires, word, excel etc open at once just fine. If it only has 2 cores, how can so many programs work? How exactly does it manage to do all these? Does operating system have something to with it?

It's great that you're curious. A simplified explanation follows with a few links to delve into:

All of the programs running in parallel is actually an illusion that is created by the OS.

Even if we have a uniprocessor system, the OS can still achieve the same thing.
For multiple programs running on the system, OS creates separate processes.
Separate processes could then time-share the processor(s) available.

Since a processor is very fast (gauged by frequency), it can switch back and forth among multiple processes that may be active in a particular time period (we're talking about the span of time in microseconds/milliseconds). Overall, this gives the user an illusion that the programs are running in parallel. This technique is called Multi-tasking.

Now, adding more processors(let's say one in your case) allows the OS to also use the processors in parallel. In this case, let's say the OS chooses to run half of the programs on one processor and the other half on another processor (in reality, it's a little more complex). Individual processors are still used by the running processes in a time-sharing fashion but since there are two processors, overall the performance of your running programs improve. Using multiple processors in parallel is called Multi-processing.

Although the definitions can be a little confusing, this overall implementation idea remains the same.


Example of an algorithm that lacks a proof of correctness We have Hoare logic. Why is it still possible that an algorithm is right but there is no proof that it's correct? Suppose the algorithm is expressed in C. Then we can argue step by step that it's doing what it's supposed to do.
So my question is:

Give me an example of an algorithm that's right but does not have a proof of correctness.

EDIT: I think a little background can help clarify where I'm going. Let me quote Scott Aaronson:

Since the 1970s, there's been speculation that P $\ne$ NP might be independent (that is, neither provable nor disprovable) from the standard axiom systems for mathematics, such as Zermelo-Fraenkel set theory. To be clear, this would mean that either

a polynomial-time algorithm for NP-complete problems doesn't exist, but we can never prove it (at least not in our usual formal systems), or else

a polynomial-time algorithm for NP-complete problems does exist, but either we can never prove that it works, or we can never prove that it halts in polynomial time.

I'm referring to the second possibility. Since Aaronson can so confidently list it as a possibility, I think there must be an existing example of type 2. That's why I'm asking this question. But it seems a quick and clear answer is not in view.

Here is an algorithm for the identity function:

Input: $n$
Check if the $n$th binary string encodes a proof of $0 > 1$ in ZFC, and if so, output $n+1$
Otherwise, output $n$

Most people suspect this algorithm computes the identity function, but we don't know, and we can't prove it in the commonly accepted framework for mathematics, ZFC.


interval scheduling algorithm can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this video and i am not able to understand the proof

Algorithm - we will accept the request that finishes first. This is also quite a natural idea, we ensure
that our resource becomes free as soon as possible.In this way we can maximize the time left to satisfy other requests.

let O is the set of optimal intervals and A is the set of intervals produced by our algorithm

formally:
   Initially let R be the set of all requests, and let A be empty
     While R is not yet empty
        Choose a request i ∈ R that has the smallest finishing time
        Add request i to A
        Delete all requests from R that are not compatible with request i
     EndWhile
   Return the set A as the set of accepted requests

Let i1,..., ik be the set
of requests in A in the order they were added to A

similarly let j1,......jm be the set of requests in O in the order they were added to O

we have to show that k $=$ m , that is both the set have same number of intervals

we want to show that our greedy rule “stays ahead” which means that each of its intervals
finishes at least as soon as the corresponding interval in the set O.

which means f(ik) $\leq$ f(jK)

here f(ik) denotes the finishing time of a interval i

this statement can easily be proved using induction.
base case here is the very first interval
 which is f(i1) $\leq$ f(j1)

Optimality -
Now let's assume that k < m which means there is a interval in O which is not selected by our algorithm

let the index of that interval is k+1

we know that f(ik$+$1) $\leq$ f(jk$+$1)        -   based on the statement we just proved

also f(ik) $\leq$ f(ik$+$1)  and  f(jk) $\leq$ f(jk$+$1)      -   As the intervals are ordered by their finishing time

clearly jk$+$1 interval was available after jk finished but we know that ik finished before jk,
so this means that an interval was available for selection after ik finished but our algorithm did not select it, but this can not happen
as our algorithm will only stop when there are no intervals left.

so our assumption was wrong which means k = m

PS - I suggest reading the greedy algorithm section from the "Algorithm & Design" by Kleinberg and tardos

here is a link to a soft copy -
http://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf


Branch predictor question If the branch predictor is placed in the fetch stage then how does it know that the current instruction is actually a branch before trying to predict its outcome? Is some (very little) decoding already done in the fetch stage before going to the actual decode stage?

There is no decoding done in the fetch stage.  The fetch stage relies on the Branch Target Buffer (BTB) to tell it which instruction addresses have had taken branches in the past.

The BTB is a small highly associative structure.  It performs two functions.  First it tells you which instructions are and are not branches.  If the current program counter (PC) is in the BTB then the instruction pointed to by the PC is a branch, and the BTB will tell us the target of that branch and the branch predictor will give us a guess about whether the branch is taken or not taken.

If the current program counter in not in the BTB then either (a) the current instruction is not a branch or (b) we have never seen this instruction before (and don't know whether or not it is a branch, but we'll assume it is not or (c) the current instruction is a branch, but we've never seen the branch taken, so we've never put it in the BTB.

This last function (branches that are never taken are never put in the BTB) makes the BTB actually a very effective branch predictor.  Branches that have never been taken are unlikely to be taken in the future, and the BTB predicts this correctly.  Branches that have been taken at least once in the recent pass are slightly more likely than not to be taken in the future, and the BTB reflects this as well.

The BTB effect was rarely taken into account in academic branch predictor research done at the end of the 1990s (nor is it taken into account in the statistics in most textbooks).  For most programs on most architectures the BTB actually filters out a significant number of branches (on the order of 25%) because they are never taken or rarely taken.  For those 25% of branches you essentially get a 99% accurate branch prediction for free.  The "real" branch predictor needs focus, then, only on the other 75% of branches.


Does O(f(n)) + O(g(n)) = O(max{f(n), g(n)})? A question from a lecture of mine.
The way I see it, while summing sets is meaningless, O(f(n)) + O(g(n)) is obviously limited from above by the greatest function in either, which means that I practically take the maximum of O(f(n)) and the maximum O(g(n)), and claim that either is the maximal one, or they are equal.

Would this be a legitimate claim in an exam?

One way to read this "identity" is as follows:

  If $a = O(f(n))$ and $b = O(g(n))$ then $a+b = O(\max\{f(n),g(n)\})$.

This indeed holds, as you can prove using the definition of big O.

There is another possible interpretation:

  $\{ a + b : a = O(f(n)), \; b = O(g(n)) \} = \{ c : c = O(\max\{f(n),g(n)\})\}$.

This also holds, as you van prove using the definition.

Whether it is a legitimate claim in an exam is up to your professor. It is definitely a legitimate claim in a paper.


Reduction from $HALT$ to $A_{TM}$ I know the reduction to from $A_{TM}$ to $HALT$. But is
the following reduction from $HALT$ to $A_{TM}$ correct?

We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$.
The following TM $F$ calculates the reduction $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

I think the line if T accepts or rejects, *accept* is correct, but it would be great if someone could check this.

Edit: I found the following slides, but I don't think the construction in there is correct: http://slideplayer.com/slide/13791105/

There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (more specific link here) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction.

While many-one reductions are generally the default notion in complexity theory, Turing reductions and the resulting degree structure are the default in computability theory. Note that if all I want to do is prove the undecidability of some set, a Turing reduction from some known-to-be-undecidable set is sufficient.

First, let's explicitly recall the definitions of the languages involved:

$A_{TM}=\{\langle M,w\rangle: M$ halts and accepts on input $w\}$.
$HALT=\{\langle M,w\rangle: M$ halts on input $w\}$.

Your proposed reduction of $HALT$ to $A_{TM}$ is correct: given $M$, we can computably build a new machine $\hat{M}$ which accepts precisely those strings on which $M$ halts. (Basically, just replace all the "reject" states in $M$ by "accept" states.)

Now let's look at the other reduction which you linked to (more specific link here).

Basically, rather than going to "all halting states accept" the linked argument considers separately:

the original machine, and
the "contrary" machine which accepts exactly when the original one rejects and vice-versa.

An affirmative answer for either case in $A_{TM}$ ensures an affirmative answer for the original machine in $HALT$.

Off the top of my head I see no reason to do this rather than follow your argument, especially because it yields a weaker result, but it is correct and is enough to prove the broader claim in the slides, namely that $A_{TM}$ is undecidable.


Evolutionary algorithm for the Physical Travelling Salesman Problem I want to solve the Physical Travelling Salesman Problem using an evolutionary algorithm.

The objective of the PTSP is to visit the maximum number of waypoints of the map in the minimum number of time steps.
The map takes the form of a two-dimensional board, where ten waypoints are scattered around and multiple obstacles are present.

Now, I have a way to run random games and create "population" — a list of waypoints in the order we visit them.
I need some idea how to do the crossover. I mean, how to create the next generation.
I saw ideas, but they take in account that each gene contains all the waypoints on the map. (Take a random part from parent1 and take the waypoints that do not appear in parent1 from parent2 in the order they appear in parent2).
What to do in case a gene contains just part of the waypoints?

Have a look at this survey on crossover operators for TSP

It gives you the history of development on this area as well.

List of operators covered:

Partially Mapped Crossover (PMX) [Goldberg, 1985]
Order Crossover (OX) [Davis, 1985]
Edge Crossover (EX) [Whitley, 1989]
Subtour Exchange Crossover (SXX) [Yamamura, 1992]
Edge Exchange Crossover (EXX) [Maekawa, 1996]
Edge Assembly Crossover (EAX) [Nagata, 1997]
Partition Crossover (PX) [Whitley, 2009]


Find the closest point in a point cloud in a near equivalent point cloud I'm having a hard time wrapping my head around an algorithm, and not really sure if such a problem is known, common and possibly named, or if this is somewhat unique.
I have 2 different clouds of points (2D). I need to generate an index map from one to the other by proximity. Points that are closest should map to each other. This part isn't that hard.
The hard part is that each "to" point should only be used by one "from" point.
For example, let's say these are my "from" points: ([x, y] // index)
[
  [1, 10],  // 0
  [10, 10], // 1
  [19, 10], // 2
]

And these are my "to" points:
[
  [11, 10], // 0
  [9, 10],  // 1
  [10, 10], // 2
]

Then I would expect the following index mapping (fromIndex: toIndex)
{
  0: 1, // [1,10] -> [9,10]
  1: 2, // [10,10 -> [10,10]
  2: 0, // [19,10] -> [11,10]
}

In this example, all three new points are closest to [10,10], but...

The new point [10,10] (index 2) is zero distance from to old point [10,10] (index 1), so it just be assigned that index.
The new point [11,10] (index 0) is 1 distance to the old point [10,10] (index 1), and 8 distance from the old point [19,10] (index 2). index 1 is closest, but since another point is closer, the second closest point is chosen (index 2).

Finding the closest point is easy, but how would I go about finding the closest point that doesn't also have another point that's even closer, and so it should find the next closest point, which also doesn't have another point closer to that, and if does find the next closest point which... (did I go recursive?)
And obviously this would be run on point clouds of large number (up to about a max of about 50,000 at the moment)
How would I go about developing this algorithm?

This problem is known as Euclidean minimum cost perfect matching, I have linked a survey by Sayan Bhattacharya that contains various references to algorithms, both exact and approximations.
If you wish to solve this problem for $n \approx 50000$, I would skip the exact solutions entirely and go straight to the approximations.


What defines negative and non-negative type operators? I'm working through some exercises in Robert Harper's "Practical Foundations for Programming Languages" and I'm not certain I understand what makes an occurrence of a type operator non-negative or negative in the general case.

I understand that positive type operators occur in the range of a function type, and that negative type operators occur in the domain of a function type, but I'm not sure how to generalize the additional category of non-negative based on the single given example t. (t -> bool) -> bool, which is only described as an occurrence in the domain of the domain without any mention of the interactions of further nesting. That also complicated my understanding of what makes an occurrence negative (must the occurrence on the left be positive, or just non-negative?), so now I'm just plain not sure what defines non-negative and negative type operators in the context of a function type.

For anybody who owns the book (second edition) this is chapter 14.

I can explain the mathematical background. Suppose we have a type operator $F$ that takes a type $A$ to a type $F(A)$, and we want to extend it so that it also maps functions. It should take a function $f : A \to B$ to a function $F(f) : F(A) \to F(B)$. This can often be done, for example if
$$F(X) = X + (C \to X)$$
for a fixed $C$, then we may define
$$F(f) : A + (C \to A) \to B + (C \to B)$$
in a natural way as
\begin{align*}
F(f)(\mathtt{inl}(a)) &= \mathtt{inl}(f(a)) \\
F(f)(\mathtt{inr}(g)) &= \mathtt{inr}(f \circ g)
\end{align*}
We say that $F$ acts covariantly on functions.

But sometimes the direction gets reversed! Consider
$$F(X) = X \to C$$
for a fixed type $C$. Then $f : A \to B$ can be mapped to
$$F(f) : (B \to C) \to (B \to A)$$
by
$$F(f) = \lambda g . g \circ f.$$
This time the direction was reversed. We say that $F$ acts contravariantly on functions.

In some cases we are stuck, for instance if $F$ mixes things up. An example would be $F(X) = X + (X \to C)$.

If $F$ takes several arguments it may act covariantly on some of them and contravariantly on others.

Covariance and contravariance are important mathematical concepts which show up in many places: category theory, physics, analysis, you name it.

The positive and negative occurrences of a type variable in a type expression tell you whether the corresponding type constructor acts covariantly (positive) or contravariantly (negative) in that position.

For example, in $F(X) = (X \to C) \to C$ we have a positive occurrence of $X$, and indeed $F$ acts on $f : A \to B$ covariantly to give $F(f) : F(A) \to F(B)$ defined by
$$F(f) = \lambda \phi : (A \to C) \to C . \lambda g : B \to C . \phi(g \circ f).$$


Efficiently labelling training data in machine learning Obviously it always depends on the specific case. However, my question is how to label data efficiently without writing a source code from scratch which solves the final problem itself?

For example, suppose that I want to use the $k$-Nearest Neighbours algorithm to classify tables from images according to their shape (square tables, rectangular tables, round tables).

For this purpose, I need to find let's say at least 500 images of various tables and then label them.

However, if I do not want to label them manually then I must write extensively a program to do this which essentially is the program I would like to have overall.

In other words, there is no point in writing from scratch an algorithm for accurately labeling data if I want to use machine learning finally because then this algorithm would solve my overall problem without machine learning. However, it is obvious that this algorithm would be very difficult to write to cover all the possible cases e.g. of tables from various images etc.

So how can I label data quickly without writing so many source code lines?

You can't.  You can't squeeze blood out of a stone.  There's no such thing as a free lunch.  You can't get something from nothing.  If you want labelled images, you will need to label them yourself, or find some existing data set that comes with labels.  There are no shortcuts.

Yes, this is tedious and labor-intensive.  This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, we often spend the majority of our time (or more!) just assembling data sets, and only a small fraction on the actual learning algorithms themselves.

I know you could do various shortcuts, like trying to write a quick program to label them.  But if that program makes mistakes, you'll just be training your machine learning algorithm to make the same mistakes -- so that's not actually helpful.

If you want to reduce the amount of labelling effort, there are ways to reduce the effort -- but still they will require a significant amount of manual labelling.  Nothing comes for free.  For instance, you can use active learning algorithms to identify which instances to label.  A simple example of that is to manually label a few hundred images as your initial training set, train a classifier, apply it to all remaining images, pick out the 20 images that the classifier is least confident on, manually label those 20 images, add them to the training set, and repeat.  (This is an application of uncertainty sampling.)  There are other, more sophisticated methods out there as well.

Another plausible approach is to somehow cluster the images, then manually label a few images from each cluster.  This has issues, though, as you'll need some reasonable way to cluster the images, and that might be a non-trivial task.  (One possible approach for clustering is to take some existing, pre-trained ImageNet classifier -- e.g., VGG, Inception, ResNet, etc. -- throw away the last layer or last two layers, and use the output before those layers as the input to some clustering algorithm like k-means.  Doing k-means clustering directly on the raw image probably won't work well, but if you do it on the vector of activation values at some deep layer near the end of a good pre-trained classifier, then you might get better results.)

Finally, we often use data augmentation to make the classifier more robust.  For instance, for each image in the training set, we might generate 10 more copies, where each copy is rotated or translated or cropped by a random amount, and add that to the training set.  This tends to help make the classifier more robust to changes in orientation or pose -- but it doesn't give you something for nothing.  You still need a large training set that contains many different kinds of tables.


Question about growth rates of functions involving n and logn I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $o$, $\omega$, $\Theta$ that would best describe the relationship between two functions $f(n) = (\log n)^{100} + n^{0.01}$ and $g(n) = (\log n)^{50} + n^{0.05}$. Intuitively, it seems like $f(n) \in o(g(n))$ because the extra $n^{0.04}$ in $g(n)$ grows much faster than the $\log^{50} n$ in $f(n)$. However, I am not really sure how to prove this using first principles. Could anyone provide any suggestions? Thanks in advance.

There exists some $n_0 > 0$ such that $\log n \le n^{0.0001}$ for all $n \ge n_0$.
This can be seen, e.g., by taking the limit:
$$
\lim_{n \to \infty} \frac{\log n}{n^{0.0001}} =
\lim_{n \to \infty} \frac{10000}{ n^{0.0001}} = 0.
$$

This means that, for $n \ge n_0$,
$$
f(n) = \log^{100} n + n^{0.01} \le  \left( n^{0.0001} \right)^{100} + n^{0.01} = 2n^{0.01}.
$$

Therefore, using the fact that $g(n) \ge n^{0.05}$:
$$
\lim_{n \to \infty} \frac{f(n)}{g(n)} \le
\lim_{n \to \infty} \frac{2n^{0.01}}{n^{0.05}} =
\lim_{n \to \infty} \frac{2}{n^{0.04}} =
0,
$$
implying that $f(n)=o(g(n)).$


In Hindley-Milner system, how can I prove that let id=\x.x in id id is well-typed? I am trying to infer the type and prove that this is well-typed:

let $f =\lambda x.x$ in $f f$

Obviously the $f$ is the identity function, so it's the same as

let $id =\lambda x.x$ in $id$ $id$

I am trying to use these rules to infer the type, going bottom-up:

First I am using (T-LET') and on the left-hand side it's easy to show that $\lambda x.x$ is of type $\alpha \rightarrow \alpha$.

However, I have a trouble with the right hand side. Can someone please help me how to finish this?

If I understand you question correctly, you are wondering how the typing judgment $f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \beta$ can be proved, where $\beta$ is some (yet unknown) type.

As we are dealing with an application, the only rule that applies is T-App, so we end up with the following (partial) typing derivation, where $\gamma$ is yet another (unknown) type.
$$ \dfrac{\dfrac{\dfrac{}{x : \alpha \vdash x : \alpha}}
{\vdash \lambda x.x : \alpha \to \alpha} \quad\quad
\dfrac{f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma \to \beta \quad\quad f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma}
{f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \beta}}
{\vdash let \; f = \lambda x.x \;\; in \;\; f\;f : \beta} $$

Now, to complete the two open branches of the derivation, the only possibility is to use the T-Var rule, which has two preconditions. Applying it in the left branch, you can easily see that $\gamma$ must actually be $\beta$. And similarly, applying the T-Var rule in the right branch, you learn that $\gamma$ (or rather $\beta$) must be an arrow type of the form $\delta \to \delta$. So in the end, you obtain the following derivation (omitting the "$f : \forall \alpha.\alpha\to\alpha \in f : \forall \alpha. \alpha \to \alpha$") for the second premise of the T-Let rule.
$$ \dfrac{\dfrac{\forall \alpha.\alpha\to\alpha \subseteq (\delta \to \delta) \to (\delta \to \delta)}{f : \forall \alpha.\alpha \to \alpha \vdash f : (\delta \to \delta) \to (\delta \to \delta)} \quad\quad \dfrac{\forall \alpha.\alpha\to\alpha \subseteq \delta \to \delta}{f : \forall \alpha.\alpha \to \alpha \vdash f : \delta \to \delta}}
{f : \forall \alpha. \alpha \to \alpha \vdash f\;f : \delta \to \delta}$$

Note that the conclusion of the full derivation then becomes $\vdash let \; f = \lambda x.x \;\; in \;\; f\;f : \delta \to \delta$.


Is it incorrect too say that this function problem cannot be in $FNP$? Decision Problem:
Is $2^k$ + $M$ NOT a prime?
$K$ and $M$ are our inputs represented as integers.
Function Variant: Output the result of $2^k$ + $m$
We can consider, $M$ = $0$.
Proof that calculating 2^n requires an exponential amount of digits as the result
Question
Is it true that a non-deterministic machine cannot output $2^n$ (exponential) digits in polynomial time?
Does this mean that the problem is not in $FNP$?

When we say that an algorithm runs in polynomial time, we mean that its running time is at most a polynomial of the length of the input.  I assume the input is an integer $n$.  The usual way to represent integers is in binary; then the integer $n$ requires $\lg n$ bits to represent.  Therefore, a polynomial-time algorithm will have a running time that is at most $p(\lg n)$, where $p$ is some polynomial.
In each step of computation, the algorithm can output at most one item (e.g., $O(1)$ bits of output).  So, an algorithm with polynomial running time $p(\lg n)$ can output at most $p(\lg n)$ digits of output, for some polynomial $p$.  You can think of this as at most $(\lg n)^c$ digits of output, for some constant $c$ (the constant $c$ will depend on the algorithm).
Now, $2^n$ is asymptotically much larger than $(\lg n)^c$.  So, no, a polynomial-time machine cannot $2^n$ digits, when given $n$ as input.
What if the machine is non-deterministic?  The same is still true.  Non-deterministic means that there are multiple possible branches that the computation could follow.  But for each branch, it's still true that the length of the output can be no longer than the number of steps of computation.  So, each branch of the non-deterministic computation is limited to outputting at most $(\lg n)^c$ digits.
You might be wondering, what is the output of a non-deterministic machine?  Well, that's not a well-defined question.  Instead, for a non-deterministic machine, we can talk about the set of possible outputs.  If it is a polynomial-time machine, then there are a set of possible outputs, but they will all be polynomial in length.  So, a string of $2^n$ digits cannot be among the set of possible outputs; it's too long.
I sense that you are somewhat new to computational complexity.  I suggest that you try to avoid thinking about "function" complexity classes until you are really solid on the "decision" complexity classes.  I find the decision classes easier to think about, and the function classes harder to think about.
Is the problem in FNP?  Well, probably it will be most useful to refer to the definition of FNP.  I'm out of time to look that up right now and check it carefully, but I expect you're going to find that the answer is 'no', because the definition requires (explicitly or implicitly) that the length of the output be at most a polynomial in the length of the input.


Why is this youtuber applying comparing two functions with O(n^2), by applying a contant to one of the functions? Here is the video in question:https://www.youtube.com/watch?v=BpiMRyWoDu0&t=131s
F(n) and g(n) are both equal to each other since they both have a time complexity of n^2
What's the point of applying the constant c to g(n) to make it 2n^2? What is this trying to show us?
Additionally, why does the inequality include 'equal to'? When will 2n^2 ever be equal to n^2 + n + 3?
Further more, why has he written n >= 4? Where did the 4 come from? I understand why he wrote n >= 3 because n(n-1)is the same as n for time complexity purposes, therefore this becomes n >= 3

Look up the definition of big-O. It states that $f=O(g)\iff \exists c>0:\exists n_0\in\mathbb{N}:\forall n>n_0:f(n)\le cg(n)$


Reasoning on Efficiency (2) Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective one is than the other.

Is there a yard stick that can be applied to ALL algorithms, with ALL time complexities, that can be used to evaluate the efficiency of two algorithms?

I actually developed a method for this, but it applies only to polynomial algorithms.

MY METHOD.

  Suppose we want to compare two algorithms for accomplishing a task $f_i(n), g_i(n)$. $f_i(n) = o\left(g_i(n)\right)$
  A simple way to compare $f_i$ and $g_i$, is to find their ratio $r_i(n)$
  $$r_i(n) = \frac{g_i(n)}{f_i(n))}$$
  Express $r_i(n)$ as a polynomial of ,$n$.
  $$r_i(n) = n^{k}, \{k: k \in \Bbb R\}$$
  $$m = \lceil{k}\rceil$$

  $R_i(n) = m^{th}$ derivative of $r_i(n)$.
  It follows that $R(n)$ is a constant.

My method works nicely for polynomial algorithms, but is completely useless for other time complexities. Is there a more effective yardstick? One that applies to all complexities?

The concepts of asymptotic running time analysis and Landau notation already provide a way to compare the asymptotic running time of two algorithms, as long as (a) you are happy to ignore constant factors, (b) only care about asymptotics (limiting behavior as problem size gets large), and (c) you want to evaluate them according to their worst-case running time.  It sounds like you are happy with (a), (b), and (c), so you should be happy with existing tools.  They do tell you how much more efficient one algorithm is than the other.  You just might not have appreciated yet how to fully use these mathematical tools and concepts, which is understandable.

In particular, if we can express the running time of algorithm A as $\Theta(f(n))$ and the running time of algorithm B as $\Theta(g(n))$, we already know how to compare them.  We know that the ratio of their running time is $\Theta(f(n)/g(n))$.  In particular:

If $f(n)/g(n) = \Theta(1)$, we know that their asymptotic worst-case running times are equivalent.
If $f(n)/g(n) = o(1)$ (i.e., $f(n) = o(g(n))$), we know that A is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(f(n)/g(n))$.
If $f(n)/g(n) = \Omega(1)$ (i.e., $f(n) = \Omega(g(n))$, or equivalently, $g(n) = o(f(n))$), we know that B is asymptotically faster, and we can measure asymptotically how much faster: it is faster by a factor of $\Theta(g(n)/f(n))$.

You might want to read How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?,  Sorting functions by asymptotic growth,  How do O and Ω relate to worst and best case?, and Justification for neglecting constants in Big O.  That will give you some essential background to help you understand how these concepts fit in.

(I'm simplifying a bit, and casting this at the level that it sounds like you're ready to absorb.  Once you understand the basics, read Are the functions always asymptotically comparable? if you want to read some more precise statements -- but beware that right now this might just cause more confusion than it's worth.)


How to prove that a binary heap can't be sorted with complexity that better than O(nlogn) I am trying to prove that you can't sort binary heap with better complexity than O(nlogn).
We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and  i know nothing about the items in the heap (except its a heap) so you  can't use radix sort or linear sort.
Problem is i feel like its not enough to say this things.
I don't know how i am supposed to prove it and i am searching for help.

A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows:

Construct a heap $H$ from $S$.
Execute $A$ with input $H$.

Such an algorithm requires time $O(n) + o(n \log n) \in o(n \log n)$ and hence it contradicts the $\Omega(n \log n)$ lower bound on comparison-based sorting algorithm. Therefore, algorithm $A$ cannot exist.


What is Unique Coverage Problem? I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to D.W for pointing out Exact Cover problem.

  Given
            a universe $U = \{ e_1, e_2, \dots, e_n\}$ of n elements and
            given a collection $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ of subsets of $U$
                such that $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$, is equal to $U$.
   Exact cover is a decisional problem of finding if there exists a sub-collection of subsets $\mathcal{S^{'}} \subseteq \mathcal{S}$, which can cover the Universe $U$ and each element $e \in U$ is contained exactly in one subset $s \in \mathcal{S^{'}}$.
  Unique coverage problem is to find
            a sub-collection $\mathcal{S}^{'} \subseteq \mathcal{S}$,
            such that, pairwise intersection of $s \in \mathcal{S^{'}} = \phi$ and cardinality of  $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$ is maximum.

My questions are,

Are the definitions written above correct?
Is the Unique Cover Problem a computational version of Exact Cover? (Exact cover requires universe $U$ to be completely covered, while Unique cover problem tries to maximize the cover of universe $U$).

From this video,I got the following example and answer for this example as 6, at duration 11:46.

  $U = \{1,2,3,4,5,6,7,8\}$

  $S_1 = \{1,2,5 \}$; $S_3 = \{1,5,6,7\}$
  $S_2 = \{1,3,8 \}$; $S_4 = \{2,4,6,8\}$

It is also mentioned in the video that the answer is 6 and its when unique cover is $\{S_3, S_4\}$, but $\{S_3 \cap S_4\} = \{6\} \neq \phi$.

Isn't the answer to above example should be either $S_3$ or $S_4$, whose cardinality is 4?

The algorithm given in the notes is as following:

  Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
  Let $i$ be the class of the maximum cardinality.
  Choose any set with probability $\frac1{2^i}$

Applying the algorithm to above example, we get:

  $class_1: \{3,4,7\}$;
   $class_2: \{2,5,6,8\}$;
   $class_3: \{1\}$

As cardinality of class 2 is maximum among others, we pick $i = 2$.

What does the algorithm mean to say,

  Choose any set with probability $\frac1{2^i} = \frac1{4}$?
  (the probability of what?)

Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?

Let's go over your questions one by one:

(1) Your definition of Unique cover is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which uniquely covers the most elements. The subset $\mathcal{S}'$ uniquely covers an element $x$ if $x$ belongs to exactly one set in $\mathcal{S}'$.

(2) Exact cover is a decision problem, whereas Unique cover is an optimization problem. The decision version of Unique cover goes as follows:

  Given a set system and an integer $k$, is there a subset of the set system which uniquely covers at least $k$ elements?

Exact cover is a special case of the decision version of Unique cover.

(3) The sets $S_3$ and $S_4$ together cover $6$ elements once ($1,2,4,5,7,8$). Since $6 > 4$, it is better to take both $S_3$ and $S_4$ rather than any of them individually.

(4) The probability is that of choosing any given set. I suggest you look for more material on probability theory and on randomized algorithms, and after that come back and see if it makes sense.

(5) This is explained very clearly in various lecture notes. There is no point repeating the explanation here. I suggest you learn probability theory and randomized algorithms from scratch, and then attempt to read the $O(\log n)$ analysis again. It might take a few weeks, but without catching up on the basics you have no chance of understanding anything which is even slightly advanced.


Approximate Nearest Neighbour Problem in Spherical Setting There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving techniques. A proper definition of the problem is found in the image below.  (The problem definition is borrowed from Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing by Laarhoven and Weger 2015. Here is the IACR page for the paper. )

(Refer to Sieving for shortest vectors in lattices using angular locality-sensitive hashing
by Laarhoven 2015. The link is in the comments.)

I was curious if there is a way to have a similar spherical setting for the approximate NN problem for the finite field $\mathbb{Z}_2^n$. Particularly, I was wondering if there was a sphere definition relevant to $\mathbb{Z}_2^n$ that could be analogical or atleast very similar to the one in Definition 4. The one in definition 4 allows entire lattices to be embedded on the sphere i.e. $P$ is a lattice.  The proposed distance measure could either be the $l_2$ norm or the hamming distance.
It does not seem that it can be simply translated into finite fields.

I apologize if this is a naive question or does not make sense because I am a first time undergraduate researcher who is not very familiar with this forum and the level of questions asked here.

There is a reasonable distance metric on $\mathbb{Z}_2^n$ that allows one to define something that can be viewed as the analog of a sphere.  In particular, use the Hamming distance.  Then given any vector $c \in \mathbb{Z}_2^n$ and any positive integer $k$, the set $\{x \in \mathbb{Z}_2^n : d(x,c) \le k\}$ can be a ball centered at $c$ with radius $k$.  You could even call it a Hamming ball.

You can also define a version of nearest-neighbor search, using the Hamming distance on $\mathbb{Z}_2^n$ instead of the ordinary Euclidean distance on $\mathbb{R}^n$.  Everything carries over.  The algorithms/solutions may need to be different, though.  For approaches to this problem, you could look at metric trees and locality sensitive hashing.


Robot lawyer algorithm I have a background in physics and have taken some few classes online in Machine learning. But I really do not understand how this Robot lawyer  can work:

A 19-year-old made a free robot lawyer that has appealed $3 million in parking tickets

I am very interested in this type of artificial intelligence but I have no idea what to start reading about the topic.

Have somebody any idea of what type of algorithm he is using?

Here is what the article says:

  Browder programmed his robot based on a conversation algorithm. It uses keywords, pronouns, and word order to understand the user's issue. He says that the more people use the robot, the more intelligent it becomes. Its algorithm can quickly analyze large amounts of data while improving itself in the process.

Can the same algorithm also make the answer based on law data?

I'll join your potential downvote-fest with a speculation-filled answer.

Here are two Expert System algorithms I've worked with in industry.

Rete Algorithm:

https://en.wikipedia.org/wiki/Rete_algorithm

IBM and Oracle both have large Rete systems.

From what I've experienced, these are rules and fact tables that can be exeucted as a single atomic rule, or a million rules all on the same problem.  In my case we expressed these rules as tables of values, and IF/ELSE logic rules that can be grouped and managed and revised and controlled.

General Problem Solver

https://en.wikipedia.org/wiki/General_Problem_Solver

My impression is GPS is more flexible, and better handles the "fuzzy logic" cases and "precedence rules" (Where the answer changes when you reoder the precedence of the rules).

From my experience, I expressed these rules as small LISP functions where the tool could chose the "best" answer even if there still were unsolved values in the LISP functions.

If I'm allowed to just blindly guess:

My guess just from my gut feel, is that he's using Jess:

http://www.jessrules.com/


Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs I'm trying to solve a problem for class that is stated like so:

  A bipartite graph is an undirected graph in which every cycle has even
  length.  We attempt to show that the Hamiltonian cycle (a cycle that
  passes through each node exactly once) problem polynomially reduces to
  the Hamiltonian cycle problem in bipartite graphs. We need a function
  $T:  \{\text{graphs}\} \to \{\text{bipartite graphs}\}$ such that $T$ can be computed in
  polynomial time and for any graph $G$, $G$ has Hamiltonian cycle iff $T(G)$
  has a Hamiltonian cycle. Let $T(G)$ be the bipartite graph obtained by
  inserting a new vertex on every edge. What is wrong with this
  transformation?

I think the problem with the transformation is that for $T(G)$ you need to insert an edge between each pair of vertices and not just insert a new vertex on every edge. I'm actually a bit stumped by this one. Any advice would be much appreciated!

The problem is that a Hamiltonian cycle has to pass through all vertices: if the cycle in the original graph does not take some edge $e$, then the vertex you split $e$ with will not be taken if you take the same route. This means that the resulting cycle is not Hamiltonian.


What do we call a greedy algorithm that tracks the best $n > 1$ solutions? A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.

To avoid this problem, we may keep track of the best $n > 1$ solutions (instead of the best only). What is the name(s) of this algorithm?

Surprisingly, I can't seem to find the answer from Google. It'd be great if you could also list some resources on extensions to the naive greedy algorithm.

You might be interested in beam search, which could be viewed as working in more or less this way.


how did they get this answer for the words that don't have bba and abb? I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb.

and the answer was a*(baa*)*b+b*(a*ab)*a*

and I'm like wait a minute is that right ? but that can't make abb, which is in the language. So it's gotta wrong.

so I came up with my own , would this be all the words that don't have both substring bba and abb ?

(b+^)(ab+a)*+b*

^ is an empty string by the way

The textbook's answer does appear to be incorrect, as you note it does not generate $abb$ (and just to rule out an alternative interpretation of the exercise - "all strings that include neither $abb$ nor $bba$ - it does generate $bba$).

However your answer is also incorrect unfortunately - it doesn't generate $bba$.

There are a couple of reasonably sensible ways to get a correct answer (of course there's always many many techniques, and different people prefer different ones).

The first is the "intuition" approach, break the problem into the two parts, "the strings that don't have $bba$" and "the strings that don't have $abb$", then combine. With this method you have to then think about how such strings would look, and convince yourself that you haven't missed any cases.

The very formal method is to construct the expression from smaller, verifiable building blocks. In this case, we can easily construct a DFA for the strings that do contain $abb$ and one for the strings that contain $bba$, then we can use the intersection construction to get a DFA for the intersection of the two languages, take the complement DFA, then convert this to a regular expression.

What they seem to have done, and messed up or made a typo in one part, is the formal-but-not-quite-as-silly-as-option-2 method, where we make the two small DFAs, take their complements separately, convert each to a regular expression, then combine. I'll do the half that they seem to have gotten wrong (the bit that allows $abb$ but not $bba$, which is the first half of their expression).

The initial DFA is:

Taking the complement we get:

This second DFA recognises all the strings that don't contain $bba$. Now we convert this to a regular expression using the normal state elimination algorithm. If you haven't seen this yet, it will appear shortly in whatever course you're studying, or you can look over this explanation, but for the moment (and for the sake of keeping this answer on track!) hopefully it's acceptable that there is an algorithm for doing this conversion. In principle this algorithm can result in slightly different regular expressions depending on the order you eliminate the states, so if you have a go at it, you may not end up with quite the same regular expression (if you try one particular order, you get a real mess).

After all that we get the regular expression:
$$
(a+ba)^{\ast}b^{\ast}
$$

If we then proceed and do the DFA for strings containing $abb$, take its complement and derive the regular expression, we get (picking the right elimination ordering) the same as their second half, $b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$, and combine them and get the final answer:
$$
(a+ba)^{\ast}b^{\ast}+b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}
$$


Complete explanation of state elimination methods I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the difference to convert the NFA to RE and DFA to RE.
Online there are a lot of resources, but it is difficult to find a complete answer to understand the general idea of this method.
And, again, sorry if my question is too general, but I think that this place is a good place to meet people that understand this argument better than me, and are also able to explain it in a logical way.

I'm not an expert, but I try to answer your question with an order, and if I will say something wrong, the people can improve my answer.
In general, is possible to use the State elimination method to convert a "Deterministic state automata" (DFA) to a regular expression (RE).
From the theory, we know the information below

If a language is regular, then it is described by a regular expression.

We also, know that if a language is regular is accepted by a DFA.
well now to convert a DFA that describes our regular language to the RE, we need to convert the DFA into a "Generalized Nondeterministic automata" (GNFA).
Definition of GNFA

A GNFA is simple nondeterministic finite automata (NFA) wherein the transition (arrows of the graph) can contain a regular expression.

We also need the rules about this GNFA, we need the rules below:

The start state must behave only outgoing state and must hasn't incoming edge.
The final/accepting state must have only incoming transition and it just hasn't outgoing edge.

Structure example

We can convert easily DFA to a GNFA with a special form, with the following step:

If a DFA has an incoming edge to the start state A, we move the start state to new state B and we can connect the state B->A with an empty string (ϵ).

In addition: The start state must have only outgoing transitions. (if there is an incoming arrow/edge, it must not carry a (non-empty) label).

if the final/accepting state A has an outgoing transition, we can move the final state to a new state B and connect the node A->B with an empty string (ϵ).

In addition: The final/accepting state must have only incoming transitions.
PS. The additional informations are coming from the first comment below this answer.
Now the last step is to convert the GNFA to a RE.
After the conversion of DFA to a GNFA with a special form, we know that each arrow of GNFA can contain a regular expression, and at this point, the last step consists of the following passages:

Remove the intermediate step with an intermedia regular expression, until to remove all intermediate state.
The result that we can have is (InitState)--- RE---->(FinalState), and the regular expression of the transition from InitState to FinalState is the regular expression accepted from the previous DFA.

The passages can be express with the Figure below:

A complete example, that can help you to understand the process described inside this answer.


Find string that minimizes the sum of the edit distances to all other strings in set I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.

Is there an algorithm for finding the string $x$ which minimizes the sum of the distances to all strings in $S$, that is

$\arg_x \min \sum_{s \in S} \text{edit-distance}(x,s)$

It seems like there should, but I can't find the right reference.

The problem is known as "median string problem" and it is NP-complete; some results can be found searching with Google; in particular "2-Approximation Algorithms for Median and Centre String Problems". If $x$ must be one of the points in $S$ then the problem becomes solvable in polynomial time.


find the shortest path between two nodes where the number of edges is minimal Say you are given an undirected unweighted graph, where s and t are nodes from the graph.
d(s,t) means the distance between s and t which outputs the number of edges.

How do I find the the maximum distance between s and t ,
max{d(s,t)}, where the edges between s and t are minimal?
Also, how can this problem can be related/reduced to the hamiltonian problem?

Any advice would be really helpful.

Hint: Given a graph $G$, add two new vertices $s,t$, each connected to all vertices in the original graph. When does there exist a path from $s$ to $t$ of length $n+1$?


Time to construct a GNBA for LTL formula I have a problem with the proof for constructing a GNBA (generalized nondeterministic Büchi automaton) for a LTL formula:

Theorem: For any  LTL formula $\varphi$ there exists a GNBA $G_{\varphi}$ over alphabet $2^{AP}$ such that:

$\operatorname{Word}(\varphi)=L_{\omega}(G_{\varphi})$.
$G_{\varphi}$ can be costructed in time and space $2^{O(|\varphi|)}$, where $|\varphi|$ is the size of $\varphi$.
The number of accepting states of $G_{\varphi}$ is bounded above by $O(|\varphi|)$.

My problem lies in the proof of (2), that is, in the proof it says that the number of states in $G_{\varphi}$ is bounded by  $2^{|\operatorname{subf}(\varphi)|}$ but since $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ (where $\operatorname{subf}(\varphi)$ is the set of all subformulae) the number of states is bounded by  $2^{O(|\varphi|)}$.

But why does $|\operatorname{subf}(\varphi)| \leq 2\cdot|\varphi|$ hold?

In general, logical formulae can be thought of as trees; inner nodes are operators and leaves are atomic propositions. Therefore, every formula consists of as many direct subformulae (that is on the first level) as its top-most operator's arity. For example,

$\qquad \varphi \land \psi$

has two direct subformulae $\varphi$ and $\psi$. This can be continued recursively and we see that

$\qquad \displaystyle |\operatorname{subf}(\varphi)| \leq \sum_{\circ \in \operatorname{op}(\varphi)} \operatorname{arity}(\circ)$,

where $\operatorname{op}(\varphi)$ is the multi-set of operators occurring in $\varphi$. Informally speaking, every operator contributes its operands to the set of subformulae. Note that we have $\leq$ and not $=$ because a subformula might occur multiple times.

In LTL, all operators have at most arity two, so $|\operatorname{subf}(\varphi)| \leq 2|\varphi|$ provided that $|.|$ counts (at least) operator occurrences.


FNP ⊂ FPSPACE or FNP ⊆ FPSPACE? It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?

It is indeed the case that $FNP\subseteq FPSPACE$. Recall that a function in $FNP$ is of the form

  Given an input $x$ and a polynomial-time predicate $F(x,y)$, if there exists a $y$ satisfying $F(x,y)$ then output any such $y$, otherwise output 'no.'

source: Complexity Zoo

To see that every problem in $FNP$ is also in $FPSPACE$, note that we may enumerate over all possible $y$ (which can have at most polynomial length) and test whether the predicate holds for any of them. This all can be done in polynomial space, since $y$ is of polynomial size and computing the predicate is polynomial-time (and thus polynomial-space).

Whether the inclusion is strict depends on how you view an $FPSPACE$ machine. The most common definition is to have a polynomial "working" tape and an unbounded (write-only) output tape and in this case, $FNP\subsetneq FPSPACE$ because the output can be exponential. If you restrict the output to what is on the working tape (and thus the output is polynomially bounded), then the question is open (and depends on whether $NP=PSPACE$).


What data structure would efficiently store integer ranges? I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following:

Insert a new integer
Insert a range of contiguous integers
Remove an integer
Remove all integers below an integer
Test if an integer is present

My data has the property that it often contains runs of integers in the collection.  For example, the collection might at one point in time be:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

The simplest approach is just to use a balanced binary tree like the C++ std::set, however, using that, I am not leveraging the fact that I often have runs of numbers.  Perhaps it would be better to store a collection of ranges?  But that means a range needs to be able to be broken up if an integer in its middle is removed, or joined together if the space between two ranges in filled in.

Are there any existing data structures that would be well suited for this problem?

I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers).  Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant).  (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do not overlap.)

This data structure you can support all of your operations in $O(\lg n)$ time, where $n$ is the number of intervals.  Since we're guaranteed $n\le 65535$, I would expect this to be quite efficient.  (In particular, yes, you can split an interval into two pieces or merge two adjacent intervals into a single interval in $O(\lg n)$ time.)


"Given an algorithm, decide whether it runs in polynomial time" is this problem in NP? This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).
However, is this problem poly-time verifiable?
A decision problem $P$ is poly time verifiable iff there is an algorithm  called verifier such that if $P(w)=$ then there is a string $c$ s.t. $(w,c)=$, if $P(w)=$ then for all strings $c$, $(w,c)=$ and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.

No.  If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.
Why in exponential time?  Because $V$ runs in time $|w|^k$, it can read at most $|w|^k$ bits of the input.  So, it suffices to enumerate all possible strings $c$ of length at most $|w|^k$, and run $V$ on each of them.  The running time will be about $2^{|w|^k}$, which is finite and thus enough to make the original problem decidable.


Why is there only a polynomial number of provers in multi-prover interactive protocols? The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following:

There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Yes. We could have defined MIP to allow an exponential number of provers but that is basically  the PCP model which is equivalent to MIP with a polynomial (or just two) provers.


How do we know any problem is in NP-complete if we don't know all problems in NP? A problem is NP-complete if:

It is in NP.
All problems in NP can reduce to it.

It's number 2 that I'm concerned with here. I would be highly surprised if we knew  every problem in NP. Based on that assumption, how do we know for sure that any problem is NP-complete? For example, how do we know that there's not some problem we don't know of that will reduce to the Boolean Satisfiability problem, but not the Clique problem? Or would such a problem be NP-Intermediate and therefore need P != NP to exist?

We do know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-complete by encoding the statement "Machine $M$ accepts $x$ given non-deterministic choices $y$" as a logical formula for every non-deterministic Turing machine; for a machine running in time $T$ and space $S$, the encoding has length roughly $O(TS)$, so when $M$ is polynomial time, the encoding has polynomial length. The corresponding SAT formula states that "for some $y$, machine $M$ accepts $x$ given non-deterministic choices $y$". This formula is satisfiable iff $M$ accepts $x$.

Having proven that one problem is NP-complete, there is no need to do this encoding again. To prove that some other problem $L$ is NP-hard, it is enough to reduce SAT to $L$. Every problem in NP is reducible to SAT, and via the auxiliary reduction, to $L$. This is the way NP-hardness results are proved nowadays, by reducing from some NP-hard problem.


Is $\{u u^R u : u \in \Sigma^*\}$ context-free? Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)

I tried to show it wasn't context-free by using the pumping lemma but I'm out of ideas.

Based on : Pumping Lemma for Context-Free Languages for reversal language

By @lukas.coenig

{ww$^R$w| w $\in$ {a,b}*} doesn't seem to be a context-free language over $\Sigma$  of length two.

Assuming this language isn't context free over an alphabet of size 2 to prove it also over size of 3.. and so on by induction might be interesting..(and if true by induction than there is probably a better way to prove it)


Compute Lazily - Model checking What is meant by lazily computing online? For example, in context of synthesis, that uses model checking.

http://www.cs.colostate.edu/~france/CS614/Readings/Readings2011/Model-checking-Survey-a21-jhala.pdf

The above paper also mentions the concept in page 21:29.

Thanks in advance

In computer science, "lazy" means "just in time": in other words, you defer doing a computation until the last possible moment (e.g., until when the output is needed).

In computer science, "online" means that you are processing a bunch of input in a streaming fashion.  For instance, you might be given a sequence of queries.  An online algorithm would immediately answer each query.  In contrast, an offline algorithm might wait until it has seen all the queries before answering any of them.


Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort This is a popular question:

  What is the most efficient (in time complexity) way to sort 1 million 32-bit integers?

Most answers seem to agree that one of the best ways would be to use radix sort since the number of bits in those numbers is assumed to be constant. This is also a very common thought exercise when CS students are first learning non-comparison based sorts. However, what I haven't seen described in detail (or at least clearly) is how to optimally choose the radix (or number of buckets) for the algorithm.

In this observed answer, the selection of the radix/number of buckets was done empirically and it turned out to be $2^8$ for 1 million 32-bit integers. I'm wondering if there is a better way to choose that number? In "Introduction to Algorithms" (p.198-199) it explains Radix's run-time should be $\Theta(d(n+k))$ (d=digits/passes, n=number of items, k=possible values). It then goes further and says that given n b-bit numbers, and any positive integer $r \leq b$, radix-sort sorts the number in $\Theta((b/r)(n+2^r))$ time. It then says:

  If $b \geq \lfloor \lg(n) \rfloor$, choosing $r = \lfloor \lg(n) \rfloor$ gives the best time to within a constant factor.

But, if we choose $r = \lg(10^6) =20$, which is not $8$ as the observed answer suggests.

This tells me that I'm very likely misinterpreting the "choosing of $r$" approach the book is suggesting and missing something (very likely) or the observed answer didn't choose the optimal value.

Could anyone clear this up for me?

Minimizing run time is a very different question from minimizing operation counts. Sorting large data sets tends to be memory bound, so the goal of optimization is not to reduce the number of operations, but to try and do make efficient use of memory — for example,

do as much work as possible in L1 cache
use bandwidth to main memory efficiently by writing full cache lines
avoid overflowing the TLB by too much

Increasing the number of buckets works against all three points; it does no good to complete a radix sort in two passes if each pass takes three times as long as each pass of a four pass implementation!


Thompson Regular Expression Search Algorithm 3rd Stage My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows:

Check that the RE is syntactically correct
Convert RE to reverse polish form

The paper states "the third stage is at its heart a pushdown stack." I don't get what that means.

It seamlessly walks us through pushing and popping off the stack to translate the RE $a(b|c)^*d$ with CNODES and NNODES.

But what is this for? I know that the purpose of the algorithm is to find all substrings in a given text that match the given RE, but I don't see how the third stage achieves this.

Let's take the example from the paper: $a(b|c)^*d$. This is first translated into RPN: "$abc|*.d.$". This is compiled into (essentially) an NFA by using a stack. Upon reading a symbol $\sigma$, we push to the stack an NFA for $\sigma$, which we will denote by $N(\sigma)$. Upon reading $*$, we pop an NFA $N(r)$ for the regular expression $r$ from the stack and push $N(r^*)$, an NFA for $r^*$. Upon reading a binary operand $\circ$, we pop two NFAs $N(r_1),N(r_2)$ and push $N(r_1 \circ r_2)$, an NFA for $r_1 \circ r_2$.

Here are the different stages. At each stage, we underline the character being processed, and the resulting stack after processing it, where the top-of-stack is to the right:

$abc|*.d. \qquad $ (empty)
$\underline{a}bc|*.d. \qquad N(a)$
$a\underline{b}c|*.d. \qquad N(a) N(b)$
$ab\underline{c}|*.d. \qquad N(a) N(b) N(c)$
$abc\underline{|}*.d. \qquad N(a) N(b|c)$
$abc|\!\underline{*}.d. \qquad N(a) N((b|c)^*)$
$abc|*\underline{.}d. \qquad N(a(b|c)^*)$
$abc|*.\underline{d}. \qquad N(a(b|c)^*) N(d)$
$abc|*.d\underline{.} \qquad N(a(b|c)^*d)$

Nowadays the regular expression will be parsed into a tree, and the translation process will proceed recursively. If the tree is processed in the correct order (DFS), then this would be completely equivalent to the algorithm described by Thompson.

Either way, having constructed an NFA for the input regular expression, we run it on the input text. This is the part in which we actually search the input text.


Analysis of algorithms, 'big O' question The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?

Also, what about more complex iterations, such as colour conversions etc?

I would like to point out that this is not a homework question, rather, it is a question from my own research/programming learning curve. I have code that I am working on, but would like to know how this analysis is carried out.

There is no such formula. If there were, it would solve the halting problem, because we could take an algorithm (Turing machine), find its big-$\Theta$ complexity, then return true or false depending on if it was $\Theta (\infty)$.

For Big-O (upper bounds), there's technically a formula, since all functions are in $O(\infty)$. However, there's no way to find a tight upper bound, nor to test if an algorithm has a bound tighter than $O(\infty)$.

That said, there are certainly tools and heuristics for determining these things, as well as limited models of computation for which the problem is decidable.

For example, if you can express your routine using recursion, often you can find a recurrence relation for the running time, which you can solve to find the Big-O time. However, none of these techniques will work all the time.


How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph? I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is extremely redundant. Is there any algorithm to circumvent this?

Pathfinding algorithms that are able to recompute the best path when the graph changes without doing a full recomputation are called "Incremental".

The incremental version of Dijkstra's algorithm has the horrible name DynamicSWSF-FP.

The much more common algorithm which combines this with A* is called LPA*


If set membership problem can be solved for a particular language does this imply that the language is regular? If we know that a language is regular, we can solve the set membership question for a given string by running it through the corresponding DFA  for that language.
But what about the other way? Means, if set membership question can be solved for a particular language does this imply that the language is regular?

Since any irregular, but decidable language answers the question with "no, there are irregular languages that are decidable", maybe some nuance for how this relates to the usual complexity classes.

For one thing, every regular language has at most linear time complexity (just use a DFA that recognizes the language and run the word on it and check whether you end up in an accepting state). Therefore, the deterministic time hierarchy theorem implies that there are languages that are decidable, but irregular, since it implies that the set of languages that, say, require at least quadratic but at most cubic time is nonempty; similarly for languages that require $\Theta(2^{2^{2^n}})$ time. On the other hand, there are irregular languages that have linear time complexity, as illustrated by the example $\{a^nb^n : n \in \mathbb{N}\}$ that David gave.

Another surprising thing I became aware of only recently is that SAT, the NP-complete problem of deciding whether a CNF formula is satisfiable, is context-sensitive. To see this, remember that the automata recognizing context-sensitive languages are the linear bounded automata, which are nondeterministic Turing machines that are only allowed to use the space used for the input (or alternatively, only use linearly much additional space - using a speedup theorem, those definitions should be equivalent); here are references on the matter.

And finally, a restricted version of the question ("does NP-completeness imply regularity?") can be answered by "no, there are irregular languages that are NP-complete". If P=NP, then all irregular languages that can be decided in polytime are NP-complete (since the reduction has all the power required for deciding any NP-problem, and so reductions always work), and if P$\neq$NP, then all NP-complete languages are irregular: if they weren't, then there would be a regular language that is NP-complete, but regular languages can be decided in linear time, contradicting P$\neq$NP.

So to sum up: decidability doesn't tell you much about where in the complexity zoo we are, and even knowing a language can be solved in linear time doesn't tell you anything about regularity. On the other hand, irregularity doesn't tell you much about time complexity either (maybe that implies that the language requires at least linear time - but I can't prove that off the cuff, not sure it's true!).


Where is the theory about "binary toggling games"? Let us -- using parameters $M, N$ and $L$ --

create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in
\{0\ ..\ N-1\}, \forall k \in \{0\ ..\ M-1\}$.
create an N-bit long vector $A_0$ and initialize it to ones.
create an $M$-bit long vector $S$ and initialize it randomly in the same manner as any $V_k$.
for $i$ from $0$ to $M$, if $S[i] = 1$, then $A_i = A_{i-1} \oplus V_k$, otherwise $A_i = A_{i-1}$, resulting in $A_M$ after $M$ steps
present an agent/player with $A_M$ together with all vectors $V_k$ and make him return $S$ or the set of indices of vector $S$ where $S[i] = 1$. It follows that $A_M \oplus V_{i_0} \oplus V_{i_1} \oplus V_{i_2} \oplus\ ...\ \oplus V_{i_{last}} = A_0$.

A simple example with $N=4$ and $M=3$:

$A_M = [0, 1, 0, 1]$, $V_0 = [1, 1, 0, 1]$, $V_1 = [0, 0, 1, 1]$, $V_2 = [0, 1, 1, 1]$

solution $\rightarrow S = [1, 0, 1],$ because $A_M \oplus V_0 \oplus V_2 = [1, 1, 1, 1]$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the "binary toggling game".

What I wonder is:

what are "binary toggling games" really called
what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

Could you please provide links? I hope they exist.

"Binary toggling games" are generally just arithmetic problems over GF(2).

Your particular problem is equivalent to the following over GF(2):

$$\sum_i V_iS_i = 1 + A_M $$

If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2):
$$V\vec{S} = 1 + A_M$$

You can solve this problem using Gaussian elimination over GF(2). In your example:

$$\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 1 & 0 & 1 & 0\\
 0 & 1 & 1 & 1\\
 1 & 1 & 1 & 0
\end{array}\right) \longrightarrow
\left(\begin{array}{ccc|c@}
 \color{red}1 & 0 & 0 & 1\\
 0 & 0 & 1 & 1\\
 0 & 1 & 1 & 1\\
 0 & 1 & 1 & 1
\end{array}\right)\longrightarrow
\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 0 &\color{red}1 & 1 & 1\\
 0 & 0 & 1 & 1\\
 0 & 0 & 0 & 0
\end{array}\right)\longrightarrow
\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 0 &1 & 0 & 0\\
 0 & 0 & \color{red}1 & 1\\
 0 & 0 & 0 & 0
\end{array}\right)
$$

From which we can read off that $S_1 = 1$, $S_2 = 0$ and $S_3 = 1$.


Does "not regular" imply "acceptor needs memory"? Regular Languages, by definition, can be accepted by finite automata, which do not have memory. But if I know that a language is not regular, does that imply that any mechanism that recognizes the language must have memory?

Every language $L \subseteq X^{\ast}$ for $X$ a finite alphabet could be accepted by the following (in general infinite) "automaton" (in the usual notation as "alphabet, states, start state, transition relation and final states")
$$
 \mathcal A = (X, Q, L, \delta, F)
$$
with $Q := \{ L/w : w \in X^{\ast} \}$, $\delta(L/w, u) := L/(wu)$
and $F := \{ L/w : \varepsilon \in L/w \}$, where
$$
 L/w := \{ u \in X^{\ast} \mid wu \in L \}
$$
is the quotient of the language (i.e. we take away prefixes from words in $L$). The set of quotients could be regarded as the states, or the memory. Which is finite if $L$ is regular (and more this construction gives a minimal finite automaton), and is infinite if $L$ is not regular (for example consider $L = \{ a^n b^n \mid n \ge 1 \}$ over $X = \{a,b\}$).

So in short in this (somehow canonical) model even a regular language has some kind of memory (a state which signalizes some property of the string being processed), but the crucial property is that we can get along with finitely many (memory) states, whereas in the non-regular case in this model we always need an "unbounded" memory/states.


Is a Turing machine too strong of a model to model physical computation? I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing thesis is wrong and that a Turing machine does not accurately model any possible real world computation. To me, it seems that not only is the Turing machine not too restrictive, it's actually unrealistically strong. Namely, it has unbounded tape and time in which to perform its computation!

I suppose that the counterargument to this would be that unbounded is not the same as infinite, and in an idealized model of the physical universe we really have unbounded space and time in which to perform computations (neglecting minor details like the expected heat death of the universe and the possibility of finite space). But still, it seems as though we are basing our ideas of what is computable on an unreasonably strong model.

So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature? Or is there some deep inherent reason why unboundness is a requirement of any such model?

Edit: To address the comments so far - I know that a Turing machine with bound tape is equivalent to a DFA, and therefore definitely does not capture in any reasonable way the notion of possible real world computations. I was rather referring to models that might not resemble Turing machines at all.

Is it too strong?
The concern should not be that a Turing machine is a too strong model because of the way we construct a Turing machine. Turing machine is essentially a framework for defining a notion of algorithm in its basic, simple steps. Every algorithm executed on a Turing machine can be executed by hand, meaning it is effectively calculable (one direction of Church-Turing thesis). The real question is - is there an effectively calculable function whose computation cannot be encoded in a Turing machine. This all seems that it must hold (and therefore many computer scientists accept Church-Turing thesis as true), but cannot formally be proven just because the term "effectively calculable" is not formally defined.

Why not bound it?
I am not sure if this satisfies your quest for "deep inherent reason why unboundness is a requirement", but think about it this way: What if we bound the tape? Say, a Turing machine must have tape of length at most $M$, for some $M \in \mathbb{N}$. Let's look at $2$ examples:

We can choose/construct a Turing machine $T_M$ that uses exactly $M$ distinct positions on a tape. Then, we can construct a Turing machine $T_{M+1}$ that runs exactly as $T_M$ with additional step - that it writes a symbol after the last symbol on its tape, once it finishes all the running steps of $T_M$.
This Turing machine (algorithm) $T_{M+1}$ therefore could not exists if we bounded the tape at $M$, but obviously - this algorithm is effectively computable.
Say you want to construct a Turing machine that adds two numbers. What if the length of numbers is more than $M$? We could not add them (nor even write them) with a Turing machine, but can obviously add them (say, by hand) via standard known algorithms for addition (that also doesn't have restrictions on length/tape).

Therefore, we must not bound the tape if we want to be able to compute things that we can in theory compute (by hand). The same arguments holds if we would want to bound the number of steps (time).

Computatioal complexity deals with resources required by an algorithm depending on size of the input, so you might want to look at that subject.

  So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature?

Turing machine is a finite model.

Different model
$\lambda$-calculus is a computational model invented by Turing’s doctoral advisor Alonzo Church. It does not resemble Turing machine and it is based on a concept of definition and application of functions. Turing and Church proved that their models are equal in computational power.


Relaxed graph coloring, with penalties for assigning adjacent vertices the same color Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus the diagonal entries of $D$ are all zero and $d_{ij}=d_{ji}$ so $D$ is symmetric.

Then there is a set of  $k$ colors. I want to assign these colors to the $N$ nodes such that the minimum  metric of a common color between any pair of nodes is maximized. So if $c(i)$ is the color assigned to $i\in [N]$ by the assignment $a\in A$, where $A$ is the set of all possible color assignments, we are looking for $$\max_{a\in A} \min_{i,j} \{d_{ij}:c(i)=c(j)\}.$$

Is this problem NP-hard?  If it is, what sort of reduction can be used to show that this problem is NP-hard?

Yes. Reduce from graph coloring.

$D$ is given by $d_{i,j} = \begin{cases} 0 & \text{ if } i=j \\ 1 & \text{ if } i \text{ is adjacent to } j \\ 2 & \text{ else}\end{cases}$.


Implementing Gauss–Legendre algorithm using arbitrary-length rationals I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate.  SuperPI computes pi using the Gauss-Legendre algorithm.

The Gauss–Legendre algorithm is quite simple, but the problem is how to store values with full precision. I store all numbers as arbitrary sized rationals, but I am still getting weird results.

Pseudocode:

a0 = 1/1;
b0 = 470832/665857; // an approximation to 1/√2
t0 = 1/4;
p0 = 1;

for i in 0..n {
    a_i+1 = (a + b)/2;
    squared_b_i+1 = a * b;
    b_i+1 = sqrt(squared_b_i+1); // calculated as sqrt(numerator)/sqrt(denominator)
    t_i+1 = t - p * (a_i - a_i+1)^2;
    p_i+1 = 2 * p;
}

let result = (a_n+b_n)^2 / (4t_n);

(actual code may be found here)

My implementation has at least two problems:

It doesn't matter how good 1/√2 approximation I take (470832/665857 in this example), the algorithm doesn't converge to the correct value.
Calculating √(a/b) as √a/√b is not very accurate, because it does  ⌊√a⌋/⌊√b⌋ which can introduce a large error.

As a result, my implementation calculates 11 true digits per 20 iterations, while SuperPI does 1M digits.

How do I implement the Gauss–Legendre algorithm efficiently, given the above challenges?

It sounds like you are using arbitrary-precision arithmetic, i.e., you represent each rational number as a ratio $a/b$ where $a,b$ are stored as arbitrary size integers (bignums).  If that's the case, that's probably the source of your problem.

Don't do that.  That's highly inefficient, because you'll end up with very large integers $a,b$, that may be far larger than needed for the desired precision level; and it'll be imprecise, because of the ⌊√a⌋/⌊√b⌋ problem you mention.

Instead, use fixed-precision arithmetic: each number is represented directly as a number (not a ratio) using a fixed-precision representation.  That will be much more efficient and more accurate.  It won't have the problem of ⌊√a⌋/⌊√b⌋, since you're not limited to a ratio of integers.  You might need to find a library that implements fixed-precision arithmetic, or to implement that part yourself, and you'll probably need to estimate the appropriate precision level based on the number of iterations and the amount of precision achievable with that given precision level.


Understanding Binary Search for Kth Smallest element in an Array The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 cause we needed to adjust the mid value based on the start and end of our range. The thing I just can't seem to wrap my head around is why does it work? The numbers in the array are unsorted and not contiguous,duplicates may exist so why does reducing the search space in our range based on countless or countequal give us the correct answer?
Can someone give some intuition or simple explanation to why this works?

Let me start by recalling the question:

  Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case.

Calling the array $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B[i]$ is the number of elements in $A$ which are at most $i$. If $B[i] \geq k$ but $B[i-1] < k$ (assuming $B[0] = 0$), then $i$ is the $k$th smallest element. We can find $i$ using binary search.

Instead of computing the array $B$ ahead of time, we have "oracle access" to it: we can compute any given entry in time $O(n)$ by going over the entire array $A$. This is the algorithm you link to.


Break and Continue in Structured Programming? One of the ways to ensure following the structured programming paradigm is by having all control flows having only one entry and one exit point. Does skipping iterations by using break and continue in languages like Java count as a second exit point (like a GOTO-statement) or not?

I am aware that Java has no (working) goto statement but a break and continue. The question was whether using them violates the structured programming paradigm or not, i.e. is it bad code style or not (in all languages having break and continue, not just Java).

That of course depends on how exactly we define structured programming. We can look to the research papers that coined the phrase, such as the 1966 Structured Programming Theorem. Structured programming, as defined in these papers, would not permit partial execution of a loop body, and therefore neither a break, continue, return or throw statement (nor any exceptions thrown by the JVM).

All of these language features were invented after structured programming, and to address perceived deficiencies of structured programming (in its original definition). Whether these amendments comply with the spirit of structured programming (or equivalently, whether a modern definition of structured programming should encompass these features) has been the topic of some debate, see for instance the 1995 paper Loop Exits and Structured Programming: Reopening the Debate.

Personally, I find applying this 1966 programming technique, ground breaking as it was at the time, verbatim to a modern programming language such as Java an undertaking of very questionable benefit, not the least because structured programming (in its original definition) does not permit exceptions, but exceptions are an integral part of the Java language.


The concept of the creation of a trapdoor in NP-complete or NP-hard problems I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:

In real world scenarios, cryptosystems based on NP-hard or NP-complete problems tend to rely on particular subclass of problems either to achieve efficiency or to allow the creation of a trapdoor.

Questions:
Is is possible to explain what does it mean the phrase "to allow the creation of a trapdoor"?
Thanks for any help

A "trapdoor" function is a function which is hard to compute, but will become very easy (or a lot easier) to compute if you have some specific knowledge.
The classical example is solving y = x^3 (modulo n) where n is the product of two very large primes; it is the basis of RSA encryption and practically impossible to solve given x and n, unless you are given the two primes p, q such that n = pq.