is L = { | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE? L is the language of all turing machines that its computing time on all inputs is O(n^2).
my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search....
However, is the language in CO-RE ?

This problem is not in RE nor in coRE.

First, your intuition that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof!
However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.

Let's start by proving that the language is not in coRE, by a reduction from $HALT_{TM}=\{\langle M,w \rangle: M$ halts on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.

Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT_{\overline{TM}}=\{\langle M,w \rangle: M$ does not halt on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.

The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.


finite automata that accepts integers divided by 3? I have found in a book the example of how to make a FA that accepts those numbers that are divisible by 3, that means that n mod 3=0. In the example the author used the binary representation of the number to be evaluated. The resulting automata is:

The states represent the probable remainders, that could be 0, 1 or 2. Some additional explanation is in the following part:

I have tried the following examples to test this automata:

If I try to do 6 mod 3 that will result in 0, so I will go from the
initial state (upper part of the figure) to the acceptance state,
that is because the modulus is 0.
If I try 5 mod 3 or 101 mod 11 that    would be 2, which in binary is 10. If I want to apply again 2 mod 3. I    will end up again with 2 and not reaching an acceptance state. From    the upper part I
followed the path 1--state 1--0--state 2. What    happens there? it
just stays in that state 2?

I just do not have a clear picture of how to test this FA for example with an input of 81 mod 3, does it make partial divisions? When I try to follow it I end up in an acceptance state even before finishing to evaluate the remainder.

Any help?

I believe you are misunderstanding the way finite automata work. A finite automaton accepts a language, i.e. a subset of the finite strings of a given finite alphabet. In your case, the accepted language is the set of strings made of $0$ and $1$ which encode a well-formed multiple of $3$.

Given a string, imagine placing a token on the initial state, then for each character of the string, left to right, move the token along the transition labelled $0$ or $1$, according to which character you read.

After having consumed each character of the string, the automaton accepts if and only if the token is on one of the accepting states.

Considering your automaton, intuitively, the top three states determine whether the string encodes a well-formed number (i.e. a string that starts with $1$ or is exactly $0$, for instance, $1000$ is valid, but $000$ isn't) while the bottom three determine whether or not it is divisible by $3$ using elementary number theory.


Can a self-learning appliance be developed? I have heard of machine learning systems that can learn from trials of data what effect it should have, but I was wondering is it possible to make a learning appliance that builds on past data? Instead of only receiving new entries, once the database is big enough to begin going over it and doing pseudo consideration, drawing conclusions about the data and adding yet more entries to its database purely from looking at its past results? I suppose such a thing would probably eat up memory quickly unless it had a threshold of entries it was allowed to create. (In theory it would take a long time to get it to a state where it can become sentient in that way, through many trial sets before it begins thinking on its own.)

An application of such a thing would go beyond just determining what the best way to optimize code is, or how to beat a player in a game, but a machine that can actually build its own personality.

You may be thinking of some combination of online and offline learning.

Online learning only use new examples to base its learning on, and modifies the model at each step.

Offline learning looks at all available data, then fixes its model and uses that model on new data.

There is some use in creating new examples from existing ones, but this is typically done by hand, as to emulate possible variations expected to appear in actual data (and typically only if you don't have enough data). There isn't much use in automating this, as any conclusions it draws from the data will already be reflected in the model - if we add entries based on these conclusions, and in turn use these to draw new conclusions, either the conclusions will remain exactly the same (i.e. there's no point in adding them), or we'll start to lean towards conclusions not corresponding to the original data, which is not a good idea.

The only way AI can build its own personality, is if you program the potential to do so into it. There's no way AI can suddenly become sentient after playing 1000000000000 games of chess if it's only been taught to play chess and only knows about chess.


How to store factorials? Can someone help me to store the factorial of large numbers such as 100! efficiently?

UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving. The true challenge is to find a data compression scheme that achieves a significant compression ratio, but with a lighter computational complexity than recomputing the factorial(s) from the argument.

More precisely, can you design an algorithm to produce all decimal digits of $n!$, for $n\le N$, using $o(N\log N!)$ storage and small computational cost, such as the lower bound $O(\log n!)$.

We can calculate 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. You can store this in any way you want: as 100!, as the ASCII string 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000, as a Unicode string, or in binary in any number of formats. It all depends on what you want to do with the value. If you want to display the value on screen as a decimal, you might as well store the decimal string. If you want to do arithmetic, then you should be using a library for dealing with "big numbers" such as GMP, and in this case the library will provide its own means for storing numbers. If you're just interested in storing the expression 100!, and intend to use it in a computer algebra software (CAS), you might as well store it as just 100!.


Work-stealing: where and how many to steal If one ignores the conflicts when accessing the dequeue in Work-Stealing algorithms, does it matter (and in what ways) if one steals from the top or bottom (or anywhere randomly) of the dequeue? Does it matter (and in what ways) if one steals one or more items ?

I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It means that you can get items more than once but at least once. There are then three operations defined $put()$, $take()$, and $steal()$. The idea is that $put()$ and $take()$ are free of synchronisation only $take()$ uses atomics. When a thread has finished its queue (or stack) it uses $steal()$ on some other threads stack.


Reinforcement Learning - Q Learning I am having trouble understanding the following problem and Q learning in general.

What I know so far about Q learning is that Q-learning is a model free method, i.e., it doesn’t need to learn P(s’|s,a). Thus it can compare the expected utility of the available actions without the model of the environment.It will also eventually find a policy that is the maximum achievable. However, I am not able to use this knowledge to do this problem. The answer is given in red.

If we are to look at time t = 1, then the equation becomes the following: $$ Q_{t+1}(s,a)=(1-1/2)(1)+1/2[R(s,a,s^{'})+(1)  maxQ(s^{'},a^{'})] $$
How do I proceed from here?

At t=1, you just took action a = d at state s = S and ended in s' = S again with 0 reward. So:

$Q(S,d) = (1 - 1/2)(1) + 1/2[0 + (1)(1)] = 1$ ($maxQ(s',a')$ is the maximum value you can get from state S in this case, which is 1)

So nothing changes. At t=2, it is exactly the same as t=1, so nothing changes again.

At t=3, we just took action p at s = S and ended on state s' = P with reward +1. Thus:

$Q(S,p) = (1 - 1/2)(0) + 1/2[1 + (1)(1)] = 1$ ($maxQ(s',a')$ here refers to $maxQ(P,a')$, the maximum value we can get from state P, which is 1.

So, update $Q(S,p)$ to 1.

At t=4, we just took action a = p at state s = P, ending in state s' = S with reward 0. Thus:

$Q(P,p) = (1 - 1/2)(0) + 1/2[0 + (1)(1)] = 1/2$

So, update $Q(P,p)$ to 1/2.

I think you can do t=5 and t=6 by yourself now, just note that maxQ at a terminal state is 0 (because there is no future reward to accumulate). If you can't, just tell me and I'll update the answer.


Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'? I'm defining 'Hard AI' as a human-equivalent intelligent machine, or beyond that. Contrast with 'Soft AI' the type of software that runs on your email filter for example.

I've been chewing on this problem for a little while now, and would like some feedback on my logic. This is the only place I could think to put it, so please feel free to move/remove if this is not appropriate.

My argument hinges on the definition of 'human-equivalent intelligence' as 'capable of solving any given instance of the Halting Problem'. This is something no machine can ever do - while they may be able to solve for sub-sets of the Halting Problem, they can never accept an arbitrary instance of it (ie, specific inputs I for a specific program P) and produce an answer.

Humans, however, do this all the time! The entire profession of programming revolves around fixing incarnations of the Halting Problem that pop up in one's own codebase. There are problem-tracking instances full of real-world examples of the Halting Problem - "Subsystem Z stops responding after receiving A with B options", etc. These examples are fixed by humans, and the problem goes away. Sometimes instructions are written for the machine to verify that the problem hasn't returned, taking advantage of the recognizability of solutions to the Halting Problem.

Since any 'Hard AI' would need to be just as capable as humans in any intellectual pursuit, and we KNOW that a machine that solves the Halting Problem cannot exist, we must conclude that there can never be human-intelligent machines.

You're understanding of "solve all instances of the Halting Problem" is flawed. All instances means ALL instances. Every single one, ever.

For example, no human knows if a Turing Machine verifying the Collatz Conjecture will halt. Bam, right there, your premise that humans can solve "all" incarnations of the Halting problem is flawed.

There is no reason to think that a sufficiently good AI wouldn't be able to solve the same, or more, instances of the Halting Problem that humans can.

The undecidability of the Halting problem means that there is no algorithm which solves the halting problem. That means there is no algorithm Humans can use, and no algorithm machines can use. The proof doesn't rely on what the algorithm runs on.

Another way to look at it is that the halting problem, and other undecidable problems, essentially boil down to searching an infinite space. The inability of humans to time travel and examine an infinite number of instances doesn't negate our intelligence, so there's no reason it would for machines either.


Is this combinatorial optimisation problem similar to any known problem? The problem is as follows:

We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a fixed integer $n$.

We now wish to overlay $n$ rectangles of dimensions $w \times h$ on the grid such that the total sum of the values of cells in these rectangles is maximized.

The following picture is an example of a two-dimensional grid with two such rectangles overlayed on it (the picture does not demonstrate the optimal solution, just one possible overlaying where $w = h = 2$ and $n = 2$)

The rectangles cannot intersect (otherwise we would just need to find the optimal position for one rectangle and then put all the rectangles in that position.)

In the example above the total sum of values in cells would be $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Is this similar to any known problem in combinatorial optimisation? so that I can start doing some reading and try to find ways to solve it.

Some more background for those interested:

So far the only ideas I had are either a greedy algorithm (which would find the best location for the first rectangle, then find the non-overlapping loctaion for the second rectangle etc.) or some metaheuristic such as genetic algorithms.

In reality I wish to solve this problem with a grid which has around a million cells and tens of thousand (or even hundreds of thousands) of rectangles, though it is not necessary to solve it in a short time (i.e it would be acceptable for the algorithm to take hours or even days.) I am not expecting an exact solution but I want to get one which is as good as possible given these constraints.

Cheers!

You could formulate this as a gigantic integer linear programming (ILP) instance, and then apply an off-the-shelf ILP solver (lp_solve, CPLEX, etc.).  They will give you the best solution they can find.  Given the size of your problem instance, I don't know whether this will be efficient enough, but it would be easy to try.

Here's the ILP formulation.  We have a zero-or-one variable $x_r$ for each possible rectangle $r$, with the intended interpretation that $x_r=1$ means you include rectangle $r$ in your set and $x_r=0$ means you don't include it.  You want to maximize the objective function $\sum_r c_r x_r$ (where $c_r$ is the profit of rectangle $r$), subject to the restriction that $\sum_r x_r = n$ and that no two rectangles overlap.  The latter restriction can be expressed as a linear inequality by requiring $x_r + x_s \le 1$ for all pairs of rectangles $r,s$ that overlap.  So, in this way you get a ILP.


what are Structural recursion, primitive recursion, recursion combinator and recursion principles? Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link

I googled and read some, but missing the points of them. I know that recursion occurs when a function appears within its definition. While $\lambda$-calculus cannot express such recursive definitions directly, it can use combinators to implement recursion.

So, what are Structural recursion, primitive recursion, recursion combinator and recursion principles? how each related to others?

Hoping someone could explain these clearly, so I can go in the right direction. now I am struggling to figure out their "points".

Thanks in advance!

The recursion combinator you mention seems to be the recursor associated to an inductive (or recursive) data type. In the paper this seems to be the type describing the syntax of lambda terms. Here, I'll take lists as a simpler recursive type.

Note that the "lists of naturals type" can be intuitively described as the "least" type admitting these constructors:
$$
\begin{array}{l}
nil : list \\
cons : nat \to list \to list
\end{array}
$$
Recursive types as the one above have an associated induction principle. For instance, if we wanted to prove a property on all lists $p(l)$, it would suffice to prove

the base case $p(nil)$, and
the inductive case $p(l) \implies p(cons\ n\ l)$ for any $n,l$.

If we had more constructors, we would have move base or inductive cases, accordingly.

Similarly, we can define a function $f : list \to A$ by induction. That is to define $f(l)$ on all lists, all we have to do is to define

what is the result in base case, i.e. $f(nil) = a : A$
provided we already defined $f(l)$, we need to define $f(cons\ n\ l)$ for all $n,l$.

Note that step 2 amount to define a function $g : nat\to A \to A$, which takes $n:nat$ and $f(l):A$ and produces $g(n)(f(l)) = f(cons\ n\ l)$.

We can generalize this by crafting a combinator that given $a,g$ produces $f$ defined as above. This is called the (primitive) recursor.

$$
\begin{array}{l}
rec : A \times (nat \to A \to A) \to (list \to A) \\
rec(a,g)(nil) = a \\
rec(a,g)(cons\ n\ l) = g(n)(rec(a,g)(l))
\end{array}
$$

Usually this is called fold_right or foldr in functional programming languages.

Note how, roughly, $a$ replaces $nil$, and $g$ replaces $cons$. Indeed, in the general case, the recursor takes one argument for each constructor of the recursively defined type at hand.

If you have a general fixed point combinator like Church's $Y$, you can easily encode the above. However, in many type theories, you don't have that luxury, since $Y$ causes the inconsistency of the related logic. Instead, for any recursive type you define, you get a restricted version of $Y$ which is the recursor: each type has its own recursion combinator. This ensures the termination of the calculus, which is important to ensure the consistency of the logic.


CFG with regular expression terminals on RHS Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G_1$:

$\begin{align*}
S & \rightarrow (a \mid b) S (c \mid d) \\
S & \rightarrow (a \mid b) A (c \mid d) \\
A & \rightarrow (f \mid g)^*
\end{align*}
$

Then the language of $G_1$ is the following:
$$L(G_1) = \{(a \mid b)^n (f \mid g)^* (c \mid d)^n \mid n > 0\}$$

Give a standard CFG that has the same language as $G_1$, is your grammar weakly equivalent to $G_1'$, strongly equivalent to $G_1'$, or both? Why?

Secondly, how can I transform any CFG with regular expressions of terminals on the right hand side to a normal context free grammar?

The general answer is pretty straightforward: if you have a grammar rule of the form $S \rightarrow {\alpha}r{\beta}$, where $r$ is a regular expression over the set of nonterminals, change this production to $S \rightarrow {\alpha}S'{\beta}$, find a right-regular grammar with start symbols $S'$ generating $L(r)$ (there is an algorithm for this); and then your grammar will include all those productions as well. Repeat for every production containing a regular expression on the right-hand side.


How memory remapping of physical address space that is above 4GB RAM works? I have a query regarding the below information in http://duartes.org/gustavo/blog/post/motherboard-chipsets-memory-map/

"In 64-bit mode it is possible to use physical addresses above the total RAM in the system to access the RAM regions that correspond to physical addresses stolen by motherboard devices. This is called reclaiming memory and it’s done with help from the chipset."

Let's say if the RAM size is of 4GB. In 64-bit mode or with PAE enabled for 32-bit mode, if the address space above the total RAM 0x10000012C is assigned to some assorted device on the mother board, then how that assorted device can get hold of some memory region on RAM?

I am not entirely sure what your question is but I will try to answer. I think your confusion comes from the fact that some peripherals (typically PCI and APIC) use memory-mapped registers that "steal" memory from the physical address space (the famous 1GB hole described in the blog post). But those memory-mapped registers do not use RAM at all. They simply steal part of the address space and thus some physical addresses that would normally refer to RAM now serve another purpose. Now if you only have 4GB of RAM and the RAM is mapped at 0, a peripheral at 0x10000012C cannot create a hole in the RAM address space because the RAM is mapped from 0 to 0xffffffff. I attached a picture that hopefully makes this clearer.

In summary: when we say "memory-mapped register" what we really mean is "physical-address-space-mapped register", this has nothing to do with RAM.

Note, however, that any peripheral (memory-mapped or not), could also use some RAM, through DMA. But this is a totally different thing because by doing so it does not steal any physical address (and thus does not create a hole).

Finally note that all of this is simplified anyway because there isn't necessarily a unique physical address space in the system, each device may have a different view of the system. See 1 for a relatively clear explanation. Thus in the picture above, I am really referring to the CPU's physical address space.

1: Not your parents’ physical address space, Gerber et al, PDF


What are applications of the levels of the Chomsky hierarchy? I've recently finished a course on languages in computer science, so we covered characteristics of regular, context-free, decidable and semi-decidable languages. While that is all well and good, we never went into any detail on what applications of this knowledge are (other than compilers being context-free language recognizers). I've tried googling for answers but wasn't able to find anything relevant. I'm wondering if someone can just explain what current applications for each 'type' of language are and perhaps link further material for reading.

Thank you.

First, let's be clear, there are two separate types of languages, Turing Decidable (also called recursive), and Turing Recognizable (also called semi-decidable or recursively-enumerable).

The "application" of decidable languages is all of computer science. It's a huge class that includes exactly the problems that can be solved by algorithms. So you're not going to find specific applications like you would for compilers and CFGs, because the applications covered by decidable languages are "everything else." If you can write code for it, it's in this class.

Recursively-enumerable problems are ones where you know a solution when you see one, but might never know when you're out of potential solutions. You always halt on a "yes" answer, but might never halt for "no". This class is basically first-order theorem proving: we recognize proofs when we see them, but with quantifiers, there's no way to know if no proof exists.

It's also worth mentioning that parsers are CFG recognizers. Other parts of compilers, like translation and type-checking, are definitely not context-free.


Fast solution for a combinatorial maximizaton problem You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (consisted of not necessarily consecutive bits). Now we have to find the maximum number from the numbers in S so that every pair of numbers is "compatible" and I want an example numbers from S with that maximum. Here is an example of the task:

n = 6;
S = { 000000, 000001, 000010, 000011, ..., 111110, 111111 };
The maximum number from the numbers in S with that property is 10.
Here is an example:
000000, 000011, 110000, 001100, 010010, 001111, 111100, 110011, 101101, 111111

I tried making some greedy solutions but they aren't working on greater n (and I think they can't be made accurate). When I thought of some graph solutions I reached an NP problem (let each binary number is vertex and we have an edge connecting them if they aren't "compatible"; now we have to find the maximum in vertices independent set). The other way I tried is making a bipartite graph with one set of vertices with the binary numbers of length n and the other with the binary numbers of length n-1. We have an edge from the first to the second set if the number from the second could be a substring of length n-1 of the number in the first. Now we have to find the maximum number of vertices from the first set so that their edges do not have any common endpoint vertex but I couldn't think out the solution of this problem and couldn't find it in the Internet.

You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that

The Varshamov-Tenengolts code (specifically $VT_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum_{i=0}^{n} i\cdot x_i \equiv 0 \mod n+1$ where $x_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.
The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.
No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).


Predicate calculus- meaning of the word "any" In the following 2 statements -

1. Anyone who eats any pumpkin is a nutrition fanatic.
&forall x ((&exist y (PUMPKIN(y) &and EAT(x,y))) &rarr FANATIC(x))

2. Anyone who buys any pumpkin either carves it or eats it.
&forall x &forall y (PUMPKIN(y) &and BUY(x,y) &rarr CARVE(x,y) &or EAT(x,y))

In the first case any pumpkin is given by &exist and

in the second case any pumpkin is given by &forall

Why the second case is also not given by &exist?

So I am assuming your question is: Why is the formula to "Anyone who buys any pumpkin either carves it or eats it."

$\forall x \forall y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

instead of

$\forall x \exists y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

The problem with your version is that there might be someone who buys a pumpkin and decides not to eat or carve it and this would contradict the statement that every bought pumpkin (by a person $x$) will be either carved or eaten.


Random restarts for unsatisfiable instances In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice.

One technique used, that has shown good results in practice, is random restart. Intuitively, randomly restarting means there is a chance of getting luckier with guessing the right variable assignments that would lead to a quick solution.

The same intuition suggests this should be much more effective when the problem instance is in fact satisfiable (so you only need to guess a set of variable assignments that constitute a solution) than if it is not (so in principle you have to check all possible assignments anyway, modulo sections of the search space that can be skipped via techniques like unit propagation and non-chronological backtracking, which are at least not obviously sensitive to the initial guesses).

Is the second intuition correct? Are random restarts in fact much more effective, on average, in cases where the problem instance is in fact satisfiable?

There is some research in this area.  In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both satisfiable and unsatisfiable SAT instances.  The theoretical justification for the speedup is that in CDCL solvers a restart allows the search to benefit from knowledge gained about persistently troublesome conflict variables sooner than backjumping would otherwise allow the partial assignment to be similarly reset.  In effect, restarts allow the discovery of shorter proofs of unsatisfiability on average.


Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem? My professor presented the halting problem as $K' = \{ w \in \{0, 1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent to $K = \{ \langle M,v \rangle | M $ Halts on $v \}$.

I tried to think it through and this is my understanding so far:

$(1)$ If $w \in K'$ then we can define $f(w)= \langle M_w,w \rangle$ then $w \in K' \Leftrightarrow  f(w) \in K$ so we have that $K'$ can be reduced to $K$

$(2)$ And for the other way around, we define $g(\langle M,v \rangle) = \langle M' \rangle$ where $M'$ is the TM that simulates the TM $M$ on input $v$ and halts iif $M$ halts on that input. So we get that both languages are reducible to each other thus equivalent.

But I'm not sure about part $(2)$, is the reasoning correct? Can someone shed some light on my problem?

The two languages aren't equal. However both $K$ and $K'$ are undecidable.

Proof:

We know that:
$K = \{ \langle M , v \rangle | M$ halts on $v$ }. Let us construct another language: $K'' = \{ \langle M , \langle M\rangle \rangle | M$ halts on $\langle M \rangle \}$. Note that $K'' \subset K$ because we replaced $v$ by $\langle M \rangle$ (encoding of $M$). Also note the similarity of $K'$ and  $K''$.

If you prove that $K'$ is undecidable, we can conclude that $K$ is undecidable.

You might have proved that $K'$ is undecidable.


Maximum Enclosing Convex Polygon of a Given Area My question is very similar to another solved question. As the title indicates, the major difference in my question is that I need to find the convex polygon that encloses the maximum number of points with a given area (instead of finding the circle that encloses the maximum number of points with a given radius).

So my question is as the following:

  Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a convex polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

I already checked on the Minimum bounding box algorithms and Convex hull algorithms. I also found some implementations for Minimum bounding polygon. However, those previous algorithms don't consider the concept of determining the convex polygon that encloses as many points as possible of a given set of points and a given area. Finally I invented an approach to solve the problem but it doesn't work in some cases.

The idea of my approach is to start by finding the minimum bounding box for all the points. If the resulting polygon's area is greater than the given area, I cut off one of the edge points according to some technique, then I re-compute the minimum bounding box and test the area. I keep looping until I reach the desired area. I won't get into details with my approach as it's not working properly.

EDIT

As a simplified solution, finding any rectangle (it doesn't have to be axis-aligned) that encloses the maximum number of points with a given area would be very beneficial and works as a temporary solution for my problem.

It sounds like your problem is the following:

  Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

This problem looks pretty tough to me, and I don't have a great algorithm for it, but I'll suggest two schemes.  The first solves a simplified version of this problem (for rectangles instead of arbitrary polygons), and the second is a heuristic algorithm that might or might not work "well enough" on real-world instances.

Simplified variant: rectangles

Suppose we focus on the easier case where $\mathcal{P}$ must be an axis-aligned rectangle.  Then I can give a $O(n^2 (\lg n)^2)$ time algorithm.

Without loss of generality, the $x$-coordinate of the left and right sides of this rectangle must agree with the $x$-coordinate of some pair of points, and similarly for the top and bottom sides.

So, guess the $x$-coordinate of the left side of the rectangle (there are $\le n$ possibilities), say $x_L$.  Now, do a binary search on the width of the rectangle (there are $\le n$ possibilities), using the following ideas.

Given a guess at the width $w$ of the rectangle, you can calculate the maximum number of points that can fit in an allowable rectangle with those $x$-coordinates for the left and right sides, as follows.  Start by filtering out all points whose $x$-coordinate is not in $[x_L,x_L+w]$.  Sort the remaining points by their $y$-axis.  Now look for the $y$-value $y_B$ for the bottom side of the rectangle, which maximizes the number of remaining points whose $y$-coordinate is in the range $[y_B,y_B+A/w]$.  This can be found with a straightforward linear scan of the remaining points (with two pointers advancing monotonically).

With this, given $x_L$, you can do a binary search for $w$.  Each guess at $w$ takes $O(n \lg n)$ work to compute the maximum number of points that can be fit into a rectangle of that sort.  Since there are $\le n$ possible values for $w$, you'll do $O(\lg n)$ iterations in the binary search.  Since there are $\le n$ possibilities for $x_L$, the overall running time is $O(n^2 (\lg n)^2)$.

Since a rectangle is a convex polygon, this gives you a lower bound on the number of points that can be covered by a convex polygon with area $\le A$.  It might not be an especially tight lower bound, but maybe it's a start.

Heuristic for arbitrary polygons

We could use branch-and-bound type techniques here.

Define a directed acyclic graph (dag), the search dag, where each vertex is a convex polyhedron $\mathcal{P}$ obtained as the convex hull of some subset of the $n$ points, and there is an edge from $\mathcal{P}$ to $\mathcal{Q}$ if there is some point $p_i$ not in $\mathcal{P}$ such that the convex hull of $\mathcal{P},p_i$ is $\mathcal{Q}$.  The root of this graph is the empty polyhedron, which covers no points.  Call any node of this graph that has no out-edges a "leaf".  The best polyhedron must be some leaf.

A naive approach would be to do a breadth-first search on this dag.  Unfortunately, the dag is probably exponential in size, so this naive approach will probably be too slow.

You might do better using branch-and-bound techniques.  Define the "quality" of a leaf in this graph to be the number of points covered by its associated polyhedron.  Also, define the "quality" of a node $x$ in this graph to be the maximum of the quality of all of the leaves that are reachable from $x$.  Of course, we cannot compute the quality of a node without exploring everything reachable from it (which is too expensive), but we can estimate it.

In particular, we can compute an upper bound on the quality of any given node.  This is enough to do branch-and-bound.  We basically iteratively explore the graph.  At each stage, we keep track of the "best" solution we've found so far: i.e., among all the polyhedron $\mathcal{P}$ corresponding to some node we've visited, keep track of the maximum number of points covered by any of these.  Say this number is $b$.  Now if we reach a node $x$ where our upper bound on its quality implies that the quality of $x$ is $\le b$, then we don't need to visit $x$ or any of its descendants.  This might help us reduce the search space.

How do we get an upper bound on the quality of a node?  Well, here's one way.  Suppose we have precomputed, for each $i=1,2,\dots,k$, the minimal area of any convex polygon that contains $i$ points, call it $\alpha(i)$.  Now if we have a node $x$ that corresponds to a polyhedron $\mathcal{P}_x$ of area $A_x$, and if $A_x+\alpha(i) > A$, then here's an upper bound on the quality of $\mathcal{P}$: it must be at most the number of points contained in $\mathcal{P}$, plus $i-1$.  This could be a somewhat loose bound, but it is something.

How do we do the precomputation?  Well, that's basically an easier instance of the same problem, with a smaller value for $A$.  So, we can do the precomputation via a recursive or iterative application of this algorithm, for increasing values of $A$ (or via similar ideas).


Compiler Question : Does the parser detect Errors in these examples or the Semantic routine? For example, which part will detect these errors, Parser or Semantic Routine?
1) int Array[10.5]  ( wrong size )
2) int x="some string"
3) A[10.5] + 3  (not in declaration, but in the middle of the code)
The book that I'm reading says the first one will be detected by parser but the third one will be detected by Semantic routine! I don't get it? why not both of them by parser? if the parser can detect first one, then it should be able to detect the third one
ALSO, i thought that lexical analyzers usually turn every number into a same token? for example:
a = 3.5 + 5 --> id = num + num
so how can parser or semantic analyzer differentiate between a real number and a integer number?
Lets assume our compiler is a modern day compiler for C for example.

It's impossible to say in general; it depends on the compiler resp. the exact definition of the syntax.

If your language contains special syntax for array declarations, the parser will note that it doesn't find an integer literal between the brackets.

For array accesses, the language probably allows arbitrary arithmetic expressions (including function calls) between the brackets. So the parser will create an expression tree, and only the type checker will determine that the expression is not of type integer.


Is an intersection between NPC and coNPC always DPC? The class DP is defined as the set of all languages $L$ such that $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$.
For example, the language SAT-UNSAT is defined in the following manner ($\varphi$ is a $3-CNF$ formula):
$\{( \varphi, \varphi'): \varphi \in SAT \wedge \varphi ' \in UNSAT \}$. This language is the intersection of:
$$L_1 = \{ (\varphi, \varphi'): \varphi \in SAT \} $$
And:
$$ L_2  = \{ (\varphi, \varphi'): \varphi' \in UNSAT \}. $$

Given $L_1$ which is known to be a NP complete problem, and $L_2$ which is known to be coNP complete problem, does $L_1 \cap L_2$ necessarily DP complete?
(I believe that the answer is yes, because I can use the reduction of $L_1$ and $L_2$. But I am still not very confident in this idea.)

NO, it is not always so.

$L_1=\{<0,\varphi>|\varphi\ \mathrm{is\ satisfiable}\}$

$L_2=\{<1,\varphi>|\varphi\ \mathrm{is\ unsatisfiable}\}$

$L_1\cap L_2=\emptyset$

EDIT: As commented below by David Richerby, $L_1=SAT$ and $L_2=UNSAT$ would likewise falsify your claim in the question.


DTM that halts on a minimum one input I am trying to show that this is Turing Recognizable.

The language A, that is a DTM, T, that halts on a minimum of one input.

My justification is that of course it is because, you just need to check if an accept state is reachable. However, this seems like I am making it trivial.

Is there something larger I am missing?

EDIT: New Idea

Let M be a DTM that does this:

For every string w in the language,
simulate w on T.
if it halts, accept.

The only problem I see with this, is if a string causes it to loop forever, then it will never try the others.

Hint: Use the technique of dovetailing, mentioned in several of the comments. The idea is to maintain a growing list of simulated Turing machines, all of them copies $T_1,T_2,\ldots$ of the input Turing machine $T$, operating as follows:

Initialize $T_1$ with the $1$st possible input, and run $T_1$ for one step.
Initialize $T_2$ with the $2$nd possible input, and run $T_1$ and $T_2$ for one step each.
Initialize $T_3$ with the $3$rd possible input, and run $T_1,T_2,T_3$ for one step each.
And so on.

You get the idea. It is perhaps not obvious how to maintain the states of several Turing machines at once, but you can figure it out on your own.


Can we compute the sum of a range of entries in $O(1)$ time? I have encountered a few tests in algorithms which ask for
a data structure which allows to get the sum of all the elements of an array in the range [i..j], in O(1) time.

Is it even possible to do so?

Yes, calculation of range sum is possible in O(1) time.
Suppose the data is given in an array. You need to preprocess the array to find the prefix sums. For this you need another array. To find range sum S(i,j] you need to compute P[j]-P[i]. Where P[j] and P[i] are entries of prefix sum array. For example, the given array is:
4 5 -2 5 -77 45.
Corresponding prefix sum array is:
4 9 7 12 -65 -20.
So, S(2, 4] = -65 - 7 = -72 (Sum from 2 to 4, 2 excluded and zero based indexing)

Note: We preprocess the given data to build the prefix sum array which takes O(n) time where n is the number of entries. After that, each query of the form S(i,j] takes O(1) time.


What does the "Lambda" in "Lambda calculus" stand for? I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from.

Can anyone explain the origins of the term?

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006):

  By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to distinguish function abstraction from class-abstraction, and then changing “$\wedge$” to “$\lambda$” for ease of printing. This origin was also reported in [Rosser, 1984, p.338]. On the other hand, in his later years Church told two enquirers that the choice was more accidental: a symbol was needed and “$\lambda$” just happened to be chosen.


Why don't we use simple binary values to compress data? In Huffman's algorithm, we form a tree and than replace each character with the tree value of 1 and 0. Why don't we simply use the binary digits like $a=0$, $b=1$, $c=10$, $d=01$, $e=11$ and so on than replace them with the characters and when decompressing aplly the reverse and replace the binary digits with the alphabets?

Suppose we code, as you suggest, $a=0$, $b=1$, $c=10$, $d=01$, $e=11$, etc., and I send you the message $1001$. You can't tell if I said $10\,0\,1=cab$, $1\,0\,01=bad$. The point of the Huffman scheme is that it's a prefix code, so it's uniquely decodable (and, further, you can always decode the start of the message based on the bits you've already seen, without having to look into the future).


Equivalance of NFAs, understanding the solution This solution comes from https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/practicefinal-sol.pdf

  Consider the language

  $$ EQ_{NFA} = \{ \langle N, N^\prime \rangle \mid N, N^\prime \text{ are NFA's with the same alphabet and } L(N) = L(N^\prime) \} $$ show
  that $EQ_{NFA} \in \textbf{PSPACE}$.

  (hint: Can you convert this to a appropriate reachability problem?)

  Solution Outline: Suppose $N$ and $N^\prime$ both have at most $n$ states. We can then convert them into DFAs $D_N$ and
  $D_{N^\prime}$ with at most $m = 2n$ states each using space
  polynomial in $n$. Finally, we can construct a DFA $S$, which is the
  product of $D_N$ and $D_{N^\prime}$ (with at most $m = 2^n$ states)
  and accepts $L(D_N)\Delta L(D_{N^\prime})$ (strings that are in
  exactly one of the languages). Now, $L(N) = L(N^\prime)$ iff $L(S) = \emptyset$ i.e. none of the final states are reachable from the start
  state in $S$.

  Since this is a reachability problem, it can be decided
  nondeterministically using space logarithmic in the size of the graph
  (because $PATH \in NL$). Thus, this problem can be decided in
  $NSPACE(\log{(m^2)}) = NSPACE(n) \subseteq NSPACE(n^2) \subseteq PSPACE)$.

I see that it works and I see that the last paragraph try to convince that it is actually $PSPACE$.  But, I have a doubt:

After all, the solution constructs two exponential automats. How is it possible?

My intuition is that:
We can compute DFA for NFA using $\log n$ memory on working tape. Obviously, we have to use exponential size of memory but on the output (readonly) tape.

Now, when we construct it we can use it in reachability problem which works in $NL$. We know that composition of $LOG$ function is $LOG$. Is my understanding correct? Does the same apply (I mean a composition of functions) when it comes to $NLOG$?

Your confusion is understandable.  The solution outline you've quoted misses an important point and suggests the opposite of that point.

The DFAs are, as you say, exponentially big.  We can construct them, but not in polynomial space.  However, the key point is that we don't need to construct and store the whole automaton.  The reachability algorithm doesn't need that.  All it needs is the ability to know what state it's in at the moment and construct the list of states it could move to next.  Both of these can be done easily, on the fly, from the description of the NFAs.  Likewise, we don't need to literally construct the product automaton: we can do that implicitly as well, by just tracking our position in each automaton separately.

Let's do a simplified example.  Suppose that we just want to know if a particular NFA $N = (Q, \Sigma, \Delta, q_0, A)$ accepts at least one string, i.e., if an accepting state is reachable from the initial state.  In this simplified scenario, we could just work directly with the NFA but we'll ignore that and convert to a DFA, $M$.  If $N$ has $n$ states, then $M$ will have $2^n$ states so, if we were to write out its full transition graph, we'd need exponential space.

However, the reachability algorithm doesn't require us to write out the whole graph.  As it runs, it says things like, "OK, I'm at vertex $v$. Where can I go next?"  Normally, we imagine that it looks up that vertex in the graph's adjacency matrix to answer this question, but that's not the only way. It could calculate what vertices can be reached, using the rules of the subset construction that generates $M$ from $N$.  Specifically, if we're at vertex $v$ then $v = \{s_1, \dots, s_\ell\}\subseteq Q$ and the vertices we can move to are the vertices of the form $\Delta(s_1,a)\cup\dots\cup\Delta(s_\ell,a)$ for each symbol $a\in\Sigma$.  Each such vertex is a subset of $Q$, which we can write down in $n$ bits, and there are at most $|\Sigma|$ different possibilities, so you can write all of them down in $n|\Sigma|$ bits, which is polynomial in the size of $N$.  Once the reachability algorithm has decided what to do next, it can forget this list of vertices and re-use the space.  If it needs to access the list of $v$'s neighbours again, it can recalculate it.

The reachability algorithm never needs the whole adjacency matrix of the graph to be written down at the same time.  Pretend, for a moment, that we did have the graph written down.  Since the graph has $2^n$ vertices, we would need  working space $O(\log 2^n) = O(n)$ to run the algorithm. Now, instead of writing the adjacency matrix down, we'll calculate it on the fly.  That will require additional working space $O(n)$ for the calculations of what the adjacency matrix is.  So the total space used is still $O(n)$, even though the graph can't be stored in that little space.

By the way, this trick of calculating things on the fly is a common trick in logarithmic space computations.  Another prominent example is showing that logspace reductions compose (i.e., if there are logspace reductions $A\to B\to C$ then there's a logspace reduction $A\to C$). What you'd like to do is just do the first reduction, store the result on a tape and then apply the second result to that; but you can't because the result of the first reduction might be too big to store.  So, instead, you start with the second reduction. Every time you need to know some character of the output of the first reduction, you recompute it from scratch.


How do multiple branches from one node occur with the Monte Carlo Tree Search? I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (right?). So, a branch never comes out from a non-leaf node. So how could one node have multiple branches (multiple child nodes) coming out of it? Here's a picture, for clarity:

So wouldn't that process just keep getting repeated? It's not a leaf node, so the algorithm won't branch (create another child node)... so it has to pick the next node. And since it only has one option, it must pick that one. It just continues down, until it reaches the end. What's the point of that?

I'm probably missing something big here, but all the pages I've look at don't really explain this. It just magically repeats selection, expansion, simulation, and back-propagation, until it constructs a nice tree at the end. How?

EDIT:
I figured it usually creates only one child node because of this taken of this source:

  In its simplest and most memory efficient implementation, MCTS will add one child node per iteration.

Also, even if you create just two or three, would that really be enough to cover all the possible moves, especially if the branching factor is large? How would one determine how many child nodes to create?

It sounds like you're reading a summary/overview.  You might be reading too much into one sentence there.  The sentence says "MCTS will add one child node per iteration".  That doesn't mean each node will have only one child after the process finishes.  You might have one iteration that adds one child of X, and a later iteration that adds another child of X, and an even later iteration that adds yet another child of X, and so on.

Similarly, nothing says that MCTS is limited to adding only two or three children per node.


Worst case using the first fit $2$-approximation for the bin packing problem I am with the phone so I would be more verbose when I will have a pc on hand, if you desire.

The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the optimum. Can you show me a concrete worst case showing that $2$ is a good (or bad) extimate for the bound?

The approximation ratio of first fit for bin packing is actually 1.7 rather than 2. See Dósa and Sgall, First fit bin packing: a tight analysis. The paper contains references which prove a matching lower bound.


What are practical applications of AI Planning? note: any tips toward making this more constructive will be highly appreciated.

I've dealt with ai-related problems, from searching algorithms, to computer vision, to machine learning. However none of which required planning, just algorithms following algorithms.

I'm not sure how effective will it be to implement AI Planning in practical problems, so I'm curious to know if there's a significant effect in doing so. Like at what point does the programmer/designer realize we need to apply AI Planning to solve this.

[In the following, I am providing links to some events in 2011/2013, but you can find much more looking for previous years]

By AI Planning I assume that you mean Automated Planning (STRIPS, SAS$^+$ and so on) instead of path-planning and other problems more tightly related to robot navigation. If this is the case, SPARK is the right forum to look at.

Other practical applications are often discussed at the main track of the conference ICAPS. A couple of examples:

Maria Fox, Derek Long, Daniele Magazzeni: Automatic Construction of Efficient Multiple Battery Usage Policies. ICAPS 2011
José E. Flórez, Álvaro Torralba Arias de Reyna, Javier García, Carlos Linares López, Angel García Olaya, Daniel Borrajo: Planning Multi-Modal Transportation Problems. ICAPS 2011 (admittedly, I am adding here a reference of my own, beg your pardon, I did just because it was easier for me to locate the reference).

Hope this helps,


Do compression tables exist and where are they used? Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, and by compressing certain bit orders.

So for example, we have 010111111111110101

A zip file would look something like:

x = 0101

x|repeat(1,8)|x

So the zip compression creates its own table of arrangements that it finds.

But, is there anything that already uses a predetermined table? For example you'd have a table like:

x = 010101010101010101010110010101010101010101010101...
y = 10101...
...

And then I'd download a file that follows this compression table, without having to download the table because you already have it.

So my question is, is this method used anywhere, and why or why not?

The big advantage of Lempel-Ziv-style compression is that

it creates its own dictionary on the fly and
tailors it to the data. Therefore, they are
general-purpose compression algorithms which
can be used without having to keep dictionaries in sync; all you need for
decoding is the encoded file and the algorithm.

If you fix a dictionary, this is going to perform well for some inputs. For instance, you can order all English words by frequency in some corpus, number them and store a sequence of these numbers instead of the words themselves. This will then work very well for English texts similar to your corpus, worse for other texts, and not well at all for weather data or images.

Note that LZ-style compression is used in popular formats such as (g)zip, PNG and GIF.

FLAC is one noteable format that uses something different, namely linear predictors. In a certain sense, you can view this as a fixed (though conceptually infinite) dictionary; the method estimates parameters of a certain model and represents bits of data by these parameters (plus some error information). This works well because the model fits the kind of data (apparently) very well, and the representatives are significantly smaller than the data itself. However, the decoder only knows the model; there is no fixed set of parameters everybody uses. So I don't think this fits your idea, either.


Complexity inversely propotional to $n$ Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?

Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $\mathbb{N}$.
In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $\forall n\colon f(n)\ge 1$. So no such algorithm can exist.


Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise to the reader. Even Stockmeyer's original paper on the hierarchy (this one, right?) proves the result in a "Remark." section, so it's not exactly the most detailed proof.

Just so we're clear, i did write my own version of the proof; it's exactly because of all the work i had to do in order to prove said result, contrasted with the one-paragraph proofs commonly found in the literature, that makes me curious about what kind of insight i might be missing.

As for how my proof proceeds, i can give an high-level overview of the harder direction. Using the certificate version of the hierarchy, and second-order logic with alternating quantifier blocks, the proof goes by induction. Base case is Fagin's Theorem. For the inductive step, you have a second-order formula deciding the input+certificate relation, so all you need to do is to introduce some existential quantifiers over the given formula quantifying all of its relational symbols, plus a formula that states that the interpretation given by the quantifiers does contain the input.

Of course, like any high-level overview, this is easier said than done. At least in my proof, there's a fair amount of translating in order to make things work. Plus there's the fact that the usual certificate definition is over languages, and we're dealing with arbitrary finite structures, so there's some conversion there too. Then you have to prove that all the stuff you did is in fact correct. All in all, it's not pretty.

So i have to ask: Is there any proof of this result that isn't afraid of working out some of the details, but has the same intuitive clarity as the usual short proof?

It's one of those proofs that's essentially obvious once you can prove Fagin's theorem that the existential fragment of SO is exactly NP. Alternating quantifiers in the SO formula takes you up the polynomial hierarchy more or less by definition.

Proposition 7.35 of Libkin's Elements of Finite Model Theory proves that MSO expresses complete problems at every level of PH. Corollary 9.9 of the same book is that SO=PH; but the proof consists of a sketch with an exercise to fill in one of the steps.  The proof that SO=PH is also essentially Exercise 7.5.18 of Ebbinghaus and Flum's Finite Model Theory (2nd ed.). Immerman's Descriptive Complexity states the equivalence as Theorem 7.21 and Corollary 7.22 but leaves the proof as an exercise and credits the result to Stockmeyer's paper.

Given all of that, I doubt you'll find a proof in print. The details probably are fiddly but your outline sounds correct.


predication, branch prediction question I have a question about predication and branch prediction.

I've emailed my professor regarding this and he replied me that predication has a less instructions than branch prediction.

So I tried making an example of my on but I'm not sure if this is right..

I've assumed for predication it has 'if' and 'else' each having 100 instructions.
Then either right or wrong, it will waste 100 instructions.

For prediction(since this has more instructions), I've assumed it has 'if' and 'else' each having 300 instructions doing exactly the same thing as the predication above.

My questions is..

Is it even possible to make 300 instructions to 100??
In above case, if predication has to win over the benefit of branch prediction, accuracy of prediction should be below 66.6%.
(300*0.3333=100) Is this correct?
If so, when deciding which would be better off than which, does it has to be based on accuracy of a prediction or the size? Reason why I am mentioning size is because during the lecture, I remember my professor saying "use predication in small size loops..."

Thanks in advance..

You are absolutely, completely on the wrong path here.

Predicated instructions are used to avoid branching. A predicated instruction avoids the cost of a branch plus possible penalty for a mispredicted branch.

If you have 100 instructions on the if and the else side, then you would need 200 predicated instructions instead of 100 unpredicated instructions to save a branch and possible mispredicted branch penalty. 200 vs. 100. That's not going to save you anything.

What on earth makes you think you would have 200 predicated instructions, and 300 unpredicated instructions on each path? I'd say you are completely misunderstanding what your professor is saying there.

I strongly suggest that you download an Intel or ARM instruction manual and study what predicated instructions are doing, because right now I have the impression that you are operating blindly without any understanding.

Maybe it would help if you wrote down how you would (in an assembly language of your choice, or an invented one) translate "if x > 0 then y = 1 else z = 2" using a conditional branch, and using predicated instructions.


DP - Removing contiguous subsequences from a sequence optimally I was asked this question a while ago and I'm very stuck:

  You have a sequence of 0's and 1's, and you can perform one operation it: removing at least $K$ consecutive 0's or $K$ consecutive 1's from the sequence. After performing one of these operations, the ends of the sequence that are on the sides of the removed portion come together and close the gap created by the removal.

  Can you make operations such that the sequence becomes empty? If so, what is the least number of operations that you can make? I'm hazy on the restraints on the problem, but assume both $N$ and $K$ have at most two digits, and that $K$ is a lot smaller than $N$.

  For example, say you have the sequence 1111000001, and $K = 5$. The solution is to remove the middle line of 0's. You cannot remove any 1's on the first step, because the longest consecutive substring of 1's is only four long. Afterwards, however, the gap closes, and the sequence 11111 is created, which can also be removed, creating the desired empty sequence. Only two operations are needed to make the sequence empty.

I believe that this is a DP problem, but I'm having trouble on what to represent as a state and how to construct a state from previous ones. Could anyone give me a hint?

First collect the consecutive alphabets together. Say the input string is "1110000110100" then I mean form the array $A=\{(3,1),(4,0),(2,1),(1,0),(1,1),(2,0)\}$ where an element (  called chunk ) of $A$ $(a,b)$ means there are $a$ consecutive $b \in \{0,1\}$. Now the problem has been reduced to removal of chunks and we will concern ourselves with $A$ rather than the original string.
Now make a DP table $D$ where $D[i][j][k]$ means least number of steps used to removed all chunks till $A[i]$ such that last chunk removed was of $k \in \{0,1\}$ and the size of the last chunk removed was $j$. If it is not possible assign it $\infty$ ( take care of the boundary cases and initial condition for table $D$ ).
Now say you are at chunk $i$ and it is a chunk made of 0's and it's size is $t$. Now you have to fill the table $D[i][][]$ given that you have already filled the tables $D[1][][],D[2][][]......D[i-1][][]$. You have two options (a) If $t \ge K$ remove this chunk first and now you are left with subproblem with $A[1]...A[i-1]$; (b) or if its possible to remove the chunks of 1's before , and then if the chunk of 0's get's size greater than equal to $K$, you can remove it ( rwe will take minimum of all cases while filling the DP table ).  As you asked for only hint I leave it upto you for coming up with the recurrence relation.

As you said $N$ and $K$ are small, I think this method would suffice.


Maximum number of similar groups of a given size that can be made from a given array I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.

I need to find the maximum number of groups with the exact same contents and of size $A$ that can be made from the elements of $B$. Once an element is used in a group it is exhausted. A group can have more than one element with the same value as long as the element is still available in $B$.

Example:

If the input array is $\{1, 2, 3, 1, 2, 3, 4\}$, and the group size is $3$ the maximum number of groups that can be made is $2$, which are $\{1, 2, 3\}$ and $\{1, 2, 3\}$.
If the input array is $\{1, 3, 3, 3, 6, 3, 10\}$, and the group size is $4$ the maximum number of groups that can be made is $1$, which is $\{1, 3, 3, 3\}$.

What I have tried so far, is to frame some equations ( given below ) but after that, I am struggling to come up with an algorithm to solve them.

Let $F_1$ be the frequency of the element $B_1$, $F_2$ be the frequency of the element $B_2$ and so on till $B_n$, where $B_1 \dots B_n$ are distinct elements from the array $B$.

Now I need to choose $n_1, n_2, \dots n_i$ such that

$n_1 + n_2 + \dots + n_i = A$
$k\cdot n_1 \leq F_1\text{ , } k\cdot n_2 \leq F_2\text{ , }\dots \text{ , }k\cdot n_i \leq F_i$
$k$ is the number of groups and we need to maximize it.

Length of $B$ can be as large as $10^5$ and $A$ can also be as large as $10^5$.

Please help me find a greedy or dynamic approach to the problem.

The function
$$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) =
\begin{cases}
1; &\text{if there is a solution of size $k$,}\\
0; &\text{otherwise}
\end{cases}
$$
is monoton, since if there is  no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $k$ for which there is a solution of size $k$. Thereby, we turned the problem into a decision problem with an $O(\log |B|)$ factor in the running time.

For a fixed value of $k$, a greedy solution suffices. If we have $F_i$ copies of some element $B_i$, then each set can contain at most $\left\lfloor\frac{F_i}{k}\right\rfloor$ of this element. So we have a solution of size $k$ if and only if
$$\sum\limits_{i=1}^{n} \left\lfloor\frac{F_i}{k}\right\rfloor \geq A.$$

As an exercise, try to prove that the greedy solution is optimal. The running time can be bounded in $O(|B|\log|B|).$


Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept.

I understand that the pumping lemma can be used to show that if a language has a length greater than the number of states, which is the pumping length, then it may not be a regular language. However, I don't understand how a language can be rejected by a DFA based on the number of accept states it has.

For example, I know that a* \cup b* is not a regular language because of the pumping lemma, but how do I know that it is not accepted by a DFA with only 1 accept state?

$\{\lambda, a, a^2, \dots, a^n\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).


If $L_1,L_2\in \mathrm{NP}$ and $w\in L_1$ or $w\in L_2$ then can $L_1\cup L_2=L$'s verifier use the same certificate $c$ for $w$? I read the following solution for Showing that $\mathrm{NP}$ is closed under union
and they used the same $c$ for both the verifies $V_1$ and $V_2$. Why is it correct?

Let $L_1$ and $L_2$ be languages in $\mathrm{NP}$. Also, for $i = 1, 2$ let $V_i(x, c)$ be
an algorithm that, for a string $x$ and a possible certificate $c$,
verifies whether $c$ is actually a certificate for $x \in L_i$. Thus, $V_i(x,c) = 1$ if certificate $c$ verifies $x \in L_i$, and $V_i(x, c) = 0$ otherwise.
Since both $L_1$ and $L_2$ are both in $\mathrm{NP}$, we know that $V_i(x, c)$ terminates
in polynomial time $O(|x|^d)$ for some constant $d$. To show that $L_3 = L_1 \cup L_2$ is also in $NP$, we will construct a polynomial-time verifier $V_3$ for $L_3$. Since a certificate $c$ for $L_3$ will have the property that
either $V_1(x, c) = 1$ or $V_2(x, c) = 1$, we can easily construct a
verifier $V_3(x, c) = V_1(x, c) \lor V_2(x, c)$. Clearly then $x \in L_3$ if and
only if there is a certificate $c$ such that $V_3(x, c) = 1$. Notice also
that the new verifier $V_3$ will run in time $O(2(|x|^d))$, which is
polynomial. Therefore, the union $L_3$ of two languages in $\mathrm{NP}$ is also in $\mathrm{NP}$, so $\mathrm{NP}$ is closed under union.

taken from here.
$M_1,M_2$ TM which accept $w$ can accept $w$ for different reasons so we can't claim that $c_1=c_2$
Questions:

Is it legal to use the same certificate for both $V_1,V_2$ in the answer? Why?

Is a verifier by definition is deterministic TM?

In the above answer, does $V_3$ runs $x,c$ on both $V_1$ and $V_2$ in the worst case?

Assume that $c_1$ and and $c_2$ are polynomial size certificates for $x \in V_1$ and $x \in V_2$. Then define $c=c_1\#c_2$, a new certificate formed by concatenation of $c_1$ and $c_2$ which is clearly polynomial size. Then $V_1$ and $V_2$ still can use $c$ as a certificate to verify $x\in V_1$ and $x\in V_2$. $V_1$ will use the left part of $c$ and the $V_2$ will use the right part of $c$.

  Is a verifier by definition is deterministic TM?

Yes, the verifier is a deterministic TM, by definition.

  In the above answer, does $V_3$ runs $x,c$ on both $V_1$ and $V_2$ in the worst case?

You can treat $V_3$ as a TM which invokes (as subroutines) $V_1(x,c)$ and $V_2(x,c)$, so if $V_1$'s worst case is $O(f)$ and $V_2$'s worst case is $O(g)$ then $V_3$'s worst case is either $O(f)$ or $O(g)$ which is polynomial.


Perform an operation on an array in O(n) I'm required to perform the following operation on an array in O(n): P[1..n] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the beginning of the array until I reach an element whose value is greater than P[i], or reach the beginning of the array. The output of the function should be an array S[1..n] that contains these values.

For example, if:

 P = [ 4, 3, 6, 1, 2, 7, 9 ]

Then I must create this array:

 S = [ 1, 1, 3, 1, 2, 6, 7 ]

If I start at P[3] (=6), I can advance 3 cells until the beginning of the array, and therefore S[3] = 3; but if I start at P[5] (=2) I will advance only 2 cells and reach P[3] (=6 > 2), so S[5] = 2.

Implementing such algorithm in O(n^2) is trivial, but I'm required to do so in O(n). I was hinted to use a stack.

Yes, you can perform this operation in $O(n)$ using a stack $\mathbb{S}$.

Before presenting the algorithm directly, I would like to give you an illustration using your example. It is not difficult for you to discover the basic idea on your own.

For your example, I give the states of the stack $\mathbb{S}$. Element $P[i]$ and its $S[i]$ are denoted by a pair (P[i], S[i]). The stack reads from left (bottom) to right (top).

Notice which elements are popped before (when) $P[i]$ is pushed and how (and why) $S[i]$ is computed (described as // comments).

initialization: empty
P[0] = 4: (4,1)
P[1] = 3: (4,1), (3,1)
P[2] = 6: (6,3)    // 3 = 1 + 1 + 1
P[3] = 1: (6,3), (1,1)
P[4] = 2: (6,3), (2,2)  // 2 = 1 + 1
P[5] = 7: (7,6)   // 6 = 2 + 3 + 1
P[6] = 9: (9,7)   // 7 = 6 + 1

Here is the basic idea.

Stack $\mathbb{S}$ stores the elements $P[i]$ in array $P$ and its corresponding (already computed) $S[i]$.

Initialization: $\mathbb{S}=\emptyset; \quad \forall i: S[i]=0.$

For each element $P[i]$ in array $P$ in order:

$\textsf{Pop}$ the elements in stack $\mathbb{S}$, until it encounters a bigger one than $P[i]$. This step simulates the "advance toward" procedure. Meanwhile, compute the sum of the $s$ values of all elements that are popped by $P[i]$. Then, $S[i]$ for $P[i]$ equals $1$ plus this sum.
Then $\textsf{Push}$ $P[i]$ and its corresponding value $S[i]$ (just computed) into $\mathbb{S}$.


What's the flaw in the P != NP proof in the article "The Computational Complexity of the Traveling Salesman Problem" I am reading through some proof of inequality of P and NP
but they are not accompanied by the flaws in the reasoning so I'm  trying to find them by myself, just to see if I'm getting the logic right. As an example I am currently reading this (very short) proof that P != NP  and for me the lack in the argomentation is the following:
what the author writes about the algorithm is sacrosanct but does not deny in any way the possible existence of algorithms or tricks that would allow to solve the problem in polynomial time.

Am I right on this one?

Yes, you are right: there are plenty of other possible algorithms the author ignores. Briefly, the author claims that the $\Theta^*(2^n)$ dynamic programming approach in the paper is nessecary to solve TSP. However, he completely ignores any sort of structure that may or may not exist in TSP instances.

So, we can look at special cases of TSP where we do know that we have special structure to see their argument is insufficient. For a simple example, consider the graph class where there is exactly one tour with cost $X$ and all edges not part of this tour have cost $>X$. Clearly, we can find a tour in $O(|E|)$ by selecting all edges with cost $\le X$. Note that if the argument of this paper would apply to the general case, it would also apply to this one, so this is a contradiction with his argument. Clearly, even if the claim of the author is correct, he has not proven it.


Universal Hashing in Practice A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if
$$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$
You can find more about universal hashing this wikipedia article.

The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:

  Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?

Universal hashing (or near-universal) is a key ingredient in defending against algorithmic complexity attacks that engineer hash table collisions from user input.

See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".


Graph problem known to be $NP$-complete only under Cook reduction The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a Karp reduction since there is no restriction on the number of calls to the oracle. So, I am interested in NP-complete graph problem that does not have a known Karp reduction from a NP-complete problem.

  Is there a natural graph problem known to be $NP$-complete only under Cook reduction, but not known to be NP-complete under Karp reductions?

Naturalness should disallow specific features of feasible solutions, for otherwise it is quite easy to start from well-known problem and make it a little easier by allowing specific features.

I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.

Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.

Given a Boolean $(\wedge;\vee;\neg)$-formula $F$ and
an integer $k$, is there an equivalent $(\wedge;\vee;\neg)$-formula of size at most $k$?

On p. 143, the authors state:

  This provides a somewhat rare example of a natural problem for which a Turing reduction seems crucial (in the sense that we do not know of any simple modification or alternative methods that would give a many-one
  reduction).

They do not cite any other such examples from the literature. I suspect that "somewhat rare" is possibly an understatement.

References

David Buchfuhrer and Christopher Umans: "The complexity of Boolean formula minimization" Journal of Computer and System Sciences, Volume 77, Issue 1, January 2011, Pages 142-153


How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book? After defining pushdown automaton in Sipser's book at p. 113:

at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:

My question is about the part "If $a$ is $\epsilon$, the machine may make this transition
without reading any symbol from the input." But in many examples in the book, it seems some $\epsilon$s which are in place of $a$ must be interpreted as an empty string to show that the pointer is reached to the end of input. For example in the following diagram, we must interpret the first $\epsilon$ in the label of the transition between $q_3$ and $q_4$ to an empty string which shows the end of input string:

Otherwise, it can accept $01^2$. Since, if we interpret $\epsilon,\$\to\epsilon$ as to make this transition from $q_3$ to $q_4$ without reading the second 1, then $01^2$ would be accepted.

Now my question is how a PDA decides if that $\epsilon$ is for moving without reading any symbol from input or that $\epsilon$ is an empty string?

Suppose that your PDA is reading $011$.

At the beginning, the PDA is at state $q_1$, and the stack is empty. The only move the PDA can make is to put $\$$ on the stack and to transition to state $q_2$.

Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q_2$ which puts $0$ on the stack. The input is now $11$, and the stack is $0\$$ (top of stack first).

Since the next symbol to be read is $1$, the only move the PDA can make is to transition to $q_3$, erasing $0$ from the top of the stack. The input is now $1$, and the stack is $\$$.

Since the next symbol to be read is $1$, the PDA must move to $q_4$, erasing $\$$ from the stack. The input is still $1$, and the stack is empty.

At this point, the PDA is stuck. It cannot make any move. However, it hasn't read all the input yet. We conclude that there is no accepting computation for this input, and so the PDA doesn't accept $011$.


Fastest way to find the smallest interval of a number Here is my problem : Given a range, let's say 0 to 10.000, and some numbers in that range (like 23, 1456, 280, 3586), I want to find, for any input x, the two closest numbers to x, the smaller one the greater one. For example for x=100, the two numbers are 23 and 280, for x=350 they are 280 and 1456.

Is there a faster way to do that than a binary search on the list of numbers ? I vaguely remember the existence of a data structure for this task, but in my case the numbers are dynamic and will change during the execution of my algorithm.

The relevant phrase is  "predecessor search" .

For that, you can dynamically choose whether-or-not equality is allowed by

for each number in the range, storing 2 times that number rather than that number directly
and
for each actual query q, submitting  (2*q) ± 1  instead of q,

where the sign depends on whether you want to allow equality
and
dividing by 2 before returning

.

With that, the greater one can be found using predecessor search in the negatives of

the actual numbers.    For your case, you could simply reverse the range, like storing

10000-23,10000-1456,10000-280,10000-3586  rather than  23,1456,280,3586 .

Page 6 of this pdf gives upper bounds for dynamic predecessor searching

and references for data structures achieving those bounds.

This pdf gives another data structure which does what you want and much more.


How come {ww} isn't regular when {uv | |u|=|v|} is? As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language.

However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is a regular language. Because we can get the DFA like below,

DFA:

--►((even))------a,b---------►(odd)
      ▲                         |
      |--------a,b--------------|

My question is, $L = \{ w w \mid w \in \{a,b\}^* \}$ also has the even length of strings ($|w|=|w|$, definitely), so $L$ still can have some DFA like the one above. How come is it not a regular language?

well, there are things that a DFA can do, and things that DFA cannot do. A DFA is quite a simple machine, and it has no access to "memory". The only "memory" it has is its current state, i.e., a very limited memory. A DFA can do tasks that require finite amount of memory, but nothing more than that.

To check if the input is of even length  - is very simple task. It requires only 1 bit of memory (odd/even). therefore, it can be done by a DFA.

However, for the second language $\{ ww \mid w\in\Sigma^*\}$ the DFA needs to check that the first $w$ is identical to the second $w$. How can you do that with no memory? In fact, since $w$ can be of any length, a (one-pass) machine that checks that the two copies of $w$ are the same must have infinite memory (to accommodate any $w$..). But a DFA has only limited memory, and thus cannot solve this task.

at least, this is the intuitive explanation.


Can someone explain me the Credit-Debit proof method for calculating operations? I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with double the size of the original one.

The proof used to demonstrate this was a credit-debit proof where each operations has a cost. ex: doubling an array cost 2 dollars reducing an array by half cost 1 dollar.

I simply don't understand how proof of that type works. Doing a quick online search I haven't find the term credit-debit used to refer to this. Maybe It's not its name? Would be nice if someone could give me some links that explain those proofs.

I believe you are referring to the accounting method for amortized analysis. With these keywords you should be able to find the explanations you are looking for.


What is a real-world use-case/need for a left-recursive grammar? I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as:

  ...like LL and LR parsing, PEGs are often frustrating to use in practise. This is, principally, because they don't support left recursion.

http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt

But this leaves me confused.

I haven't read about an actual real-world use case of why you'd even need left-recursion in the first place, especially if there are techniques to convert left recursion to right recursion. In addition, left-recursion feels less intuitive than right-recursion.

What is a real-world use case or need for a left recursive grammar to help me better understand? By "real world" I'm looking for an example grammar that is more human readable than the typical theoretical examples such as:

$A \to B\alpha \mid C$

$B \to A\beta \mid D$

For example:

$filePath \to pathSegment*$

$pathSegment \to pathSegment \mid slash$

$slash \to /$

Part of the reason I ask is b/c left-recursion doesn't seem very intuitive; it seems more intuitive to use right-recursion. And also because I wonder if it's even a practical problem to try to solve.

Update

This makes sense, but seems to be the only major reason:

  $E \to E - n \mid n$

  converted becomes

  $E \to nT*$

  $T \to - n$

  "10 - 5 - 3" is then parsed:

  L-recursive : (((10) - 5) - 3)

  R-recusive : (10 (- 5 (- 3)))

http://etymon.blogspot.com/2006/09/why-i-prefer-lalr-parsers.html

Is that all?

There are probably better reasons than this, but one nice thing about left recursion is you get parse trees that naturally represent left associativity. You expect 5 + 3 + 2 to be evaluated as (5 + 3) + 2, but when parsed with the right recursive transformation you show, the parse tree would be the opposite.

This doesn't seem to matter until you start thinking about type coercion (Right word?). Consider 1u / 2u / 1.0f in C. (1 / 2) / 1.0 = 0 / 1.0 = 0.0 but 1 / (2 / 1.0) = 1 / 2.0 = 0.5.


Are all proof techniques which only look at black box behaviour of a TM relativizing? I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier.

However, it is hard to find a concrete definition of a "relativizing" proof. The best defintion I have found is as follows:
"A relativizing proof is any proof that is insensitive to the presence of oracles". So any proof technique that cannot tell if a TM used an oracle is relativizing.

Now my question is: Does this imply that all relativizing proofs only look at the black box behaviour of TMs? Moreover, are all proofs which only look at the black box behaviour of TMs also relativizing? Or are there cases where a proof is relativizing but is not looking at the black box behaviour of a TM, or vice-versa?

A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is relativizing if it is of the form
$$\forall A \,.\, \phi(T^A)$$
We say that the statement $\phi$ relativizes. There is no requirement on how such a statement is proved, i.e., we do not assume that we only observe the "black box" behavior of $T$ or anything like that. In fact, it is clear that this cannot be the case, as one can easily prove a relativizing theorem about Turing machines which speaks about how the machine works.

Often we start with a theorem about an ordinary Turing machine, and later we ask whether the theorem relativizes. This just means that we first proved $\phi(T^\emptyset)$, and now we wonder whether the trivial oracle $\emptyset$ could be replaced with an arbitrary one $A$ so that we get $\forall A \,.\, \phi(T^A)$.


Shorten Length Reduction I've stumbled upon this Question:

We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every
$ w\in A $, s.t  if $ |w| \geq n \ than \ |f(w)| < |w| $. Also, $A,B \notin \{\Sigma^*,\emptyset \} $. Prove there is such a reduction which is also polynomial-time reduction from any languages $ A,B \in P $.
This was my approach: Take $ w' $ to be the shortest word in $B$ and define $f(w) = w'$ for every $w \in A $.
I'm pretty sure the idea is correct because we simply choose $n = |w'| + 1$
and then obviously for every $w \ s.t \ |w| >= n \ we \ get \ |w| > n-1 = |w'| = |f(w)| $

So my question is, can I really choose a word $ w' $ to be the shortest word in $B$?

Also, am I correct with my approach?

Thanks!

In order to prove your result, you don't need to give an algorithm that gets a description of $A$ and $B$ and outputs a description of $f$, a polytime shortening reduction from $A$ to $B$. It's enough to show that for each $A$ and $B$, such an $f$ exists. If a language $B$ is different from $\emptyset$ and $\Sigma^*$ then there is some word $x \in B$ and some other word $y \notin B$, and these are enough to carry out your construction (you don't actually need them to be the shortest word).


Since programs are swapped from backing store to main memory why don't they get lost when the computer is suddenly turned off? So when I play a video, that means the video is moved from backing store to main memory. Then if I remove my laptop's battery all of sudden, that means the video should get lost as main memory is volatile. Why doesn't this happen though?


How can I make a pipeline with undefined/unlimited stages? I've been told that if you understand a pipeline then you should be able to make it with any depth, but I can only do 4 stages and maybe 5 if the memory is not too slow. How can I learn how to make infinite pipelines?

The thing about the MIPS/DLX-ish pipeline that you're probably talking about is that all of the pipeline control is central. There is a pipeline/hazard circuit which knows what's going on everywhere, and it does all the hard work.

This is probably why you asked the question: you can already see that there is no way this will scale!

There are three main techniques to construct a deep pipeline:

Nest pipelines and use hierarchical control.
Eliminate central control by making control as local as possible.
Reduce the need for control by designing the pipeline so that some situations that would require control never happen, or turn into an easier-to-handle control situation.

We'll take a look at these in turn, but bear in mind that all of these techniques can be mixed and matched as appropriate.

Hierarchical control

This is the simplest modification to what you've already seen. The idea here is that each logical unit in a CPU (e.g. instruction fetch unit, integer unit, load/store unit) may be a small pipeline by itself. Then you can decide what control needs to happen within that unit and what control needs to happen between units.

If you think about an instruction fetch unit, for example, there are various reasons why it might stall: it might be experiencing a cache miss, it might be recovering from a mispredicted branch, or whatever. In many situations, the control for the core as a whole may not care why the IFU is stalling, it only matters that it is stalling, because that means it isn't supplying instructions to the next stage. So the IFU may implement its own control, and communicate with higher-level control using coarser signals.

An extreme example of this is to use a coprocessor design. Coprocessors don't have to be on separate chips; the MIPS architecture uses a coprocessor for the MMU, for example. It isn't really a separate processor, but it is wired up to the core's control system as if it were.

This was an especially popular technique back in the day when CPUs came on more than one physical die such as POWER1.

Local control

Based on the previous idea, another way of coordinating different units is to just let them communicate with their surrounding units. There will probably still need to be some central control, but this could be reserved for large-scale events such as recovering from a fault or bad speculation.

So, for example, a unit which can't take any more work at the moment (whether it's because it's doing a multi-cycle operation, stalled on a cache miss, or stalled because the unit it needs to send a result to is itself busy) might simply provide a signal which says "I cannot take any more work right now". Any unit which wants to feed it work looks for that signal.

Another example of something that could reasonably be called "local control" is to use busses with arbitration. You can move data through the CPU using busses, and if two units want to write to the same bus at the same time, they decide between them that one will back off. You might use this in a Tomasulo pipeline.

An extreme example of local control is the counterflow pipeline. This is an example of a pipeline which can be arbitrarily deep using only local control, to the point where the pipeline could in principle be made completely asynchronous.

Redesign

If it is possible to eliminate the need for control by redesigning the pipeline, this is always worth considering. The classic example is register renaming, which effectively eliminates WAR hazards for registers. If a hazard is impossible, there doesn't need to be any control for it!

There are endless variations on this theme. For example, register renaming when there aren't "enough" physical registers available turns the WAR hazard into a stall in the rename stage. A stall early in the pipeline may be easier to control than a hazard late in a deep pipeline, because there are fewer cases to consider.

Another variation is to use speculation with a general recovery mechanism. If you think of a SPARC/MIPS-like pipeline, there is a delay slot after every branch, which is only possible because the pipeline is short. In a deeper pipeline, the most common solution is to speculate the branch and then use a general pipeline recovery mechanism if we got it wrong.

It's a similar story with instructions that could fault. Any memory access could cause a page fault. Any division could be a division by zero. We effectively "speculate" that this didn't happen, and fall back on the general recovery mechanism if it actually did. That way we don't need special control for a page fault.

A good place to start on this is Mike Johnson's book Superscalar Microprocessor Design (1991). It's old but it's full of good stuff that explains how these sorts of things actually work in practice.


How can I see which language type will result from the union or intersection of different language types? I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language.

Is there a way or rule to decide this for all language types?

This notion is clalled closure property. A family $\mathcal F$ of languages is closed under (binary) operation $\#$ if $K\# L$ is in $\mathcal F$ for all $K,L$ in $\mathcal F$.

There are no general rules: context-free $\mathsf{CF}$ is closed under union $\cup$, deterministic context-free $\mathsf{DCF}$ is not. However there are resources that list the known closure properties for important families, especially the Chomsy hierarchy.


What would be the classification of R according to paradigms? I would like to know in which classification is the R programming language. It has elements of the imperative paradigm and object oriented paradigm (some things like that even a number is an object and they can be freely mixed). I am not quite sure if it has functional programming characteristics. So it can be considered a scripting language?

What would be its classification in one of the paradigms?

R can do tasks in batches so it can be considered also a scripting language, is that so?

Scripting language

I once heard the following definition of what a scripting language as at some conference. Namely, if its main purpose is to orchestrate components that exist in their own rights outside of the language. Consider a theatre script - it orchestrates actors who all exist independently of the script. Bash scripts and batch files (the latter article even has a section entitled "Other Windows scripting languages") are prototypical representatives of a scripting language according to the given definition, because they are completely useless if you couldn't invoke external tools or commands like grep, ls or cd.

The most important part of this definition is the "to orchestrate components that exist in their own rights outside of the language" bit. At the end of the day, all computer languages (no coined term AFAIK) allow you to orchestrate components, thereby creating more new and complex components. However, in a programming language you mainly orchestrate library functions that only exist because the programming language exist.

Having said that, I would consider R a multi-paradigm programming language, where multi-paradigm includes at least the procedural paradigm and object-oriented paradigm.

Imperative paradigm

As a last remark: imperative programming includes both aforementioned paradigms and is different from declarative programming. An imperative language focuses on the "how to do things" and consists of more or less directly executable steps, whereas a declarative language focuses on the "what to achieve". As an example, consider sorting a list. An imperative program what consists of a procedure/method that moves elements around and thereby sorts the list, and each single instruction can be executed in a sort of obvious way. A declarative program would consist of a description of the property "sorted", but how to "execute" the property is not at all obvious. If you are interested in the differences, have a look at Quicksort implemented in Java and Prolog (among others).

What Wikipedia says

Addressing a comment by @vonbrand and in support of my reply to that comment, here are a couple of quotes from Wikipedia:

The first line in the article on Perl describes Perl as a

  Perl is a high-level, general-purpose, interpreted, dynamic
  programming language.

but in the second paragraph you find

  Perl was originally developed by Larry Wall in 1987 as a
  general-purpose Unix scripting language to make report processing
  easier.

It is similar for Python, where the first paragraph is

  Python is a general-purpose, interpreted high-level programming
  language whose design philosophy emphasizes code readability. Its
  syntax is said to be clear and expressive. Python has a large and
  comprehensive standard library.

In the second paragraph you'll find

  Like other dynamic languages, Python is often used as a scripting
  language, but is also used in a wide range of non-scripting contexts.

which, I think, supports my comment given below quite nicely.

Furthermore, the article about scripting languages defines

  A scripting language or script language is a programming language that
  supports the writing of scripts, programs written for a software
  environment that automate the execution of tasks which could
  alternatively be executed one-by-one by a human operator.

and then goes on as follows, where the first sentence is, in my opinion, the most important one

  Scripting is usually a property of the primary implementations of a
  language, rather than a language per se, although many languages are
  not very suited to this kind of implementation. For example, C++
  interpreters do exist, but C++ is generally not considered a scripting
  language for two reasons: these implementations are rarely used, and
  the time required to write program in C++ would be far greater than
  the time required to write an equivalent script in a language like
  Python.


Linear Temporal Logic (LTL) Syntax Infinitely Often I'm a little confused about some LTL syntax.

When the Global and Future operator (GFx) or []<>x is used, what does it mean. In the lecture slides it is given as infinitely often. But I don't understand it.

When used as FGx or <>[]x, I understand it as eventually in the future something will be true forever. E.g. eventually x will become 3 (x = 3) and x will stay as 3 forever.

Can someone explain what GFx means?

Consider just $Fx$. It means that at some point in time, say $t_k$, from the perspective of current moment $t_0$, $x$ will be true. After this moment, $x$ may never again be true. Specificaly, at the moment $t_{k+1}$ the formula $Fx$ may not hold.

If we add $G$, we are saying that at every moment from current moment something most hold. $GFx$, that is $G(Fx)$, says that $Fx$ must hold in every moment, meaning that, in the above situation, even at $t_{k+1}$ $Fx$ holds, that is — there must be some future moment where $x$ holds.

We have that for any moment $t_i$ $Fx$ must hold. That means that for any $t_i$ $x$ must hold at some future $t_j$. Wherever we are in time, $x$ will hold eventually. And that is the same as saying that $x$ holds infinitely many times.