Finite languages are Turing decidable - contradiction

This has been asked before in various guises. The answer is very simple.

If the continuum hypothesis holds, then here is pseudocode for a Turing machine accepting $L$:

Accept if the input equals 1.

If the continuum hypothesis doesn't hold, then here is pseudocode for a Turing machine accepting $L$:

Accept if the input equals 0.

In both cases, we have shown that there exists a Turing machine that decides $L$.

If you're confused, here is a slightly more formal version of your theorem:

  There exists a Turing machine $T$ such that if CH holds, $L(T) = \{1\}$, and if CH doesn't hold, $L(T) = \{0\}$.

Since CH either holds or doesn't hold, one of the following machines accepts $L$: the machine accepting only $1$, and the machine accepting only $0$. In particular, there exists a Turing machine whose language satisfies the requirements.

Perhaps you're confused about the incompleteness result. It states that there is no proof in ZFC of the continuum hypothesis or of its negation. Nevertheless, the continuum hypothesis is either true or false.

More formally, we can think of it in the following way. We live in a "model" of ZFC (model is actually a formal term!), in which every statement (more accurately, every first-order statement in the language of ZFC) has a definite truth value. In particular, in our model either the continuum hypothesis is true or it is false, and we know for sure that one of the possibilities holds, even if we cannot prove either possibility (and so we don't know which one holds).

If you don't like this sort of reasoning, I suggest looking into constructive mathematics and intuitionism, which is what logicians who didn't like this kind of reasoning came up with.


"ROM" stands for "read only memory".  This usually means that you can read any location in ROM, but you can't change what is already in ROM.  (Data in ROM is written when the ROM chip is constructed, or using special hardware operations in exceptional situations.)

"RAM" stands for "random access memory".  In practice, what this means is that you can read any location in RAM, and you can overwrite any location in RAM.  So this differs from ROM in that you are allowed to write into locations in RAM.  (Originally, "memory" could only be accessed in specific locations at specific times.  For example, if all of your storage is on a tape, then you can't read or write locations on the tape that are not under the read/write head; you have to move the tape first.  RAM was better because the access was "random", in the sense that you could easily access any location in RAM at any time.)

Both RAM and ROM can contain any information that can be translated into in binary form.  This can include (a) machine language or assembler instructions, (b) addresses of locations in RAM or ROM, (c) data.  It can include high-level programming language function representations as well.  Whether we call that data or instructions depends on the context.


How to choose proper activation functions for hidden and output layers of a perceptron neural network?

Input: it is not common to use activation functions in the input layer. Just rescale your data to the [-1;1] interval;
Hidden: the $tanh$ activation used to be the most popular. Now, this role has been taken by the $relu$ (rectified linear unit) activation, which produce sparse activations and better preserve the gradients;
Output: here is where you need to chose the activation function according to your problem type. For classification use the softmax activation (the multivariate version of the logistic sigmoid). For regression problems you may use linear outputs (identity activation function).


A more precise expression of the condition "$x$ is a contiguous substring of $y$" produces

$$L = \{x^r \# wxz | x, w, z\in \{a, b, c\}^*\}$$

That should make it clear that the language is context-free.


What happens when many interrupt requests happen at the same time?

In most cases, interrupt requests are processed, in priority order. Typically this does not involve a queue, but instead, lower priority interrupts continue to be asserted until such time as they can be processed.

A typical example would be the interrupt controller in a PC. This traditionally has a number of inputs, each assigned a priority. The peripheral signals its request. This remains until the processor clears the interrupting condition.


Proving a binary heap has $\lceil n/2 \rceil$ leaves

Here's a simpler logical proof.

Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.

Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.


The confusion comes mainly from different meanings of validity.

In the context of syntax, we are used to understand 'valid' as syntactically correct. As in '42["Hello world"] is a valid C expression'. I believe this is also how you understood Glenn&Gasarch. Their statement does make sense with semantic instead of syntactic validity.

Let me shortly recap semantics of WS1S. Generally, in second-order logic (weak or non-weak), the semantic of a formula is defined relative to an interpretation. The interpretation defines the meaning of all symbols. It consists of a structure and an assignment. The structure defines the universe and the meaning of the symbols from the base vocabulary. The assignment defines the meaning of the free variables. For a formula $\varphi$ and an interpretation $\mathcal I$, the semantics define whether $\mathcal I\models\varphi$ shall hold.

In WS1S, the structure is fixed: The universe is the natural numbers and the only other symbol is interpreted by the successor relation. Hence, for formulae $\varphi$ without free variables (sentences), the semantics can do without mentioning the interpretation. That could be written just $\models\varphi$, or $\models_{\text{WS1S}}\varphi$. And that is what Glenn&Gasarch mean with validity.

Let me stress that the finite-subset restriction of WS1S is not a syntactic one. The syntax of WS1S is the same as that of S1S (which has quantification over arbitrary subsets). Hence syntactic validity (well-formedness) is not jeopardized by concerns of what can or cannot be achieved with a finite subset. Indeed the only difference between WS1S and S1S is of semantic nature. By definition, $\mathcal I\models \exists X\varphi$ holds

(in case of S1S) if there is a subset $S$ of the universe such that $\mathcal I[\frac SX]\models\varphi$, or
(in case of WS1S) if there is a finite subset $S$ of the universe such that $\mathcal I[\frac SX]\models\varphi$.

Now to the other two formulae you asked about. Both are syntactically valid, if you allow binary second-order variables ($R$ in this case) as arguments (which is fine for defining subformulae as building blocks; in the end these variables will have to be substituted by other formulae). As they have free variables, we cannot say anything about semantic validity without having an assignment.

However, the names of the formulae suggest intended semantics. And we can compare the actual semantics to the intended ones.

The first formula holds (in the sense of $\models$) iff the set which is assigned to $Z$ is closed to the right under the relation assigned to $R$. That does seem to match the intention.
The second formula holds iff the element assigned to $z_2$ is reachable from the element assigned to $z_1$ by a path all of whose steps belong to the relation assigned to $R$, or if infinitely many elements are reachable in that way. That does not seem to match the intention.

But again, I would not use the notion of validity to discuss whether a formula fulfills its purpose.


Is Differential Evolution a genetic algorithm?

If you're asking for a homework assignment, then I can't really help you, because the answer really depends on how your professor interprets the taxonomy. But if you're asking for your own edification, I can give you my view.

First, the distinctions between the four classes you list (particularly between 1, 3, and 4) are largely historic. There are still some very real differences of course, but we don't view the lines between them as sharply as we once did. This means, for example, that GAs can be real-valued instead of binary and might rely on mutation more than crossover. You can have an evolution strategy for the traveling salesman problem. Really the description in the book isn't terribly well suited for use as a taxonomy for this reason. I teach from this book, and I like it a lot, so that's not really a criticism. I don't think the authors intended for you to try and use it as a well-defined taxonomy either.

If we go with this idea as a rough taxonomy though, then in principle, we have an umbrella term: "Evolutionary Computation" or "Evolutionary Algorithms" that covers all four of the cases you list. In practice though, while if someone says "evolution strategy" or "genetic programming", it's because they intentionally want to highlight that that's what they're doing, people sometimes say "genetic algorithms" when they really mean "evolutionary algorithms". So that term is especially hard to interpret.

So we might be able to call DE a GA with that understanding and be OK, but it really depends on who's asking the question as to whether that's what they had in mind or not.

Looking at the problem another way though, it gets even fuzzier. Right now, you're reading someone else's taxonomy and trying to fit the pieces together. What if you take a step back and try to formally define what a genetic algorithm or evolutionary algorithm is yourself? You might come up with something like "an algorithm that maintains a population of one or more candidate solutions, usually generated randomly, and continually selects the better individuals from the population, produces new individuals from the old ones via some type of variation operators, and favors the better of these new individuals for insertion into the population".

It's hard to get much narrower than that without excluding some things we think are "obviously" evolutionary algorithms, but this definition is really very broad. Certainly things like differential evolution and particle swarm optimization meet this definition, but so does, for example, simulated annealing. You can even take a simple next-descent hill-climber and call it a (1+1)-ES.

Personally then, my answer to your question is "sort of". If I write a paper that proposes a novel DE variant that looks super-awesome, I'd absolutely submit it to a journal like Evolutionary Computation. I know that my algorithm would be viewed as being appropriate for a venue that focused on genetic and evolutionary algorithms. But I probably wouldn't tell people that I used a "genetic algorithm" either, because that term doesn't feel precise enough to capture what it is that I want to express.

I'm not sure this is a particularly helpful answer, but I think it's probably a pretty common view among people in the field.


Attack on hash functions that do not satisfy the one-way property

For the second one, would the answer be that an attacker can simply obtain the original message given a hash?

Well, the message $M$ is already given to the adversary (it is sent to Bob over an insecure channel), so he needs not find it. To break the scheme he needs to send a new pair $M^*, h(M^*\|S_{ab})$ such that Bob will accept $M^* \ne M$ as the message sent by Alice.

For the second question: If it is easy to generate pre-images of $h$,
the adversary might be able to learn the secret key $S_{ab}$ from $h(M\| S_{ab})$ thus breaking the scheme.
(Note this might not be trivial. The inverting process might output $M_1, S_1$ such that $h(M\|S_{ab})=h(M_1\|S_1)$, but this is not useful for the adversary.. Furthermore, if the adversary try again to invert $h$, he might get the same pre-image.)

For the third question: Now we assume inverting $h$ takes a lot of time, so let's make the adversary's life harder by requiring him to invert it many times in order to break the scheme. For instance, use the hash $k$ times $h(h(h(....h(M\|S_{ab})..))$. Other solutions exist as well.


Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here.

As commented, this operation is central in cryptography, like RSA. Doing this operation efficiently for fixed $y$ and $z$ are critical.

There are several efficient libraries for doing multiprecision computation, perhaps the most known is GMP, which in turn is used in several languages that offer "big integers." Most computer algebra systems offer computation with large integers.


Simple algorithm for IEEE-754 division on 8-bit CPU?

When using properly-rounded higher-precision floating-point arithmetic to compute operations in lower-precision arithmetic, there is the potential issue of double rounding: The result is first rounded to the higher precision, then rounded again during conversion to the lower precision. This can lead to incorrect results, but that is not always the case.

Samuel Figueroa, "When is double rounding innocuous?", ACM SIGNUM Newsletter, Vol. 30, No. 3, July 1995, pp. 21-26

shows that in the case of floating-point division, the higher-precision format needs to have twice the precision of the lower-precision format to avoid issues due to double rounding. This conditions is satisfied were we to use IEEE-754 binary64 to perform the division, then round the result to IEEE-754 binary32. On the other hand, if the higher precision uses 40 mantissa bits, its precision is less than twice that of binary32, so some incorrect results due to double rounding would be expected.

However, from the description in the question it doesn't sound like this is the case. Rather, it seems that there is an internal computation that computes many more quotient bits than are strictly necessary, and this un-rounded result is rounded once to get the binary32 result. After normalization of dividend and divisor a correctly rounded binary32 division requires a total of 25 quotient bits (24 bits for the significand including the integer bit that is implicit in the stored format, plus a round bit), plus a sticky bit that is the OR of all other potential quotient bits.

Note that we don't have to compute the potentially infinite number of quotient bits in order to determine the value of the sticky bit. It suffices to know whether the remainder after computation of 25 quotient bits is zero or not. A zero remainder means the sticky bit is zero, a non-zero remainder means the sticky bit is one. The rounding in nearest-or-even mode requires three pieces of information: the least significant bit of the significand, the round bit, and the sticky bit. The significand needs to be increased when either (1) the round bit is set and the sticky bit is set or (2; tie case) the round bit is set, the sticky bit is clear, but the LSB of the significand is set (meaning it is odd).

Conceptually, for division in a semi-logarithmic floating-point format one needs to subtract the exponents and divide the significand. The conceptually simplest way to perform the latter operation is to perform binary long-hand division. In each step, one compares the current remainder with the divisor. If it is greater than or equal to the divisor, the next quotient bits is one and one can subtract the divisor from the remainder. Then double the remainder for the next step.

Using a small 8x8->16 bit multiply would conceptually be much more involved. One would either build a narrow division operation from this building block and perform a high-radix long-hand division (e.g. base 256), or build a much wider multiplication operation with is then used to compute the quotient with a Newton-Raphson iteration for the reciprocal, using fixed-point computation. In the latter case, the rounding is more involved as an accurate remainder does not fall naturally out of the computation. In addition, a table of starting approximations, say 8 bits, for the reciprocal is typically needed. The following research report discusses relevant trade-offs in the context of the 8-bit Kestrel processor:

Eric Rice and Richard Hughey, "Multiprecision division on small-word parallel processors: Expanded Version". University of California Santa Cruz, April 1998 (online)

I incorporated the above algorithmic sketch into the (tested) ISO-C code below. This code is written for clarity and does not incorporate various obvious optimizations, however I have tried to minimize the size of variables under the assumption that the asker's platform has support for 8-bit operations and limited support for 16-bit operations, similar to a Z80.

#include <stdint.h>

#define SIGN_MASK     (0x80000000)  /* sign bit of IEEE-754 binary32 format */
#define EXPO_MASK     (0x7f800000)  /* exponent bits of IEEE-754 binary32 */
#define MANT_MASK     (0x007fffff)  /* significand bits of IEEE-754 binary32 */
#define MANT_INTBIT   (0x00800000)  /* where integer bit would be if stored */
#define QNAN_BIT      (0x00400000)  /* distinguishes QNaN from SNaN */
#define INFTY         (0x7f800000)  /* infinity */
#define INDEFINITE    (0xffc00000)  /* special QNaN */
#define MAX_NORM_EXPO (254)         /* maximum biased exponent for normals */
#define MIN_NORM_EXPO (1)           /* minimum biased exponent for normals */
#define EXPO_BIAS     (127)         /* exponent bias IEEE-754 binary32 */
#define MANT_BITS     (24)          /* effective # of mantissa bits binary32 */
#define QUOT_BITS     (MANT_BITS+1) /* one extra bit for rounding */
#define EXPO_SHFT     (MANT_BITS-1) /* integer bit is implicit */
#define ROUND_BIT     (1)           /* mask for round bit in 25-bit quotient */
#define MANT_LSB      (2)           /* mask for significand lsb in quotient */

uint32_t fp32_div_kernel (uint32_t a, uint32_t b)
{
    uint32_t r, x, y, sign;
    uint16_t expo_x, expo_y, expo_res;
    uint8_t i, odd, rnd, sticky;

    /* extract biased exponents and sign bits */
    expo_x = (a & EXPO_MASK) >> EXPO_SHFT;
    expo_y = (b & EXPO_MASK) >> EXPO_SHFT;
    sign = (a ^ b) & SIGN_MASK;

    if ((expo_x >= MIN_NORM_EXPO) && (expo_x <= MAX_NORM_EXPO) &&
        (expo_y >= MIN_NORM_EXPO) && (expo_y <= MIN_NORM_EXPO)) { /* fast path */
divide:
        /* extract significands */
        x = (a & MANT_MASK) | MANT_INTBIT;
        y = (b & MANT_MASK) | MANT_INTBIT;
        /* compute exponent of result */
        expo_res = expo_x - expo_y + EXPO_BIAS;
        /* dividend may not be smaller than divisor: normalize */
        if (x < y) {
            x = x << 1;
            expo_res--;
        }
        /* generate quotient one bit at at time */
        r = 0;
        for (i = 0; i < QUOT_BITS; i++) {
            r = r << 1;
            if (x >= y) {
                x = x - y;
                r = r | 1;
            }
            x = x << 1;
        }
        /* OR remainder bits into sticky bit */
        sticky = (x != 0);
        if ((expo_res >= MIN_NORM_EXPO) &&
            (expo_res <= MAX_NORM_EXPO)) { /* normal, may overflow to infinity*/
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
            /* combine exponent and significand */
            r = ((uint32_t)expo_res << EXPO_SHFT) + (r - MANT_INTBIT);
        } else if ((int16_t)expo_res > MAX_NORM_EXPO) { // overflow: infinity
            r = INFTY;
        } else { /* underflow: result is zero, subnormal, or smallest normal */
            uint8_t shift = (uint8_t)(1 - expo_res);
            /* clamp shift count */
            if (shift > QUOT_BITS) shift = QUOT_BITS;
            /* OR shifted-off bits of significand into sticky bit */
            sticky = sticky | ((r & ~(~0 << shift)) != 0);
            /* denormalize significand */
            r = r >> shift;
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
        }
        /* combine sign bit with combo of exponent and significand */
        r = r | sign;
    } else { /* slow path */
        /* take absolute value of arguments */
        x = a & ~SIGN_MASK;
        y = b & ~SIGN_MASK;
        /* if dividend is a NaN, convert that NaN into a QNaN and return it */
        if (x > INFTY) return a | QNAN_BIT;
        /* if divisor is a NaN, convert that NaN into a QNaN and return it */
        if (y > INFTY) return b | QNAN_BIT;
        /* dividend and divisor are both zero or infinity: invalid operation */
        if (((x == 0) && (y == 0)) ||
            ((x == INFTY) && (y == INFTY))) return INDEFINITE;
        /* 0/y or x/INF -> 0 */
        if ((x == 0) || (y == INFTY)) return sign;
        /* x/0 or INF/y -> INF */
        if ((y == 0) || (x == INFTY)) return sign | INFTY;
        /* if dividend is a subnormal, normalize it */
        if (expo_x == 0) {
            expo_x++;
            do {
                a = a + a;
                expo_x--;
            } while (!(a & MANT_INTBIT));
        }
        /* if divisor is a subnormal, normalize it */
        if (expo_y == 0) {
            expo_y++;
            do {
                b = b + b;
                expo_y--;
            } while (!(b & MANT_INTBIT));
        }
        /* now that dividend and divisor are normalized, do the division */
        goto divide;
    }
    return r;
}


As a map is a geometric object, you can use from the concept of map matching in computational geometry. Also, some measures like Frechet Distance could help you to compare two maps on the plane.


Worst case analysis of $100n + 5$ for different $n$

Big-$O$ is the set of functions
$$O(f)=\{g\colon \exists C>0, \exists N \in \mathbb{N}, \forall n > N, g(n) \leqslant Cf(n)  \}$$
So we can write $100n+5 \leqslant  105\cdot n$, taking $C=105, N=1$, and we obtain
$$100n+5 \in O(n)$$


Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?

The key is indeed that the numbers are expressed in binary. As you observe, the numbers could have a value that is exponential in the size of the vertex cover instance. If the reduction "wrote them out" in unary when computing the Subset-Sum instance, this would take exponential time. However in binary, writing down the bits of the number (i.e. computing their representation in the Subset-Sum instance) only takes polynomial time.

Just to emphasise the distinction, it only takes 7 digits to write out 1,000,000 in base ten, so writing it down takes about 7 steps. If we did it in unary, it would take about a million steps. The same thing is happening in the reduction, if it were using unary, it would not be polynomial in the size of the graph, but in binary - because what we're measuring is the number of steps taken to write it down - it is polynomial.


How is RANSAC used to estimate a homography given the descriptors of both images computed with SIFT?

How do you estimate inliers?  You use RANSAC.  That's what RANSAC does for you: it computes a homography and gives you a prediction for which pairs are inliers and which are outliers.

In SIFT, we first generate keypoints and the feature vector for each keypoint.  Also, if $k$ is a keypoint in image $x$ and $k'$ is a keypoint in image $x'$, the feature vectors give a way to tell whether $k,k'$ are good matches.  For each $k$, we look for a good match: a $k'$ from $x'$ that is significantly closer to $k$ than any other keypoint in $x'$.  The set of good matches forms a set of possible inliers.

Then, we apply RANSAC.  We randomly pick four good matches, compute a homography from these four, and test how good this homography is by checking how many of the good matches are consistent with the homography (if $k,k'$ are a good match, we're hoping that in most cases the homography will map $k$ to something near $k'$).  Good matches that are consistent with the homography are called inliers (for this homography), and those that aren't are called outliers (for this homography).  We count the number of outliers for this homography.  Then, we repeat this 1000 times (picking a set of four good matches anew each time), in each iteration deriving a homography and counting the number of outliers associated with it.  We keep the homography with the smallest number of outliers.

This is a simplification of the procedure but it will give you the gist of how SIFT works.


I can not understand some petri net properties ( quasi-liveness and liveness )

To answer your first question:

An attempt to explain Petri nets in terms some 10-year olds will understand (see, for instance, Murata's well-known description):

A Petri net is a diagram that consists of three kinds of elements. We call them transitions, places, and arcs. In the example above, the transitions are green boxes and the places are white rounds. The arcs are arrows that run from places to transitions and from transitions to places. Transitions and places have names. A place may contain tokens. A token is usually drawn as a little dot.
A Petri net describes a set of circumstances in which changes can happen in certain ways. It describes exactly how the changes can happen. For each change, it describes the conditions under which it can occur, and the conditions that result from the change.
A transition describes a possible change. Its name should name that change. For example: a customer arrives, or: switch the light off, or: the light breaks, or: the sun goes down.
A place describes a possible condition. Its name should name that condition and should be of the form: something (for example: a person, thing, place, etc.) is something (a condition that that person, thing, place, etc. is in).  For example: the sun is shining, or: a customer is waiting, or: a spot is available, or: the light is broken.
A token describes a particular something for which the condition holds, and to which the change applies. For instance: the sun shining, or: a customer waiting, or: a spot being available, or: the light being broken.
The arcs describe which conditions must hold for a change to occur, by running from exactly those places to that transition. They describe which conditions will hold as a result of the change, by running from that transition to exactly those places. In the example given above: switch light on is only possible if the light is off; after switch light on, the light is on. Etcetera.
As we said above, the places of a Petri net can contain tokens. In some Petri nets, like the example above, they never contain more than one token; in other examples they do contain more than one token. When a change occurs (we say: a transition fires), usually the count of tokens changes: some places get fewer tokens and other places get more. We can describe the state we are in by saying how many tokens are in each place. We call such a listing a marking of the Petri net. So a marking lists for each place how many tokens are in that place.

In the example above, the marking has only one token, in light is on.
Only two transitions can fire: the upper light breaks and light is off.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light off fires, we end up in the marking that has one token in light is off and no tokens elsewhere. In that marking, two transitions can fire, namely the lower light breaks and switch light on.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light on fires, we end up in the marking that we started with.

With that out of the way, we can describe quasi-liveness and liveness:

A transition is said to be quasi-live if it can be fired at least once.  That is, from the present marking, either it can fire directly, or by firing transitions it is possible to arrive in a marking in which it can fire directly.  In other words: in the present situation, there is a way in which this change can occur, either now or in the future.

In the example above, every transition is quasi-live: as we have seen, two transitions can fire directly, while for the other two, a transition can fire such that they can then fire.

A marking is said to be quasi-live if all transitions are quasi-live for that marking.   In other words: in the present situation, all changes can still occur, either right away or later. This is the case in the example above.

A marking is said to be dead, a deadlock, if no transitions can fire. No changes can ever occur. This is the case for the marking we reach after firing one of the light breaks transitions.

A transition is said to be live if it is quasi-live in every possible marking.  That is to say: in any situation, that change can still occur, either right away or later. In the example above, no transition is live: we have found a dead marking, in which none of them can fire.

A Petri net is said to be live if all of its transitions are live. In any situation, all of the changes can still occur.  Clearly this is not the case in the example above.

We can change the example by adding new transitions: repair light. That would give us a live Petri net.

To answer your second question: a standard reference for how to determine liveness of Petri nets is Murata's article mentioned above. I recommend it; it is readable and the techniques it describes are readily applicable.

Deciding whether an arbitrary Petri net is live is possible, but very hard.
See, for instance, this informal discussion by prof. Javier Esparza. A fairly recent article (E. Best and H. Wimmel, Structure Theory of Petri Nets in: Transactions on Petri Nets and Other Models of Concurrency VII, 2013) says:

  For liveness we know that it is at least as hard as the reachability problem. The latter is EXPSPACE-hard, and no upper complexity bounds are known at the present time.

So researchers have focused on defining limited classes of Petri nets for which properties such as liveness are easier to decide; for instance, it is co-NP-complete for free-choice nets.


If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B)

In case you were wondering, the answer is yes.

Here is the reasoning.

Lemma: Let $f$ be a reduction from $A$ to $B$. Then $f$ is also a reduction from $\overline A$ to $\overline B$.
Proof: By the definition of a reduction, $f$ maps $A$ to $B$ and $f$ maps the complement of $A$ to the complement of $B$. So $f$ maps the complement of the complement of $A$, which is $A$ itself, to $B$, which is the complement of the complement of $B$. By the definition of a reduction again, $f$ is a reduction from the complement of $A$ to the complement of $B$. QED.

Suppose $A$ is polynomial-time reducible to $B$. Let $f$ be a polynomial reduction from $A$ to $B$. The lemmas shows that $f$ is also a reduction from the complement of $A$ to the complement of $B$. Since $f$ is polynomial-time, $\overline A$ is polynomial-time reduced to $\overline B$ by $f$.

With $A$ replaced by $\overline A$ and $B$ by $\overline B$, the above paragraph also shows $\overline A$ is polynomial-time reducible to $\overline B$ implies $A$ is polynomial-time reduced to $B$.

The above two paragraphs shows the equivalence of $A\leq_p B$ and $\overline{A}\leq_p \overline{B}$.


Insertion sort with pairs of numbers already in order

Insertion Sort is one of the algorithms which only swaps adjacent elements if they are out of order. Therefore, it's performance is intimately tied to the number of inversions in the input; see e.g. here for a detailed explanation.

Observe that in your class of inputs, the maximum number of inversions is not $n(n-1)$ as in the unrestricted case, but one less for each pair of elements. Since there are on average $\Theta(n^2)$ many inversions in random permutations, you'll have as many in your ordered-pairs permutations, assuming uniform randomness, because you lose at most linearly many in each.

For the details, find an analysis of Insertion Sort that rests on the number of inversions (e.g. in a good textbook) and change the numbers; the calculations should mostly remain the same.


How to formulate a computational problem rigorously?

a good resource on/for this, fairly well known by academics but not so widely known outside of specialists, is Mathematical Writing by  Donald E. Knuth, Tracy L. Larrabee, and Paul M. Roberts. there is a published book, lecture videos, and a set of notes. it is more written from the perspective of people attempting to master mathematical writing eg for creating papers, but all the advice is highly applicable to the case of laymen attempting to formulate problems precisely. mathematical writing while formidable to learn is the scientific approach to rigorously define/formulate—and as the book details, solve, eg via algorithms or proofs—computational/algorithmic problems.

Mathematical Writing book info
Mathematical writing lecture videos index
Mathematical writing CS1193 class notes

also, the classic Garey & Johnson text, Computers & Intractability does not exactly describe how to formulate problems precisely, but it does give many examples, and diverse theoretical/conceptual/technical "patterns", organized into sections of similar problems, which can be used as "building blocks" to describe computational/algorithmic problems.


Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

The answer is no (although from a rather syntactic reason, which might not be what you were looking for).

Let $f : \Sigma^* \rightarrow \Sigma^*$ be some arbitrary function, then it is implementable in the following "stupid" language which is not Turing complete:

Any string $s\in \Sigma^*$ is a valid program, and all strings represent the program which, given $x$ as input, outputs $f(x)$. Note that I don't really care how it computes $f$ (as I'm defining a new model of computation). If this bothers you, imagine any string is translated to the same fixed Java program which computes $f$ (assuming $f$ is computable).


Automata with minimal number of states using reverse

Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.

The proper construction just uses the two initial states. The determinization algorithm can handle that.


Calculating time it takes to download content

Most likely what you have is a line with a 400kbps bandwidth. That means a maximum throughput of 400kbps.

If you divide by 8 bits you get KiloBytes/s = 50Kbs.

1GB = 100000KB, thus 6GB = 600000KB,

600000KB / 50KB/s = 12000 seconds = 200 minutes = 3 hours 20 minutes

That means it would take at least 3 hours 20 minutes to download.   It could take significantly longer depending on network traffic.


Which one of these two sets is computably enumerable?

As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set of Turing machines that recognize no less 330 strings is computably enumerable.

Let us show that second set is computably enumerable using dovetailing. Let $M_1, M_2, \cdots$ list all Turing machines. Let $w_1, w_2,\cdots$ list all words over the alphabet. We can build a Turing machine using the universal Turing machine to run the following procedure.

for i from 1 to infinity:

for j from 1 to i:

let string_count be 0
for k from 1 to i:

run $M_j$ with input $w_k$ up to $i$ steps. If it is found $M_j$ accepts $w_k$, add 1 to the string_count. If string_count is no less than 330, append $M_j$ to the output tape.

It is clear that every Turing machine that accepts no less than 330 strings will be added to the list at some point of time. Although each of them may be listed many times, that does not matter. Also only that kind of machines will be included in the list. So we have shown that the second set is computably enumerable.

Rice's theorem tells us the second set, which is $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is no less than } 330 \}$$ is undecidable. Since it is computably enumerable, its complement (relative to the decidable problem whether a string encodes a Turing machine) $$\{\langle M\rangle : M\text{ is a TM and }L(M)\text{ has property that its size is less than } 330 \}$$ cannot be computably enumerable.
Well, the size of that number 330 does not affect our argument here. If we change it to 331, we see that the first set is not computably enumerable.


The address generated by the CPU is divided into 3 parts for the identification of its position in the cache. These three field as you mus be knowing are : BYte Offset , Index and TAG . The index bits determine the line number in the cache.
You need to find the number of bits present in the index field.


You are confusing NP and NP-hard. The fact that a problem is (say) in L doesn't preclude it being in NP, in fact, quite the contrary: any problem which is in L is a fortiori in NP, i.e. L$\subseteq$NP. On the other hand, it is not likely to be NP-hard (and assuming that P$\neq$NP, if it is in L then it cannot be NP-hard).

Another mistake you're making is that a problem which is approximable can't be NP-hard (or rather, its decision version can't be NP-hard). Considering MAX-3SAT, there is a trivial 7/8-approximation algorithm (pick a random assignment; this can be derandomized), yet the decision version 3SAT is NP-complete.

You're right that GAP-A$(a,b)$ being easy doesn't imply that GAP-A$(a/2,b/2)$ is easy. One example (replacing $1/2$ with an arbitrary $c$) is MAX-2SAT. GAP-2SAT$(a,1)$ is easy for any $a<1$, yet there exist some $b,c$ for which GAP-2SAT$(b,c)$ is NP-hard. (Unfortunately, $c=1/2$ doesn't work, since every 2SAT instance can be $1/2$-satisfied.)


TM that accepts all strings is recognizable or not?

Your intuition is correct: your $L$ is unrecognizable. Here's a hint on how to proceed.

If we define $A_\text{TM}= \{(\langle M\rangle,w)\mid M \text{ accepts }w\}$, then it's known that its complement, $\overline{A_\text{TM}}$, is unreconizable so if we can construct a mapping reduction $\overline{A_\text{TM}}\le_M L$, then we'll have shown that $L$ is unrecognizable.

Define the mapping $f(\langle M\rangle, w)\rightarrow \langle N\rangle$ where the TM $N$ depends on $M$ and $w$ and is defined by

N(x) =
   run M on w for |x| moves
   if M hasn't accepted yet,
      accept

The key idea here is that if $M$ accepts $w$, then it will do so in $k$ moves, for some number $k$, so if $M$ accepts $w$, then $N$ will accept all and only those strings of length less than $k$, and so the language of $N$ will be $L(N) = \Sigma^{k-1}$. On the other hand, if $M$ doesn't accept $w$, then $N$ will accept all strings.

With this hint, you should be able to show that $(\langle M\rangle, w)\in \overline{A_\text{TM}}\Longleftrightarrow\langle N\rangle\in L$, which is the reduction we need.


# of permutations satisfying special inequalties of each element0

A faster approach

It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations.  This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.

The idea is to enumerate all possible subsets of $t$ elements.  We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in).  There are $\binom{n}{t}$ such choices for $S$.

For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\{1,2,\dots,n\}\setminus S$ so that the last $n-t$ elements satisfy the second condition.  Then, we multiply these two counts.

Each of those counts can be computed efficiently.  For instance, to compute count (i), we compute

$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$

where $g(i) = |S \cap \{1,2,\dots,f(i)\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$).  Similarly, to compute count (ii), we compute

$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$

where $h(i) = |\overline{S} \cap \{f(i),\dots,n\}|$.

These two counts can be computed using $O(n)$ operations, leading to the claimed running time.

A further optimization

You can further optimize this, by splitting $S$ into two parts.  Decompose $S$ into

$$S = S_1 \cup S_2,$$

where $S_1 \cap S_2 = \emptyset$, by defining

$$\begin{align*}
S_1 &= S \cap \{f(t+1),f(t+1)+1,\dots,n-1,n\}\\
S_2 &= S \cap \{1,2,3,\dots,f(t+1)-1\}.
\end{align*}$$

Now notice that to count (ii), we don't actually need to know both $S_1$ and $S_2$: it's enough to know $|S_1|$ and $S_2$: the exact elements in $S_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j>t$.

Furthermore, since $|S|=t$ and $|S|=|S_1|+|S_2|$, it suffices to know $S_2$.  Once we know $S_2$, we can compute $|S_1|=t-|S_2|$ and then compute count (ii).

Similarly, once we know $S_2$, we can also compute count (i).

So, we're going to enumerate all possible values for $S_2$, i.e., all subsets of $\{1,2,3,\dots,f(t+1)-1\}$ of size $\le t$.  There are

$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$

possible choices for $S_2$.  Then we obtain an algorithm whose running time is $O(Q \cdot n)$.  The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.

In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$.  For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.

Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0).  It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.


Is it possible to have multiple languages accepted by a DFA?

Revisit the definition of the language a finite automaton accepts: it is the set of exactly the words the automaton has an accepting computation for. All these words, but no others. This set is always unique.

Here, the accepted language does indeed have subsets

$\{ 00x \mid x \in \{0\}^* \}$ and
$\{  0x11 \mid x \in \{0\}^* \}$.

You will have to check if that are really all accepted words. This may be simpler to do after minimizing the automaton.


Why do the sequent calculus NOT left and NOT right rules work?

You could start by considering simplified versions of the rules and build intuition by considering those cases. For instance,

$$\frac{\neg A, \ B \implies C}{B \implies C, \ A} (\neg L)$$

can be interpreted as stating that $(\neg A\wedge B)\Rightarrow C$ implies
$B\Rightarrow (C\vee A)$.

So if it is the case that $\neg A$ and $B$ are true implies $C$ is true, then if only $B$ is true, either $C$ is true (independently of $\neg A$) or $A$ is true, for otherwise $\neg A$ would be true, which combined with $B$ being true would make $C$ true.

A similar game can be played with the other case.


What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?

The complexity very much depends on whether you are looking at the worst case, or at the average case when you choose n at random.

To find whether $n^{1/b}$ is an integer, you could pre-calculate the set of possible integers $(a^b) \mod k$ for various k, and check whether $n \mod k$ is among those values - if not then $n^{1/b}$ is not an integer. If n is chosen at random, then this will eliminate many cases very quickly.

You can numerically calculate $n^{1/b}$ and check if it is an integer. If you calculate this value with (log n / b + 20) bits precision, and n was chosen at random, then your chance is 99.9999% that you can prove it is not an integer - this will fail if the result is an integer or close to one. There is a clever method doing the calculation using quadratically convergent Newton iteration involving only multiplications and additions / subtractions. Since only the last step requires the full precision, and the calculation involves raising numbers to powers b which is done in log b multiplications, this can be done in $O ({(\log n)^2 \over b^2} * \log b)$ steps using naive multiplication, and $O ((\log n / b) * \log (\log n / b) * \log b)$ using FFT. For random n, most of the time this is all that is needed.

It is possible that we find $n^{1/b}$ rounded to the nearest integer and cannot prove that $n^{1/b}$ is not an integer. In these cases we may have to calculate $a^b$. Again, only the final product needs full precision, so this is done in $O(log^2 n)$ using naive multiplication, or $O (log n log log n) using FFT.


Find shortest paths in a weighed unipathic graph

Choose a data representation

First, look at the size of the result. You want the collection of shortest paths from $s$ to every other node. Unless the average length of a path is bounded by a constant (which it isn't: any list is unipath, and if you take the root for $s$ the total length of the paths is $n(n-1)/2$ where $n$ is the length of the list), you'll need to be careful in your data representation: the structure containing the paths will need to use sharing between paths.

   Excluding cycles, there is a single path from $s$ to any other node $u$. If that path goes through an intermediate node $t$, then the first segment of the path is the desired path from $s$ to $t$.

I propose to store the result in an array, indexed by nodes numbered from $0$ to $|E|-1$, with $s=0$. Each element in the array stores the index of the previous node on the path to that node (use e.g. $-1$ as a special marker for nodes that are unreachable from $s$). The path from $s$ to $t$ will be $(s=R[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$.

Traverse the graph

Initialize $R$ to all $-1$.

Perform a depth-first or breadth-first traversal of the graph starting from $s$. Each time a node $u$ is reached, set $R[u]$ to its predecessor.

Since there are cycles, a node might be reached more than once. Having $R[u] \ne -1$ indicates that $u$ has already been visited.

Prove the correctness

   Because of the unipathic property, it doesn't matter how we reach each node, as long as we haven't completed a cycle. There is only one simple path.

Prove the complexity

The algorithm may reach each node more than once, so it's not clear that its complexity is $O(|V|)$. The work done is in fact $\Theta(|E_0|)$ where $V_0$ are the edges that are reachable from the source. More precisely, we reach a node more than once only in one circumstance: if the node is the first that we reach on a particular cycle, and in this case we reach it twice (once from a simple path, and once after completing the cycle).

Well then. Let's prove that in a unipathic graph, the number of elementary cycles grows at most linearly with the number of nodes. (An elementary cycle is one that does not contain a shorter cycle.) In the following discussion, I'll assume that the graph has no self-edge (no edge from a node to itself; such edges are irrelevant for the path construction anyway).

Unipathic graphs can have cycles, but in a very constrained way. It would be nice if we could somehow associate each cycle to a distinct node (or at least, at most a bounded number of cycles per node). Can cycles share a node? Unfortunately, yes.

   You can have $m$ cycles all sharing one node $a$ and no other nodes. The resulting graph is unipathic. With cycles of length 2, this is a star pattern with a central node $a$ and any number of nodes $b_i$ such that $\forall i, a \leftrightarrows b_i$.

So we'll need to work harder. Well, let's try to prove it inductively. Let $\#V(G)$ be the number of nodes in a graph $G$, $\#E(G)$ the number of edges and $\#C(G)$ the number of elementary cycles that aren't self edges. I assert that if $G$ is unipathic and not empty then $\#C(G) \le \#V(G)-1$.

For a graph with one or two nodes, this is obvious. Suppose the assertion holds for all graphs such that $\#V(G) < n$ and let $G$ be a unipathic graph with $n$ nodes. If $G$ has no cycle, $0 = \#C(G) < \#V(G)$, case closed. Otherwise, let $(a_1,\ldots,a_m)$ be an elementary cycle.

   Collapse the cycle: let $G'$ be the graph whose nodes are those of $G$ minus $\{a_1,\ldots,a_m\}$ plus a node $a$ and whose edges are all the edges of $G$ not involving the $a_i$'s, plus $a \rightarrow_{G'} b$ whenever $\exists i, a_i \rightarrow_G b$ and $b \rightarrow_{G'} a$ whenever $\exists i, b \rightarrow_G a_i$. Every path in $G'$ induces a path in $G$ (if the path involves $b \rightarrow a \rightarrow c$, then replace this by $b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ in $G$). Therefore $G'$ is unipathic. Furthermore, since cycles in $G$ do not share edges, $G'$ has all the cycles in $G$ except for the one we eliminated: $\#C(G') = \#C(G)-1$. By induction, $\#C(G') \le \#V(G')-1$. Since $\#V(G') = \#V(G) - m + 1$, we have $\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$.

This concludes the proof. The traversal follows at most $2|V|-2$ edges.


Proving the regularity of the following language

You can always take $n = 1$ for any string in your language...


Clear, complete, proof that a language is Turing Compete?

Every language that can implement two counters $C_1, C_2$ (i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete:

ADD $1$ to counter $C_i$, GOTO instruction $I_j$
SUBTRACT $1$ from  counter $C_i$ if $C_i > 0$ and GOTO instruction $I_j$; otherwise (if $C_i = 0$) GOTO instruction $I_k$

The result is proved in:

Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in the Theory of Turing Machines" (1961)

Don't forget that a computational model (in your case a programming language + a device that executes programs written in that language) can be considered Turing complete only if it supports access to an unbounded amount of memory (i.e. space) or can store (in some form) arbitrarily large integers. A programming language implementation on a real computer is equivalent to a Linear Bounded Automaton.

You can also find a lot of references on the Wikipedia pages on RAM model and RASP model.

Finally a nice book focused on the equivalence of different models of computation is:

"Models of Computation: An Introduction to Computability Theory", by Maribel Fernandez


Is Newton's algorithm really this much better than conjugate gradient descent?

The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing.  We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me.

There are some functions where Newton's method will be vastly better.  For instance, with a quadratic function, where a few iterations of Newton's method will suffice to get a very precise answer; yet gradient descent might take many iterations to get similar precision.  This can be partly explained theoretically by understanding that Newton's method often converges quadratically or faster (though for some bad cases it can converge more slowly), while gradient descent typically converges sub-linearly for convex functions or linearly for strongly convex functions (and for bad cases it can converge much more slowly), so in a theoretical sense Newton's method often requires fewer iterations than gradient descent.

Conversely, there are also some functions where (conjugate) gradient descent will be better, for instance because one iteration of gradient descent is much faster than one iteration of Newton's method.  One example would be training deep neural networks, where gradient descent works very well but Newton's method would be painfully slow due to the very high dimensionality and the time it takes to do a single iteration of Newton's method.

I would caution against drawing a conclusion about the performance of Newton's method on all functions, based on an empirical observation of its performance on one particular function (a sample size of $n=1$).


Where I can I find Pre Trained CNN Datasets for Facial Emotion Recognition?

You are probably interested in IAPS, and want to read Analysis of Physiological Signals for Emotion Recognition Based on Support Vector Machine.

But to be honest this classification is doomed in advance, not only pictures are stripped of below threshold of effector activisation but also you do not get baseline as point of reference.

If you are really interested then start from reading everything that Ekman or Sejnowski wrote and feed your NN with only relevant parts, otherwise the most of the data feeded is noise.


Understanding Cache Mapping and Access (Computer Architecture)

Any physical address consists of two parts : one part is the block offset and the other part is the block number.

Physical Address { Block number, Block Offset}

Block Number has further 2 parts : the index part and the tag.

The memory is assumed to be logically divided into many blocks. A block may contain more than one words in it ( which is indicated by the block size ). To reach to a specific word block offset is used.
Block offset is the number of bits required to address each word in the memory.

For instance, in a byte addressable system ( 1 word = 1 byte ) if the block size = 1 KB thenBlock Offset = 10 bits.  (Byteoffset=log2(bytes in one cache block)
The block offset remains same in each type of mapping as the number of words in each block do not change.

The implementation of block number is different in different mappings.

In case of Direct mapping the block number has two parts:

block no { tag, line number}

Since each block is mapped to one line in the cache,  the "line number" part of block number contains number of bits required to identify each line in the cache.
In this case since cache size = 512 KB and block size = (64 * 4)B = 256 B
The Number of lines in the cache = 512 KB / 256 B = 2 K = 2 ^ 11
Therefore, the number of bits in line number part will be 11.
The remaining bits are tag bits.

Fully Associative Mapping the tag number is same as the block number .
In Fully Associative Mapping any memory block can be mapped to any of the cache lines. So to check which line of the cache a particular block is mapped to every line number is "tagged".

And in Set Associative Mapping the block number is divided into two parts:

block no { tag, set number}

Here, the cache is divided into many sets, so the "set number" part consists of the number of bits required to identify each set uniquely.
Depending on the number of lines in each set ( a K-way set associative mapping will contain K lines in each set), the number of sets can be found out.

Hope this will help you.


Greedy algorithm: Minimizing the maximum of a list

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some maximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.


Some basic questions on halt and move in Turing machines

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the  same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.

  In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).

It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $\mathrm{HALT}$.

  Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?

Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.

  Can the tape-head move more than one unit to the left or right?

Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.

Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.


Bellman-Ford Termination when there is no change on vertex weights?

Part (1) is indeed true. The idea is that in $k$ steps the algorithm is only considering paths of length $k$. Indeed, you can prove by induction on $k$ that the path realizing the value of $d(v)$ after $k$ steps is at most $k$ edges long.

If the algorithm terminates after $k$ steps, then the results of the first $k-1$ steps are already optimal, hence (1).

Part (2) is indeed false, and I'm sure you can give a counterexample on your own.

The simultaneous version of the Bellman–Ford algorithm, referred to in part (1), has the following pseudo-code (where $d(x,y)$ is the weight of the edge connecting $x$ and $y$):

A[0,x,y] = ∞ for all x,y
t ← 0
do
  for all x,y:
    A[t+1,x,y] = min(A[t,x,y], { A[t,x,z] + d(z,y) : all z ≠ x,y })
  t ← t+1
while A[t,x,y] ≠ A[t-1,x,y] for some x,y
return A[t,x,y]

Take as an example the (undirected) graph $x - y - z - w$ (with unit weights). Here is a trace of the algorithm:

$$
\begin{array}{c|cccccc}
t & A[t,x,y] & A[t,x,z] & A[t,x,w] & A[t,y,z] & A[t,y,w] & A[t,z,w] \\\hline
0 & \infty & \infty & \infty & \infty & \infty & \infty \\
1 & 1 & \infty & \infty & 1 & \infty & 1 \\
2 & 1 & 2 & \infty & 1 & 2 & 1 \\
3 & 1 & 2 & 3 & 1 & 2 & 1 \\
4 & 1 & 2 & 3 & 1 & 2 & 1
\end{array}
$$


It is definitely more plausible, for the simple reason that $NP \subseteq TIME[O(n^{\log n})]$ is implied by $NP \subseteq P$. However, it is conjectured that $NP$ requires exponential time (this is known as the Exponential Time Hypothesis), and so both statements are conjectured to be false.


Algorithm to match timestamped events from two sources

Here is a pragmatic approach:

Look for matching pairs.  Consider a pair $(s,r)$ (where $s$ is from the first device and $r$ from the second device) to be a match if their timestamps are very close, i.e., $|s-r| \le \epsilon$ for some small fixed value of $\epsilon$ that you choose in advance.  $\epsilon$ is a tolerance.  To find matching pairs, for each $s$, you look for a value $r$ in the range $[s-\epsilon,s+\epsilon]$.

You can quickly find all matching pairs by first sorting $s$ and $r$ individually, then doing a linear scan across them.
Count how many values don't have a match.  Use the number of values that don't have a match to derive a confidence score.  The more mismatches, the less confident you are.

There are a number of elaborations possible:

For instance, if you've found $n$ matching pairs $(s_1,r_1),\dots,(s_n,r_n)$, you can use $|s_1-r_1|+\dots+|s_n-r_n|$ as an additional confidence measure: the higher this is, the worse a match it is.  You could compute a weighted sum of $|s_1-r_1|+\dots+|s_n-r_n|$ and the number of mismatched pairs.
If you frequently find that many points can be matched to multiple other possible points (one $s$ has multiple $r_i$'s it could match to), you could try framing this as a bipartite graph matching problem.  Basically, you have a vertex for each sample point, and an edge between $s$ and $r$ if $|s-r|\le \epsilon$; now find a maximum matching in this bipartite graph, and that will give you a way to find the maximum number of matched pairs.  Then you can use the number of unmatched values as a confidence score.  You can also use some kind of search over a range of $\epsilon$ values, if it's not clear how to choose $\epsilon$ a priori.

However, this is probably overkill and unnecessary, if events are well-aligned (if the typical distance between two events from a same device is much larger than the typical alignment error in the timestamp for an event at one device vs the timestamp at the other device).  If events are well-aligned, simply choosing a suitable threshold $\epsilon$ and applying the simple approach at the top of my answer will probably suffice.
If you expect systematic clock skew, where one device's clock is a bit ahead of the other device's clock (by a constant), you could correct for this in a number of ways:

One simple pragmatic way is to look for a set of matching pairs $(s_1,r_1),\dots,(s_n,r_n)$ in a first pass (this first pass doesn't have to be perfect, so you could use a larger value of $\epsilon$).  Then, use the median of $s_1-r_1, \dots, s_n-r_n$ as your estimate of the clock skew; say the median is $\Delta$.  Now replace each $s_i$ with $s'_i=s_i-\Delta$.  Finally, do a second pass where you match the (corrected) $s'_i$'s to the $r_j$'s, maybe with a smaller value of $\epsilon$.  In practice this might work very well.
Alternatively, you could use RANSAC to fit a line $s=r+c$ to the data, where the constant $c$ is unknown.  Normally RANSAC is described as a way to fit a line $y=ax+c$ (in this setting, $s=ar+c$), but in your application, we can fix $a=1$ (assuming both clocks run at the same rate and we care only about clock skew) and then apply RANSAC methods to find the best fit line, i.e., to find the constant $c$ that provides the best fit.


What's flawed about the "save-the-input" method of reversible computing?

There are two important features of reversible computing that are missing from your discussion of reversible computing:

A reversible function has to be a bijection, and
Reversibility is defined on the level of local gates, not just the global level.

In particular, for your extension of $\{0,1\}^n \rightarrow \{0,1\}^n$ into $\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ by copying, you don't ensure bijection because you don't explain what happens when the last $n$ bits of input for your function aren't $0^n$.

As for the second point, that is really the essential part of reversible-computing from the physics perspective. The physical process can't simply "undo" heating at a global level, thus every gate has to be reversible for the circuit to be reversible in the relevant-to-physics sense.

Finally, the theory of reversible computing is not unreasonably complicated, but it is definitely not trivial. In particular, there are some circuits that can be implemented with strictly fewer registers/wires non-reversibly than they can be reversibly. However, the blow up in going from non-reversible to reversible is not too bad.

In general, I seldom hear reversible computing come up in classical CS courses, because it is seldom relevant to classical computation. However, it is an important topic in quantum computing because all quantum circuits are reversible and because one has to handle what is on your 'junk' wires carefully to avoid unnecessary entanglement.


DAG for contiguous subsequence of maximum sum

You grasped the idea right. For the problem of finding "contiguous subsequence of maximum sum", the DAG is indeed $a_1 \to a_2 \to ... \to a_n$, since the sequence is contiguous.
To get a better feel for DAG, you should consider the problem of finding an "increasing subsequence of maximum sum" problem. By increasing subsequence, I mean that $a_{i} \leq a_{j}$ for any two consecutive elements $a_{i}$ and $a_{j}$ in the sequence.
Note that, an increasing subsequence might not be contiguous. And, to calculate $S(i)$, you will need $S(j)$ such that $a_{j}\leq a_{i}$. So there will be an edge between the nodes $j$ and $i$ if and only if $a_{j}\leq a_{i}$ and $j < i$. You will get your DAG. Here, DAG might not contain the edges between $a_{i}$ and $a_{i+1}$, as it was in the previous problem.
You can also consider the problem of finding the "subsequence of maximum sum". Here the subsequence is neither contiguous nor increasing. Here DAG will contain an edge between every pair of nodes $a_{i}$ and $a_{j}$ for $i<j$. And, the maximum value is trivially the sum of all positive values in the array.


Computing the Kolmogorov complexity of a string

If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'>n$ pseudorandom string, then the answer is no. The reason actually has nothing to do with the properties of PRGs, but simply relies on the fact that the output of the generator is computable, and that its range is infinite.

Kolmogorov's complexity isn't computable on any infinite recursively enumerable set of strings. To show this you can follow the standard proof of uncomputability of Kolmogorov's complexity. Since the set is infinite, it contains strings of arbitrarily high Kolmogorov's complexity, so you can write a program which enumerates them until it finds some string of high enough complexity, and then stop and output it. This was also answered in this math.se question.


"not provable", what does this to do with unification?

They mean you can't use the rules in Figure 2 defining $\approx$ (and $\#$) to derive $\emptyset\vdash a.\!X\approx b.\!X$.  If you attempt to do it you'll use $\approx$-abstraction-2 followed by $\approx$-suspension at which point you'll not be able to satisfy the premise as $\nabla$ is empty but the disagreement set is $\{a,b\}$.  There are no other applicable rules, so there is no derivation.

Conceptually, though conceptual understanding is not needed to answer this question, what's happening is with an empty freshness environment we're free to replace $X$ with $a$ (or $b$) but $a.\!a \neq_\alpha b.\!a$. This is what it means in the sentences following that quote by $\alpha$-equivalence not being preserved by substitution.  The freshness constraints in $\nabla$ are what disallow such substitutions. So in an empty freshness environment $a.\!X$ and $b.\!X$ can't be unified as their instances need not be $\alpha$-equivalent.

I recommend getting more familiar with inductively defined judgements and derivations, as e.g. discussed in Chapter 2 of Robert Harper's Practical Foundations for Programming Languages. You should do the exercises there, and write out the complete derivations for the examples in the Nominal Unification paper. Ultimately, checking derivability like this should be as straightforward and mechanical as checking $(x+3)(x-1) = x^2+2x-3$.


What are the modern alternatives to Backus–Naur form and what are their advantages?

Answer 1: The question is meaningless as written.
You are mixing different kinds of notations here that are intended for different purposes.

BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar.
"Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or to a concrete notation for writing this type of grammar. Van Wijngaarden grammars are strictly more expressive than context-free grammars. In fact, parsing them is undecidable in general, making them more like an esoteric programming language in some respects.
ANTLR is a particular software tool for generating parsers. It has a language for writing grammars that it accepts as input. Like most other parser generators, ANTLR includes specialized features in its grammar language for manipulating the generated parser code. For example, it is possible in an ANTLR input file to directly insert Java code that is to be executed by the generated parser when a certain token is encountered. This sort of feature only makes sense in the context of a parser generator.

Answer 2: It mostly doesn't matter.
If, as you say, "you want to invent a new programing language," there are two situations where writing down a grammar is relevant:

Writing a parser as part of the compiler implementation. Your choice of how to express the grammar here is dictated by how your parser is implemented. Whether you use an ANTLR/Yacc/Bison-style parser generator, a parser combinator library, etc. will determine what your grammar looks like in the source code.

Writing a language specification. Most programming language specifications are written to be read by humans, not computers. Therefore, anything that is sufficiently clear to a human reader is an acceptable choice of notation. It is common for a language specification to define its own grammar notation, rendering the particular choice of notation largely irrelevant. For example, the "Lexical Structure" chapter of the Haskell 2010 Language Report starts with a "Notational Conventions" section that defines how the grammar will be written.


How many virtual machines run inside MS Windows?

The NT kernel does have sub-systems or did for DOS, Win32, POSIX, and OS/2. You might consider them to be a VM layer in that they are instantiated per process and provides a compatible binary API to the process so that it may run. Each of these sub-systems only maps the binary API for the process to the API of the kernel and as such they don't do much other than that. State pertaining to a sub-system is kept in the process's context.

See chapter 5 in Inside Windows NT (Helen Custer, 1993) for more.


Error propagation when compiling a compiler

There is no reason why compiling a compiler's source code with a broken compiler would result in a working compiler. The bug in the existing binary could well lead to a binary that is completely broken, or subtly broken, or has the very same bug.

For example, there once was a version of CAML (an ancestor language of Ocaml) where one version of the compiler omitted the code for a case in a match-case construct under certain circumstances. So the developers fixed the bug — a case was missing in a match-case construct in the source code. But the compiler was bootstrapped (the CAML compiler was written in CAML), and compiling the corrected source generated a binary that was still buggy, because the compiler bug caused the new case to not have generated code. The developers had to rewrite the code in a different way, then recompile to get a correct compiler, and after that they could change the source code back to using the desired match-case construct.

There is a rather famous example where such a self-reproducing bug was introduced deliberately: the “Thompson hack”. Ken Thompson was one of the main authors of the Unix operating system and the first C compiler. He introduced a backdoor in the operating system by modifying the source code of the login program to allow him to log in on any Unix system. Then he reverted this change and instead modified the C compiler to insert this backdoor whenever it was compiling login.c. Then he modified the C compiler again to add code to insert the backdoor in login whenever the compiler was compiling itself. He recompiled the compiler and removed all traces of his backdoor. So he had a self-perpetuating bug which happened to be a backdoor. I strongly recommend “Reflections on Trusting Trust”, his Turing award lecture, where he revealed and explained this backdoor.

In practice, there are a few ways to reduce the risk of self-perpetuating compiler bugs. Compiler writers usually try to use a well-known, stable subset of the language, and avoid newer features where the compiler is more likely to have bugs. Some compilers have a bootstrap compiler which depends on a subset $A$ of the language and is capable of compiling a subset $B \supset A$; the full compiler is written in $B$ and is capable of compiling the whole language. If multiple compilers exist for the language the compiler is written in, this makes it unlikely that they'll all be too buggy to compile the compiler.

There are research efforts to reduce the trusted base of compilers, i.e. the amount of software that must be assumed to be correct in order to guarantee that the compiler binaries will work correctly. In particular, certified compilers come with a proof that the compiler binary has the semantics specified by its source code. A correctness statement goes like this: “assuming that the proof checker for the compiler is correct, and assuming that the runtime environment in which the compiler runs conforms to its model, then the compiler always produces binaries that have the semantics specified by their source code”. The trusted base consists in the runtime environment and the proof checker, which is typically orders of magnitude smaller than a compiler.


Is it possible to find the nth term  of a Fibonacci sequence using a definitive for loop?

If it is only the third chapter, I doubt the authors have covered dynamic programming, but I will illustrate what is going on when a for loop is used to compute the $n^\text{th}$ Fibonacci number, $F_n$.

Recall the definition,
$$F_n = \begin{cases} 0 & n = 0\\
1 & n = 1\\
F_{n-1} + F_{n - 2} & \text{otherwise}
\end{cases}$$

We could naively compute this using a recursive function defined in Python as,

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

However by recomputing the same sub-problem many times, this function requires exponential time to compute (illustrated below)!

There is a fix, though. We can use dynamic programming to do "smarter" recursion and keep our previous results around. This way, we don't need to recompute $F_i$. Our function call "tree" will collapse to a list and and will compute $F_n$ from the "bottom-up".

def fib2(n):
    if n < 2:
        return n
    else:
        if not results[n]:
            results[n] = fib2(n - 1) + fib2(n - 2)
        return results[n]

Now we have our $O(n)$ time algorithm to compute $F_n$, but if you notice, we require $O(n)$ additional space (one spot in the array for each $F_i$). This can be cut down to $O(1)$ additional space because each $F_i$ requires only two other fibonacci numbers, namely $F_{i-1}$ and $F_{i-2}$.

def fib3(n):
    if n < 2:
        return n
    f_0 = 0
    f_1 = 1
    f_n = 0
    for _ in range(n - 1):
        f_n = f_0 + f_1
        f_0 = f_1
        f_1 = f_n

    return f_n


How to sort objects based only on "less than" relationships?

What you are looking for is a comparison sort. Please take a look at that article.

Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final sorted list. Object i should occur before object j if Z(i, j) = 1. Object i can occur before or after object j if Z(i, j) = Z(j, i) = 0.

As vonbrand mentioned, we should assume that the matrix Z specifies a well-defined "less than" relation or, in terms of math, a total strict-order on the values of the objects. Otherwise, the given objects may not be sorted.

Z[i, j] = 0 if Z[j, i] = 1. Otherwise, we cannot sort object i and object j.
Z[j, i] = 0 if Z[i, k] = 1 and Z[k, j] = 1 for some k. Otherwise, we cannot sort object i, j and k (think of paper-scissors-rock).

Assume that Z specifies a well-defined "less than" relation. Then it also defines a "$\le$" comparison operation naturally. Namely, if Z(j, i) = 0, then object i $\le$ object j. So we can apply any comparison sort to sort the given $n$ object.

Almost all sorting algorithms are comparison sorts. For example, quicksort, mergesort, insertion sort, selection sort and bubble sort. A notable exception is counting sort.


Maximum matching using linear programming

This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and combinatorial optimization. Edmonds gave a description of the general matching polytope, which has exponentially many defining linear inequalities. While the simplex method cannot be used to optimize the corresponding linear program, other approaches, such as the ellipsoid algorithm and some interior point methods, can use a separation oracle for efficient optimization (at least theoretically).

There is a third algorithm, due to Micali and V. Vazirani, which is however also quite complicated; see the recent exposition by Vazirani.


Number of non-XOR gates needed to implement an n-bit boolean function

By counting circuits, $2^{n/2 + 1}$ appears to be close to asymptotically optimal.

Let $C_{n,k}$ be the number of distinct circuits with $n$ bits and $k$ AND gates.

We lower bound $C_{n,k}$ by noting that we need to choose $k$ such that there is at least as many possible circuits as possible functions, i.e. $2^{2^n} \leq C_{n,k}$.

We upper bound $C_{n,k}$ by noting that every AND gate takes as input a bit which may have had each initial input and each output of a previous AND gate and possibly the constant 1 XOR'd into it. For the first AND gate there are $n + 1$ bits that may or may not be xored into each input of rht AND gate. For the second AND gate there are $n + 2$ bits, for the third $n+3$, and so forth. Then there's $n+k+1$ choices for what to xor into our output bit. Thus $C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$.

Now we know $2^{2^n} \leq C_{n,k} \leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}$. By omitting the $C_{n,k}$ in the center we get an inequality in terms of $k$ and $n$ that we can use to bound $k$ in terms of $n$ as follows:

$$\begin{align}
2^{2^n}
&\leq 4^{n+1} 4^{n+2} \ldots 4^{n+k} \cdot 2^{n+k+1}
\\
&= 2^{n+k+1} \prod_{i=1}^k 4^{n+i}
\\
&= 2^{n+k+1} 4^{\sum_{i=1}^k n+i}
\\
&= 2^{n+k+1} 4^{kn + k(k+1)/2}
\\
&= 2^{2kn + k^2 + 2k + n + 1}
\end{align}$$

Now we start manipulating both sides:

$$\begin{align}
2^{2^n} &\leq 2^{2kn + k^2 + 2k + n + 1}
\\
2^n &\leq 2kn + k^2 + 2k + n + 1
\\
0 &\leq k^2 + k(2n + 2) + (n + 1 - 2^n)
\end{align}$$

Finally, find the quadratic roots where the inequality switches, and focus down to the asymptotically dominant term of the positive root:

$$\begin{align}
k &= \frac{-2n -2 \pm \sqrt{(2n+2)^2 + 4 \cdot (2^n - n - 1)}}{2}
\\
  &= -n - 1 \pm \sqrt{n^2 + 2n + 1 + 2^n - n - 1}
\\
  &= -n - 1 \pm \sqrt{n^2 + n + 2^n}
\\
  &\in \Omega \left(-n -\frac{1}{2} + \sqrt{n^2 + n + 2^n} \right)
\\
  &= \Omega \left(\sqrt{2^n} \right)
\\
\end{align}$$

So it appears that $k$ must be asymptotically at least $\Omega(\sqrt{2^n})$ in order for there to be enough circuits to cover all of the possible functions.


Can you apply neural networks to design algorithms?

There are a few issues to consider.

If P!=NP, this approach is doomed from the start because you can't try every one of the infinite number of possible algorithms in finite time. That's I think the main deal-breaker here. Unless P=NP, which most people doubt, then the best you could ever do is say "my AI failed to find a polynomial-time algorithm in X amount of time", which doesn't mean no such algorithm exists. If you assume that P=NP, then in principle, an evolutionary algorithm, neural network, or other search technique could potentially find an example of a polynomial algorithm for an NP-complete problem, and that's all you need to prove that P=NP.

In practice, there are some challenges to deal with. I'm sure certain approaches would be more natural to try than others. Neural nets require numeric vectors of inputs and outputs, so you need to develop some way to encode an algorithm as a vector and a way to determine a binary "is_polynomial" so that you have an error gradient to follow. Or I suppose a continuous function measuring "degree of polynomial-ness" if such a thing makes sense. You're certainly going to need some way to measure success regardless of approach, but something like Genetic Programming could theoretically eliminate the need for a cumbersome translation of algorithm to real vector, since GP operates directly on an executable representation. Give it a Turing-complete set of operators to work with and it could presumably eventually find a polynomial solution if such a thing exists.

It's also far from clear that you have a friendly search space to work with here. I think most of the time, your hypothetical GP or whatever is going to wander around a very flat plateau of individuals that don't even successfully solve the problem, regardless of run-time. You could attempt to introduce a gradient to follow by favoring shorter programs or programs that terminate faster or whatever thing you came up with, but there's no good reason to think that gradient points in the direction of the prize-winning algorithm you're looking for. Theoretically, there are fairly easy conditions to meet that say given infinite search time, a given algorithm will eventually find any arbitrary solution that exists, but a workable algorithm in practice tends to require there be some structure in the search space that can be exploited. If you make a local move somewhere in the space that looks like it's better, you want that move to take you generally closer to the solution you're looking for. If the world looks basically random in terms of what moves me closer or further away, search algorithms struggle to do better than just randomly trying things.

Short answer, it's conceivably possible to build an algorithm that searches for poly-time solutions to an NP-hard problem, but the world is likely constructed so that that won't actually solve the problem you hope to solve.


How is a program stored before compiling?

Here is a brief overview of a typical compilation and execution flow on a Von Neumann machine:

Type in the source code in a plain text editor.
This source code consists of characters. Characters are encoded as bits. An example of encoding is ASCII. These bits are stored on the disk, when you save the source code.
Invoke the compiler to compile the source code. The compiler parses the source code file(s), produces object code and links the object files to produce a machine language file called executable. The executable is stored on the disk.
Run the executable. This is called execution.

At all steps in the process, the operating system controls and co-ordinates processes and does the memory management.

Data is stored in the RAM temporarily when the process running on the machine requires it.

Data is stored on the disk when it needs to be stored permanently.

There is also a process called swapping which is done by the OS when there is no RAM memory left. A section of the disk memory is used for swapping.

There can be multiple processes running on the machine. These processes can run parallely or concurrently. The operating system allocates resources for processes and schedules the processes to run using scheduling algorithms.

This was just a brief overview. To learn more, I highly recommend the free online course on MIT's OCW called Computational Structures.


A concrete example about string w and string x used in the proof of Rice's Theorem

A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Your characterisation of reduction is a bit misleading. You don't start with an "easy" problem and reduce it to a "harder" problem (how can you know it's an easy problem if it's unknown? Often you're attempting the reduction to find out whether your problem is "easy").

A reduction is a computable transformation from one problem to another. It proves that the source problem is no harder (in some sense) than the target problem.

Sometimes we do this because we already know the source problem is impossible to solve; this proves that the target problem is impossible too. Since the source problem is "no harder" than the target problem, and we already know the source is undecidable, the target problem must be undecidable (or the source would in fact be harder). More intuitively, if we can reduce the source to the target and the source is undecidable, then the target must be undecidable or we could use the reduction and the solution to the target in order to solve the source (which we already know can't be done).

Other times we find a reduction because we know the target problem is decidable. This shows that the source problem is decidable too.

So you can use a reduction argument either to a problem that's already known to be decidable, or from a problem that's already known to be undecidable, depending on what you're trying to prove.

So, Rice's Theorum. I don't quite understand the questions you're asking, since I haven't seen the particular statement of the proof that's giving you trouble. Instead, here's my quickie explanation of how to prove Rice's Theorum, which I'm pretty sure is similar.

Suppose we have an arbitrary language $L$, consisting of (encodings of) exactly those TMs with some non-trivial semantic property $P$.[1] To prove that there is no algorithm for deciding language $L$, I will reduce the Halting Problem to the decision problem for $L$.

So the Halting Problem (or the particular variant of it I will use here) is: given $\langle M, x\rangle$, an encoding of a Turing machine $M$ and an input $x$, does $M$ halt on $x$?

My reduction must transform the input to the Halting Problem $\langle M, x \rangle$ into the input for the hypothetical decider for $L$, which I will call $ML$. $L$ is a language of Turing machines, so $ML$'s input looks like $\langle M \rangle$.

So my reduction will take $\langle M, x \rangle$ and compute $\langle M' \rangle$. $M'$ is a machine that takes an input $w$ and functions as follows:

Simulate $M$ on $x$, ignoring the result
Simulate $MP$ on $w$; accept if it accepts and reject if it rejects

Here $MP$ is a machine that whose encoding is in $L$ i.e. it has the property $P$. Since we're considering a non-trivial property $P$, such an $MP$ is guaranteed to exist.

Note that $x$ is part of the machine $M'$ the reduction has produced, while $w$ is the input to that machine whenever it is run. $x$ and $w$ are completely unrelated. We are assuming we've been given a particular $x$ as part of the input to the Halting Problem, but since we haven't proposed running $M'$, there is no specific $w$ at the moment.

Now, if $M$ halts on input $x$, then $M'$ always gets to stage 2 and thus accepts/rejects exactly the same strings as $MP$. Since the property $P$ is semantic, it doesn't depend on the particular TM, only on the language it accepts, so in this case $M'$ also has property $P$. If $M$ doesn't halt on input $x$, then $M'$ never gets to an accept state regardless of input, so its language is the empty language.

So now we don't want to run $M'$ on anything, since it might not even halt, but we could run our hypothetical $ML$ on it to check whether it's in $L$. This will almost tell us whether $M$ halts on $x$; the only thing we're missing is that the empty language might happen to have property $P$, in which case $ML$ will always accept $M'$ whether or not $M$ halts on $x$. But we can easily amend $M'$: if $P$ is true of the empty language (which our reduction could check using $ML$ if $ML$ could actually exist), then we use $MN$ instead of $MP$ - some machine that doesn't have property $P$ (which is also guaranteed to exist by the non-triviality of $P$) - and then our $M'$ has property $P$ if-and-only-if $M$ doesn't halt on $x$.

So now we've shown that a hypothetical decider for $L$, the language of machines with property $P$, could be used to decide the Halting Problem. Since we already know the Halting Problem can't be decided, $ML$ can't exist. Since the only thing I assumed about $P$ was that it was a semantic and non-trivial property, the proof holds for any semantic and non-trivial property.

I cheated a little in my reduction, since I had to use $ML$ to work out whether the empty language has property $P$, which means the reduction is only computable if $ML$ exists. This breaks my earlier definition of a reduction as "a computable transformation from one problem to another", but the proof by contradiction is still perfectly valid; proving a language undecidable by reduction from an undecidable language is really just a special case of a proof by contradiction anyway.

[1] A property of a TM is semantic if all TMs that accept the same language share the property, i.e. the property doesn't depend on the particular implementation of the TM but only on the language it accepts. A property is non-trivial if there is at least one TM that has the property and at least one TM that doesn't have the property.


Complexity of finding 7th smallest element in a min-heap?

If you had a "black-box" min heap where the only operations available to you are adding elements and extracting (reading and simultaneously removing) the smallest item, then the time complexity is O (n) obviously.

It is imaginable that you have a specific implementation where even finding the second smallest element cannot be done in constant time. You might have in your data structure O (log n) items that might be the second smallest, and the O (log n) operation to remove the smallest item will also determine the second largest. I find it hard to describe an algorithm that works that way, but I'm sure it's possible.

The way a min-heap is usually implemented (or the way it is implemented if I had to implement it, or the way it is implemented in a random text book), finding the 7th smallest element can be done in constant time.


Is page size always equal to frame size?

A page is a region of virtual address space, and a page frame is a region of physical memory. A page which maps a region of physical memory must have the same size as that piece of physical memory, otherwise there's no point.

They also typically must be aligned correctly. If you try to map, say, a 2Mb page frame into virtual memory, both the virtual address and physical address must both be 2Mb aligned.

Many modern CPUs support more than one page size, and some can support different page sizes in the same address space. Current Intel x86-64, for example, supports 4kb, 2Mb and 1Gb page sizes. These numbers are not arbitrary; they represent the address space covered by different "levels" in the multilevel page table. Similarly, modern ARM supports 4kb, 64kb, and 1Mb pages, though ARM does not refer to the 1Mb pages as "pages" (they are "sections"). ARMv4 and ARMv5 supported splitting pages further into so-called "subpages"; these are no longer available in ARMv7.

Interestingly, there are a few other things that are often the same size as the page size. Obviously a TLB entry is the same size as a page or frame, since it's conceptually a cache for page table entries. However, L1 cache size is often determined by the page size, too.

Suppose the L1 cache is set-associative (a direct-mapped cache is really just a 1-way set associative cache, so you can think of this as a limiting case), then it's often convenient to make one "set" the size of a physical page. So suppose that the page size is 4kb, and the L1 cache is a 4-way set-associative cache, then the "best" size for the L1 cache is 16kb (which is four times 4kb). See if you can work out for yourself this might be the case.


What's the difference between transdichotomous model and RAM?

The transdichotomous model is first proposed by Michael Fredman and Dan Willard [1]. They wrote the motivation as

  ... On the other hand, with the inclusion of division and Boolean operations, they obtain a linear time algorithm. This linear time algorithm, however, suffers from an abuse of the unit cost assumption. In particular, the algorithm generates operands during the course of its computation whose individual lengths are $N^2$ times the length of the largest of the $N$ numbers to be sorted.

  What seems to be needed is a computational model that avoids the potential abuses of the unit cost random access machine, but allows for unit cost operations among operands of “reasonable” size, i.e., operands of size commensurate with the sizes of the numbers to be sorted. Accordingly, we consider a reformulation of the sorting problem wherein our machine has a $b$-bit word size, and each of the $N$ input numbers is assumed to be a non-negative integer less than $2^b$ (and hence each tits into one word). Moreover, it is desirable that a sorting algorithm use only $O(N)$ words of memory.

That is to say, in contrast with RAM model, the transdichotomous model is less powerful because it does not allow unit cost operations on arbitrary large number. For example, in the sorting problem where the largest number is $m$, the transdichotomous model only allows unit cost operations on numbers no more than $m$.

[1] Fredman, M. L., & Willard, D. E. (1993). Surpassing the information theoretic bound with fusion trees. Journal of computer and system sciences, 47(3), 424-436.


Represent a real number without loss of precision

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.


How to create constraints for Mixed integer linear problem?

You have the constraint:

$\sum_{k=t}^{t+H_{i,j}}$ $(x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$ $\geq$ $H_{i,j} (x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$

I presume your iteration variable is $t$. In that case this says that the amount of energy used in the task is at least the expected amount of energy based on its first slot multiplied by task length. This doesn't guarantee using correct type of energy etc.

Assuming you use all required types of energy in the first slot of the task and that you need to use exactly two of them, you should have the following:

Exactly two types of energy used in first slot:

$$x_{t, i, j} + y_{t, i, j} + z_{t, i ,j} = 2$$

If you use some energy in first slot, you need to use it until the end of the task, so in each step variable indicating use of some energy type has the same value as in the first step of the task:

$$ \forall_{t'=t}^{t + H_{i,j}} x_{t', i, j} = x_{t, i, j} $$

Same goes for $y$ and $z$ variables.


Will such an algorithm be feasible, will it be considered a poly time algorithm?

As the length of the input is $p$ and the worst case of the algorithm is $O(p\log(p))$, the algorithm is polynomial as the worst case is $O(p^2)$ and $p^2$ is polynomial.

For the second case, there is not any change in time complexity as constant values are multiplied or divided in the polynomial or logarithmic case. To scrutinize more, $p \frac{\log(p/5)}{100} = p \frac{(\log(p) - \log(5))}{100} = \frac{p\log(p) - p\log(5)}{100} = \Theta(p\log(p))$.


Asymptotics of a recurrence defined with two variables

Interesting recurrence. Let's take a crack at this. Just a heads up, this answer is a bit wordy/explicit.

Clearly the first issue/difficulty is that we're trying to define this in terms of two variables ($n_1, n_2$). This seems hard so let's go ahead and redefine this relation:

$$t(n_1 + n_2) \geq t(n_1) + t(n_2) + c \log_2(1 + n_2)$$

Let $\alpha$ be a constant such that $0 < \alpha \leq \frac{1}{2}$. We can then define $n$ and $n'$ as:

$$n = n_1 + n_2$$
$$n' = \lceil \alpha n \rceil$$

You also asked for the smallest function that satisfies this. I'm taking this to mean when the left side if smallest, so we will redefine $t(n_1 + n_2)$ as:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n - n')$$

or possibly:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n')$$

If we were just looking for the upper bound of $t(n_1 + n_2)$ then we would only need the first case because it is the worst case, but we are looking for the tight bound. In any case, we now have a more manageable form of our recurrence.

You can prove by induction that:

$$an \leq t(n) \leq bn - c\log_2 n + d$$

for some constants $a,b,c > 0$. Constant $d$ will be defined momentarily.

Induction step for Lower Bound

$$
\begin{align}
t(n) & = t(n') + t(n - n') + c \log_2(1 + n - n')\\
 & \geq t(n') + t(n - n') + c \log_2(1)\\
 & = an' + an - an' + 0\\
 & = an
\end{align}
$$

Induction step for Upper Bound

$$
\begin{align}
t(n) &= t(n') + t(n - n') + c \log_2(1 + n - n')\\
 &\leq t(n') + t(n - n') + c \log_2 n\\
 &= bn' - c\log_2n' + d + b(n-n') - c\log_2(n-n') + d + c \log_2 n\\
 &= bn + 2d - c\log_2n' - c\log_2(n-n') + c \log_2 n\\
 &= bn + 2d - c\log_2(n'(n-n')) + c \log_2 n\\
 &= bn + 2d - c\log_2(\alpha n(n- \alpha n)) + c \log_2 n\\
 &= bn + 2d - c\log_2(n^2 \alpha (1- \alpha )) + c \log_2 n\\
 &= bn + 2d - 2c\log_2 n - c\log_2( \alpha (1- \alpha )) + c \log_2 n\\
 &= bn - c \log_2 n + 2d - c\log_2( \alpha (1- \alpha ))
\end{align}
$$

Now we can define $d$ in terms of constants $c$ and $\alpha$.

$$ d = c\log_2( \alpha (1- \alpha ))$$

Therefore

$$t(n) \leq bn - c \log_2 n + d$$

Clearly $an \leq t(n) \leq bn$. It's worth noting this is because $d$ will always be negative.

Now we can conclude

$$t(n_1 + n_2) = \Theta(n_1 + n_2)$$


Which of these two functions has a higher order of growth/complexity?

You have gotten wrong the 1st property, that $2^{\log^*(n)} \sim ~n$.  This is not the case.
The notation $\log^*(n)$ is the iterated logarithm, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.