How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? I am reading about embedding/automation of modal logics in classical higher order logic (http://page.mi.fu-berlin.de/cbenzmueller/papers/C46.pdf) and Goedels proof of God's existence is prominent example here https://www.isa-afp.org/entries/GoedelGod.html (as encoded for Isabelle/HOL).
This embedding has embedding for Leibniz equality for individuals:
abbreviation mLeibeq :: "μ ⇒ μ ⇒ σ" (infixr "mL=" 90) where "x mL= y ≡ ∀(λφ. (φ x m→ φ y))"

and this type of euqality is used for the first axiom already:
A1a: "[∀(λΦ. P (λx. m¬ (Φ x)) m→ m¬ (P Φ))]"

which can be written without lambdas as:
A1a: ∀φ[P(¬φ)↔¬P(φ)]

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

The $x$ in $\forall x . P(x)$ is not an argument. It is a bound variable indicating which variable the quantifer is ranging over.
Let us compare the situation to the definite integral, for concretness just from $0$ to $1$. Here is an example:
$$\int_0^1 x^2 + 3 x \, dx$$
This is a very archaic way of writing mathematical expressions that mathematicians like to stick to. In general (and ignoring details about non-integrable functions) the definite integral is itself a function: it takes a function $f$ as an argument, such as $f(x) = x^2 + 3x$ and returns a number (the area under the curve). So we could simply write $I$ for "integrate from $0$ to $1$" and then the integral of $f$ is simply
$$I(f)$$
(Or if you want to keep the integration bounds visible write $I_0^1(f)$, but I won't).
The argument $f$ need not be a symbol, it can be a complex expression:
$$I(x \mapsto x^2 + 3 x)$$
Notice how "$dx$" above changed to "$x \mapsto$". In $\lambda$-calculus notation we would write this as
$$I(\lambda x . x^2 + 3 x).$$
In archaic notation people sometimes feel uneasy about writing
$$\int_0^1 f$$
and so they end up always displaying $dx$ by writing
$$\int_0^1 f(x) \, dx$$
even though there really is no need to do so, because $\int_0^1$ is a higher-order function which maps real-valued functions to real numbers.
If you want to make traditional mathematician feel uneasy you should write
$$\int_0^1 (x \mapsto x^2 + 3 x)$$
on their whiteboards
If this much is clear, then it should be easy to see that the universal quantifier $\forall$ is like integration, except that it takes a propositional function (one mapping into truth values instead of numbers) and returns a truth value.
The archaic notation
$$\forall x . (x^2 + 3 x > -3)$$
can be changed, just like for integrals, to
$$A(f).$$
Here $A$ is the universal quantifier, and $f$ its argument, which is a function mapping from a set to the truth values. An example of such a function is $f(x) = (x^2 + 3 x > -3)$. And again, we can inline the complex expression to get
$$A(\lambda x . (x^2 + 3 x > -3))$$
Now just replace $A$ with $\forall$ for good old times sake:
$$\forall(\lambda x . (x^2 + 3 x > -3)).$$
This his how computers like it. The notation is general, so we can write just $\forall f$ instead of $\forall x . f(x)$, and it exposes $\forall$ for what it is: a higher-order function that maps propositional function to truth values.


Another vertex cover question? I'm not sure this is equivalent to bipartite vertex cover question. The question is:

Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex from the left side.

e.g. In the following graph, the answer is 1, cause vertex g has connection to all vertex on the left.

It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\{d\},\{d\},\{a,b,c,d\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.


Essential bit content - prove that we can't use less bits than that Let $H_0$ be $\log_2(|A|)$, where $A$ is a set.
Let $C$ be a compressor $C\colon A \to \{1,0\}^l \cup \bot$.
This is a silly question, because intuitively it seems obvious.
How can I prove that $l$ can't be less than $H_0$?
I can prove that $l = H_0$ is sufficient, but how can I prove that it can't be less.

The function wouldn't be one-to-one otherwise.
The size of the set in the left is $|A|$, and its image would be of size at most $2^l<2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.
Therefore it will be a lossy-compression for any $l<H_0$.


How to prove that $L^* = L^*L^*$ I need to prove or disprove that $L^* = L^*L^*$.
Intuitively, I know this is true, and I know I need to prove that $L^*$ is subset of $L^*L^*$ and that $L^*L^*$ is a subset of $L^*$.
But I am really struggling to prove that.

Here is a partial answer, to put you on the right track. Try to complete it to a full answer.
Let's try to show that $L^*\subseteq L^* L^*$.
Let $x\in L^*$, so we know that we can write $x=y_1\cdots y_k$ where $y_i\in L$ for all $i$.
Now, let's assume for a moment that $k\ge 2$, then we can look at two words: $x_1=y_1$ and $x_2=y_2\cdots y_k$. We then have that $x=x_1x_2$ and $x_1\in L^*$ and $x_2\in L^*$, so $x\in L^*L^*$.
If $k<2$, then we can take $x_2=\epsilon$, and possible $x_1=\epsilon$, and the proof still works. So we have $L^*\subseteq L^* L^*$.
Can you now follow a similar scheme for the other containment?


If there is any research on Goal Based Programming (GBP)? The more I think about programming and optimization, the more I think "why not just specify a goal and have the program figure out the optimal solution to it".

I am familiar with basic "optimization problems" such as finding the best fit line to a curve, or gradient descent sorts of things. What I'm talking about is way more complicated than that.

What I'm imagining is to say something like "An HTTPS server exists", and for the system to figure out how to build one. Obviously given just that info, it's not enough. It would require human-level training in programming and understanding concepts and everything.

But my question is, what could you do to build a system to support such a "goal statement"? What would the key parts be?

It seems at first, the simplest goal is "Action x is performed". This is required to change the current world into the desired (goal) world. For example, "Add" is performed on 1 and 2 is a goal stating that the "add" function is applied to the two arguments. It seems that from this foundation, you can build up higher and higher levels of abstraction to the point where you could then say "An HTTPS server exists". But this HTTPS server is a structure, not an action. So you need some way to have some intermediate goals that transcribe goals into (not actions, but) structures. Perhaps, The result of x operation exists is a simple transformation between the two.

But then I'm stuck haha. What do the goals look like in the intermediate realm? Has anyone done any research into this area? Searching doesn't yield much, though it brings up a book Goal programming and extensions which I might have to purchase.

Yes.  The research area is known as program synthesis.  You can find hundreds or thousands of papers on the subject.  (You might also be interested in declarative programming.)

What you're describing is way beyond the state of the art.  It'd be really cool if we could do something like that -- but we're a long long way away from knowing how to build that.


Hash function orders ships from closest to furthest from the origin Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle).

We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to furtest away from the origin.

We want to have an expected time complexity of this ordering algorithm to be done in $\theta(n)$ time.

Each ship has a coordinate $(x,y)$, and so I want my hash function to be something like $\text{h((x,y)) = small index if close to origin, big index if farther}$.

What would be a hash function and algorithm that can run in expected $\theta(n)$ time?

I think my hash function should be something like the following, taking into account the distance:

$h((x,y)) = \sqrt{(x-0)^2 + (y-0)^2} = \sqrt{x^2+y^2}$

You can't.  This problem is as hard as sorting, so it'll need $\Omega(n \log n)$ time (in the comparison-based model); it's not reasonable to expect a linear-time algorithm for sorting.

The obvious solution is to sort the points by their distance from the origin.  If the hash function computes the distance from the origin, well, then you're just sorting hash values.


How to prove NP-hardness of a longest-path problem? I have this question:

Input:
G(V, E) = an undirected graph, V={v1, v2, ..., vn} (V = set of nodes, E = set of edges)
where there is a path connecting from v1 to vn.

Question:
What is the maximum number of nodes you can visit when starting from v1 and ending at vn.
(including v1 and vn)
Each node can only be visited at most once.

I want to prove that this is NP-hard by reducing it from a known NP-complete problem, such as undirected Hamiltonian path or subset-sum.

However I don't know exactly how to do this and this is where I need help.

Can anyone help please?

Assuming I understand your definition, your problem is related to the optimisation version of LONGEST PATH:

  LONGEST PATH
  Input: A graph $G=(V,E)$, an integer $k$.
  Question: Is there a path with at least $k$ vertices in $G$

This problem is NP-complete, there's a fairly obvious reduction from HAMILTONIAN PATH - just set $k = n$, and clearly if we are given an (ordered) set of vertices, we can easily check that it is a path over at least $k$ vertices.

Note that we can assume that $G$ is connected, and we will do so from now on.

The optimization version max-LONGEST PATH where we ask for the path of maximum length is then NP-hard (the polynomial-time equivalence of these two problems is a straightforward exercise).

Then the difference between max-LONGEST PATH and your problem is that you have two specified vertices that are the start and the end of the path. Now we need a reduction from some NP-hard problem to your problem, but we already have one that's really close.

Given an instance $G$ of max-LONGEST PATH you should now be able to construct an instance $G'$ of your problem such that if $p$ is the longest path in $G$, then this is almost the longest path in $G'$.

A further hint if you are still beating your head against a wall in about, say, 2 hours:

   Try taking $G$ and adding two new vertices $s$ and $t$ and connecting them so that they can start and end such a path $p$ - remember though that you don't know what $p$ is.


Is a Turing machine without the ability to write on blank cells less powerful than standard Turing? Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

I think the answer is yes but i'm unable to find a computation that standard Turing machine can do but this machine can't.

Any ideas?

The type of Turing machine you describe is a linear bounded automaton (it can only write on the parts of the tape containing the input). LBAs are the acceptors for context-sensitive languages so to find a specific example of a problem that can't be solved with this restriction but can be solved in general by a Turing machine, you just need a language that is decidable but not context-sensitive.

The example given on Wikipedia is:

  An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

For more examples, see Is there an example of a recursive language which is not context sensitive?


Longest common sub-sequences with a condition A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length.
Now you are given two arrays $S$ and $T$ with integers. You need to find a sub-sequence which is common to both arrays, has maximum length, and is a good sub sequence.
This is a pure dynamic programming problem, in which states ( I am not sure,but is is my guess) are $dp[i][j]$  is answer for $S[1:i]$ and $T[1:j]$ ($A[1:i]$ means subarray of $A$ from $1$ to $i$). But I could not find transition between states, could anyone help me.
P.S - Problem link

A two-dimensional $dp[i][j]$ is not fine enough to enable a recurrence relation. We need to track more information to be able to find the solutions to larger problems from the solutions of smaller problems.
Instead of $dp[i][j]$, try filling the following two tables simultaneously

$dp\_good[i][j]$, which means the length of longest common good subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. This number is $0$ is $S[i]\not=T[j]$.
$dp\_bad[i][j]$, which means the length of longest common bad subsequence of $S[1:i]$ and $T[1:j]$ that ends at $S[i]$ and $T[j]$. Here a bad subsequence just means it is not a good subsequence. Again, this number is $0$ is $S[i]\not=T[j]$.

The answer will be the maximum of all $dp\_good[i][j]$.
The above approach should work when you are looking for a sequence that "contains at least one pair of numbers which are adjacent and equal."
For the original problem, Task: ZAJ
Stutter, we should define a good string as a stutter, i.e., a string that consists of successive pairs of two equal elements. A bad string will be defined as "almost a stutter", that is, a strings which becomes a stutter if we delete its last element.


Is there a fundamental difference in LIFO and FIFO entropy coding? The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS).

A very interesting difference between the two is that AC is FIFO and ANS is LIFO. That is, in AC the first symbol you encode into the bitstream is also the first symbol you decode. However with ANS the last symbol you encode is the first symbol you decode.

Is there a fundamental difference between these approaches? Could one be converted into the other? What are the advantages/disadvantages of the two approaches?

LIFO and FIFO encoders with adaptive models are equally capable, with minor implementation differences.

Fabian Giesen writes about this in a blog post:

  Reverse encoding

  As mentioned above, ANS coders are LIFO: whatever order you encode symbols in, the decoder will produce them in the opposite order. All my ANS coders (including the public ryg_rans) use the convention that the encoder processes the data in reverse (working from the end towards the beginning), whereas the decoder works forwards (beginning towards end).

  With a static model, this is odd, but not especially problematic. With an adaptive model, decoder and model have to process data in the same direction, since the decoder updates the model as it goes along and needs current model probabilities to even know what to read next. So the decoder and the model want to process data in the same direction (forward being the natural choice), and the rANS encoder needs to be processing symbols in the opposite order.

To reiterate, in a FIFO coder,

Run the model forwards on the data to obtain intervals corresponding to estimated probabilities
Run the encoder forwards on this list of intervals.
Run the decoder, generating the decompressed data in its original order.

In a LIFO coder:

Run the model forwards on the data to obtain intervals
Run the encoder in reverse on this list of intervals. Streaming is done by encoding in blocks, which can be as large as your memory capacity.
Run the decoder, generating the decompressed data in its original order.


How to compute (x MOD y) with just SUM and MULT gates? It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates.

By the way, I could not come up with designing $MOD$ function with $SUM$- and $MULT$-only circuit. How can one construct such a circuit?

P.S. The Turing machine is simple. Assuming $\#x\#y\#$ as the input, it suffices to go back and forth and cross $y$ of the remaining entries of $x$ as much as possible.

Turing machines and circuits are very different models of computation: Turing machines are a uniform model and circuits are a non-uniform model. Turing machines accept inputs of an arbitrary length, whereas circuits accept inputs of a fixed length. We can convert Turing machines to equivalent circuits in which the properties of the machine we started with are reflected. For example, a Turing machine running in polynomial time can be converted to a sequence of circuits of polynomial size.

If we have a sequence of circuits, one for each possible length of input, we can interpret the sequence as computing a function. As mentioned above, one way of generating such a sequence of circuits is from a Turing machine. Circuits which can be generated by a Turing machine, which accepts $n$ as input and outputs the circuit handling inputs of length $n$, are known as uniform circuits. (There are various more refined notions of uniformity, in which the Turing machine has some resource restrictions.) However, not all sequences of circuits arise in this way. For example, if $L$ is any length in which membership depends only on the length of the input, then $L$ can be computed by a sequence of circuits. However, $L$ need not even be computable. For example, consider the language of all inputs of length $n$ such that the $n$th Turing machine halts on the empty input.

You say that $\{SUM,MULT\}$ is Turing-complete, but there are a few problems with this statement. First, you seem to think of SUM and MULT as gates, which are components of circuits. As explained above, a model for circuits can't really be Turing-complete, though a set of gates can be complete in the sense that using it you can compute any function. Second, we usually (but not always) think of circuits as Boolean-valued. You haven't explained what the domain of SUM and MULT is, but I suspect that it is not $\{0,1\}$. In that case you have to explain exactly what circuit model you are interested in, and what notion of completeness you are interested in: while Boolean circuits can compute all functions $\{0,1\}^n \to \{0,1\}$, the same doesn't necessarily hold in other circuit models such as algebraic circuits.


Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \cdots < x_r = n\}$ such that $f(r,X) := \displaystyle\max_{j=0}^{r-1} \sum_{i = x_j}^{x_{j+1}-1} a_i$ is minimized over all possible $X$.

I can think of a brute force approach, that is, generate $\Theta ({{n-1} \choose {r-1}})$ sets $X$ and calculate the $\max$ for each $X$, each of which takes as many as $r$ steps. This is a very inefficient approach. How do I make it better? I feel like there is a way using DP. (Please feel free to edit the title if this is not DP).
This seems like a possible solution. What if we pre-compute $\displaystyle\Sigma_{i=j}^{j+k} {a_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function $$\text{best}(p,q) = \text{best way of having } q \text{ intervals such that we end at } [p-x,p] \text{ for some } x \geq 0$$ Our goal is to find $\text{best}(n,r)$ and backtrack to find the intervals.
$\text{best}(p,q) = \min \{ \text{best}(p,q-1), \ \max(\text{best}(p-1,q-1), \text{dist}(p-1,p)), \ \max(\text{best}(p-2,q-1), \text{dist}(p-2,p)), \dots) \}$
where $\text{dist}(x,y)$ = $\displaystyle\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult and time-hungry.
I tried greedy and I could generate counter-examples right away. Was not very helpful.

Main idea: Instead of finding $X$ itself, find the minimum value for $f(r,X)$. After you do this, it is easy to find a minimal $X$. Simply greedily add elements to an interval until the sum of the interval is too large - once this happens, create a new interval at that position.
Finding the minimal value for $f(r,X)$ is a classic (maybe prototypical) binary search problem. The algorithm is as follows: binary search over the answer. Within your binary search, greedily add elements to an interval until the sum of the interval is higher than the answer - once this happens, create a new interval. (Note that this is the same method as is used to construct $X$.) At the end, check how many intervals you have formed - if it is $\leq r$ then it is possible to divide the array into $r$ intervals such that $f(r,X) \leq ans$. The time complexity is $O(NlogS)$, where $S$ is the sum of all $a_i$.
Although binary search does work for all practical values, your statement does state $\mathbb{N}$ as the possible size of elements. If elements can be arbitrarily large, we can use DP as you mentioned, fairly similar to the DP that you use. $best(p,q)$ can be the minimum $f(\cdot)$ taking $q$ intervals from the first $p$ elements. By transitioning in the same way as your statement, we get a trivial $O(N^3)$ solution.
We can also optimise this DP. One optimisation: $best(x,q)$ is monotonically increasing as $x$ increases, but $dist(x,p)$ is monotonically decreasing. So, we can use binary search to find the intersection of the two lines. The transition is now $O(logN)$ and the overall complexity is $O(N^2logN)$.
Important thing to note: this DP avoids the issues with your DP because it doesn't store the actual $X$ within the DP itself.


Why to implement Open list in Heuristic search with priority queue I don't understand why do we need to implement Open list using priority queue? There could be other data structure.

I understand the usage of priority queues from this example clearly. The newly discovered node would always be inserted at the head of the Open List. Then why do we need priority queue?

This article has mentioned everything about open list.

Usually Open Set contains the states. Its more convenient to assume Open Set as a list. However, the when we were to implement it in some programming language, we use priority queue as data structure.

By states, I mean assume rubix cube of 6 faces. When  we rotate it we could have 3 possibilities: 90, 180, 270 degree rotations.

Total states 6x3 = 18

Your question is not perfectly clear to me, so maybe I answer a different question from what you intended. The article you linked talks about A* as a search algorithm that uses a heuristic to speed up searching, so I'll talk about this.

In a naive search you explore a graph for example in breadth first order: You start at some node, then visit its neighbors, then the neighbors of the neighbors and so on until you reach your goal state (or there is nothing more to explore).

Now suppose you had some function (the "heuristic") that can tell you more or less accurately how close a particular node is to your goal node. Then you can speed up your search by visiting nodes that are closer to your goal first. Now it depends on the quality of your heuristic how you should do that.

If your heuristic is perfect, that is, it tells you the distance to the goal accurately for every node, then you can just look at the neighbors of your start node and proceed to the node with the smallest distance to the goal. From there again you look at the neighbors and proceed to the one with the smallest distance to the goal. You don't need to keep any memory of possible alternative routes, because your heuristic exactly tells you which node you have to go to.

If the heuristic is not perfect however, the picture changes. Say your heuristic is optimistic, that is, it always underestimates the distance to the goal. Then can't assume that the neighbor with the smallest heuristic distance to the goal is always the correct node to which to proceed, because it might turn out that the true distance is much larger than what your heuristic told you. So you have to remember some alternative routes.

You can do that as follows: Maintain a set of nodes to which you could proceed (the neighbors of all nodes that you have already seen but not visited). This is you open set. In each step you continue searching from the node in the open set where the distance from the start plus the heuristic distance to the goal is smallest.

Now how do you find this node in the open set? You could store the open set as a list look at all nodes in each step to find it, but that is inefficient. Instead you could maintain the open set as a heap, where finding the minimum is cheap.

So this is why you want to use a heap in a heuristic search. It speeds up finding the next node from which to proceed with your search.


Is there a polynomial sized arithmetic formula for iterated matrix multiplication? I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow up with some more details.
In particular, they describe a scheme for iterated matrix multiplication (for the purposes of this post, multiplying $n$, $n \times n$ matrices) in log space, poly "catalytic space", and polynomial time. The argument to the best of my understanding can be sketched as follows.

Theorem 4 (second article) says any arithmetic formula (i.e. arithmetic circuit w/ fanout 1) of depth $d$ can be computed with a program of size $4^d$ (and all the previously mentioned space guarantees). Here, "program" is in the context of register machines, and the size is the number of instructions and equals the runtime.

Brent et al. 1973 proved that any arithmetic formula of size $s$ can be "balanced" to have depth $O(\log s)$, so combining with (1) it has a program of size $poly(s)$

For some reason, I cannot find this last, implied claim in either of the articles: there is a arithmetic formula of size $s = poly(n)$ for iterated matrix multiplication. This would imply the claim made by the papers -- that IMM can be done in polynomial time with the other space bounds, but for some reason I can't find the claim explicitly written out, which suggests I am missing something.

The smallest formula I can think of for iterated matrix multiplication is "divide and conquer" on the number of matrices, and results in size $n^{O(\log n)}$, and I don't see any way to improve on this.
The first linked article says "iterated matrix product can be computed transparently
by polynomial size programs", which would seem to follow by putting together 1,2, and 3, but it references an old thesis I can't find anywhere.
So, it's either the case that I've totally misread the argument, or there should exist a polynomial sized arithmetic formula for iterated matrix multiplication. Does anyone know of one?

After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size formula. The idea seems pretty straightforward too:
Everything stated previously applies to all rings, so if the elements of the matrix were $Z_2$, then we could consider the ring of $n \times n$ matrices over $Z_2$. There's clearly a $\log n$ depth formula for the product of $n$ ring elements, so we can apply theorem 4.
The only additional considerations are

Theorem 4 says the program will need only 3 working registers, but since each register holds an entire matrix, these registers will take up $O(n^2)$ space. This turns out to be completely fine for us, since we have polynomial catalytic space to work with.

In order to actually translate the program back onto our (catalytic) turing machine, we need to rewrite matrix instructions to instructions on the underlying ring ($Z_2$ for example). Luckily, this is trivial since each instruction in the form $r_i \leftarrow r_i \pm x \ast y$ becomes $n^3$ primitive instructions: $r_i^{uv} \leftarrow r_i^{uv} \pm x^{uw}y^{wv}$ for $u,v,w = 1 \ldots n$ and no extra space of any sort is used.

This seems to be roughly in agreement with the $O(n^9)$ time complexity given by the second reference from the OP -- the program size of $4^d$ from Theorem 4 combined with the $\log_2 n$ depth of the straightforward matrix multiplication formula makes an $O(n^2)$ sized program, each matrix instruction which is further broken down into $O(n^3)$ "primitive" instructions, and each instruction might take up to $O(n^3)$ time to execute on a turing machine due to the size of the inputs.


Formal defintion of SET-PARTITION as a language I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it

$$
\left\{ \langle S,A,B\rangle  \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\in B} n \right\}
\quad \text{ or } \\
\left\{ \langle S\rangle   \;\middle|\; \text{ there exists a partition } (A,B) \text{ of } S \text{ with } \sum_{n\in A} n = \sum_{n\in B} n\right\} \quad ?
$$

The set partition problem asks whether there exists a 2-partition of a multi-set such that sum of numbers in one set is equal to the sum of numbers in the other set.

Note the phrase whether there exists; if you are already being given the partition in the input $\langle S,A,B \rangle$ then the problem becomes whether the given partition is valid and sum of elements of $A$ and $B$ are equal. This problem is easy and can be solved in polynomial it time.

However, Set Partition is NP-Complete, which seems unlikely to be solved in polynomial time.


How does size of list in merge-sort, quick-sort, insertion-sort, matter? We have been taught that:

Insertion-sort will best work if we have a small list.
Quick-sort will best work if we have a long list.
Merge-sort will best work if we have a huge list.

It is not intuitively understandable.
However, let us say if we have a list with 20 elements and want to sort it because shifting action does cost a lot for us, that would be a perfect choice to go with Insertion-sort.
I do not know If I am getting the idea right or not, but my issue is that I can not correlate the logic behind these sorting algorithms with the size of lists, Also does worst, average and best cases affect the size list.
getting me out of confusion would be really much appreciated, thanks.

It's unclear to me why you put the algorithms in that order. Also, "best work" is quite informal. There are many ways to compare sorting algorithm (worst-case time, expected-time, space complexity, etc). Some considerations that might help you are below.
I can see how InsertionSort could be faster than MergeSort of QuickSort in practice for small lists.
The worst-case complexity of InsertionSort can be upper bounded by $c n^2$ for some constant $c$, while the worst-case (resp. expected) complexity of quicksort can be lower bounded by $c' n \log n$ for some $c'$. It might very well be that the multiplicative constant $c'$ is large enough to satisfy $c n^2 < c' n\log n$ for small $n$.
For huge lists, a "standard" implementation of merge sort requires $O(n)$ auxiliary space, while quick-sort can be run in place. They both have the same asymptotic expected running time, so if that's how you are comparing your algorithms, QuickSort might be preferred.
If you're comparing the algorithms by their worst case running time then it might be the case (I didn't estimate the actual constant, which depends on the specific implementation anyway) that QuickSort runs in time $\approx c_q n^2$ while MergeSort runs in time $\approx  c_m n \log n$. In this case MergeSort is clearly preferred for large enough list but, if  $c_q \ll c_m$, QuickSort would be preferred for moderately-sized lists.
Notice that, in practice, you can just use QuickSort (since the extra overhead spent for small lists in negligible, in the absolute sense). Fancy implementations (such as the ones often found in standard libraries) use hybrid algorithms: they run QuickSort and if they realize that the size of the subproblems is somehow not shrinking fast enough, they revert to MergeSort. Whenever the number of elements left to sort is small, they switch to a quadratic-time sorting algorithm like InsertionSort.


Transitions triggered by sets of events In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a transition could be triggered by a set of events, such as receiving any one of some set of characters?

Technically, a transition has to be an atomic event (in the context of formal languages, the reading of a symbol). That said, there are two situations in which you could imagine something different:

1) You could use a set of symbols as an abbreviation of multiple alternative transitions from one state to the other, or a string of symbols as an abbreviation of a sequence of transitions that happen one after the other. In fact, a number of different abbreviations are commonly used when dealing with finite automata on practical situations.

2) You could have a language whose symbols have an internal structure (for instance, they are encodings of sets). Of course, this internal structure should be transparent to the formal treatment of the language.

As with any alternative representation of a formal expression, these variations should be used when their understanding is clear, from definition, or context.


Designing a DFA for binary strings having 1 as the fourth character from the end I came across someone else's old post here

Designing a DFA that accepts strings such that nth character from last satisfies condition

And decided to try it. Apparently it was a homework problem but it was from 2013 so I assume it is okay to discuss it openly by now.

The problem is:

  Design a DFA that accepts strings having 1 as the 4th character from
  the end, on the alphabet {0,1}

The regular expression that does this I believe is (0|1)*1(000|001|010|011|100|101|110|111).

My NFA:

Used Google to see how DFAs work and tried this translation:

Was this a valid solution to the problem?

(Blue arrow = points to starting state, green states are accepting states)

You have not created a DFA.

What you have created is a second slightly less messy NFA. (Sort of; as mentioned in comments elsewhere you need the explosion of internal states out from (2) that you have out from (9) in the original NFA)

So let's pretend that we have an NFA that is made by chopping off state (2) in the second picture and adding state (9) from the first picture in its place.

Now, let's walk through the powerset construction on that new NFA:

Start in state {1}. So let's call the DFA state corresponding to the singleton set {1}, DFA_1.

From DFA_1 you can see either a 0 or a 1. On 0, DFA_1 goes to {1}, so DFA_1 again. On 1, it goes to {1,9}. Call that DFA_2.

From DFA_2, on 0 it goes to {1,10,13,16,19}. Call that DFA_3. On 1 it goes to {1,9,22,25,28,31}. Call that DFA_4.

For DFA_3, on 0 it goes to {1,11,14} (since the other nodes only have transitions out on 1). Call that DFA_5. On 1, from DFA_3 we go to {1,9,17,20}. Call that DFA_6.

For DFA_4, on 0 it goes to {1,10,13,16,19,23,26} - call that DFA_7. On 1, DFA_4 goes to {1,9,22,25,28,29,31,32}. Call that DFA_8.

For DFA_5, on 0 it goes to {1,12}. Call that DFA_9. Note that DFA_9 is an accepting state. On 1 it goes to {1,9,15}. Call this DFA_10, also an accepting state.

For DFA_6, on 0 it goes to {1,10,13,16,18,19}. Call this DFA_11. On 1, we get {1,9,21,22,25,28,31}. Call this DFA_12. Note that DFA_11 and DFA_12 are accepting states.

For DFA_7, on 0 it goes to {1,11,14,24}. Call that DFA_13. On 1, we get {1,9,17,20,27}. Call that DFA_14. (DFA states 13 and 14 are accepting states)

For DFA_8, on 0 it goes to {1,10,13,16,19,23,26,30}. Call that DFA_15. On 1, it goes to {1,9,22,25,28,29,31,32,33}. Call that DFA_16. (DFA states 15 and 16 are accepting states)

For DFA_9, on 0 it goes to {1}. We've seen this before! That's DFA_1. On 1 it goes to {1,9}, which is DFA_2.

For DFA_10, on 0 it goes to {1,10,13,16,19}, that is, DFA_3. On 1 it goes to {1,9,22,25,28,31}, that is DFA_4.

For DFA_11, on 0 it goes to {1,11,14}, which is DFA_5. On 1 it goes to {1,9,17,20}, that is, DFA_6.

For DFA_12, on 0 it goes to {1,10,13,16,19,23,26}, or DFA_7. On 1, it goes to {1,9,22,25,28,29,31,32}, or DFA_8.

For DFA_13, on 0 it goes to {1,12} (DFA_9). On 1 it goes to {1,9,15} (DFA_10).

For DFA_14, on 0 it goes to {1,10,13,16,18,19} (DFA_11). On 1, we get {1,9,21,22,25,28,31} (DFA_12)

For DFA_15, on 0 it goes to {1,11,14,24} (DFA_13) On 1, we get {1,9,17,20,27} (DFA_14).

For DFA_16, I hope you can see the pattern by now. On 0 it goes to DFA_15 and on 1 to DFA_16.

So, in summary:

DFA state #  |   Next for 0  |  Next for 1  |  Accepting?
---------------------------------------------------------
          1  |       1       |      2       |
          2  |       3       |      4       |
          3  |       5       |      6       |
          4  |       7       |      8       |
          5  |       9       |     10       |
          6  |      11       |     12       |
          7  |      13       |     14       |
          8  |      15       |     16       |
          9  |       1       |      2       |  yes
         10  |       3       |      4       |  yes
         11  |       5       |      6       |  yes
         12  |       7       |      8       |  yes
         13  |       9       |     10       |  yes
         14  |      11       |     12       |  yes
         15  |      13       |     14       |  yes
         16  |      15       |     16       |  yes

As a side note, I think this process might have been simpler had you started with an NFA of only 5 states corresponding to the regex (0|1)*1((0|1)(0|1)(0|1)).

(Though you'd still end up needing 16 DFA states - it can be proven that that's the minimal number of DFA states needed for this problem)


how to solve this lambda expression with free variable/s Iam a beginner in Lambda Calculus, I have a expression
saying

(λx.xy)

Here y is a free variable and x is a bound variable. My question is what would be the value of the expression (which has free variables).

The term $\lambda x . x y$ is in normal form. It does not reduce any further.

In general, to find out these things, you can just type them into a $\lambda$-calculus calculator. One is available in my PL zoo (hmm, it is momentarily under construction):

lambda @ programming languages zoo
Type Ctrl-D to exit or "#help;" for help.
# #constant y ;
y is a constant.
# ^ x . x y ;
    = λ x . x y

The language wants you to declare free variables as constants, which is why we first explain that y is a known constant.


How to understand these exposure algorithm rules for System F sub? The book "Types and Programming Languages" said System F sub type checking introduce exposure typing rules alongside algorithmic typing and sub-typing rules.

       exposure algorithm

       X<:T ∈ Γ        Γ |- T ⇑ T'
       --------------------------- (XA-PROMOTE)
               Γ |- X ⇑ T'

        T is not a type variable
       --------------------------- (XA-other)
               Γ |- T ⇑ T

The first one seems simple, but the second rule seems bit wrong to me.
"T is not a type variable", which "T" it is referring to?

Does "Γ |- T ⇑ T" mean left and right hand side of "⇑" are same types?

For example, with the type checking

          " Γ |- sone: SPos"

where

          sone= λ A <: Top.
                 λ B <: A.
                  λ C <: A.
                   λ m : A->B.
                    λ n : C. m n.

          and

          SPos= All A <: Top. All B<: A. All C<: A. (A-> B) -> (C-> A).

After applying "TA_TABS" and "TA_ABS" rules

 {A <: Top, B<: A, C<: A, m : A->B, n : C } |- m n :B
-----------------------------------------------------------TA-APP
 {...} |- :- m:T1   ,  {...}|-T1 ⇑ (T11->B)  ,  {...}|-n:T2  , {...}|-T2<:T11

 {...}|-n:T2    we know  T2=C
 then
 {...}|-C<:T11  we get T11=top

 then put it in place

 {...} |- :- m:T1   , {...}|-T1 ⇑ (top->B)
 ------------------------------------------

which rule applies now?

I believe from

{...}|-T1 ⇑ (top->B)

we should get "T1=A->B" , but how?

both (XA-PROMOTE) and (XA-other) seems cannot be applied.

please help!

In a typing rule (and more generally any deduction rule), all metavariables¹ are universally quantified. That is, the rule can be applied for any instantiation that is syntactically correct. For example, (XA-PROMOTE) means “for any context $\Gamma$, for any type variable $X$, for any type $T$, for any type $T'$, if $\Gamma$ contains $X <: T$ and the typing judgement $\Gamma \vdash T \Uparrow T'$ is true, then the typing judgement $\Gamma \vdash X \Uparrow T'$ is true”. The rule (XA-other) states “for any type $T$, for any context $\Gamma$, if $T$ is not a type variable then the typing judgement $T \vdash T \Uparrow T$ is true”.

The question “which $T$ is it referring to?” is not meaningful: the rule does not refer to a particular $T$. On the contrary, the rule applies to any $T$; the conclusion applies to any $T$ that matches the premise.

In $\Gamma \vdash T \Uparrow T$, the left- and right-hand sides of $\Uparrow$ are the same type. The rule states that the relation $\Uparrow$ in any given context $\Gamma$ is symmetric on the subset of the set of all types that consists of the types that are not type variables. Some examples of typing judgements that can be derived by this rule are:
$$
\vdash \mathsf{Top} \Uparrow \mathsf{Top} \\
X <: \mathsf{Top}, Y <: X \vdash X \rightarrow \mathsf{Top} \Uparrow X \rightarrow \mathsf{Top} \\
X <: \mathsf{Top}, Y <: X \vdash (\forall Z <: Y, X \rightarrow Z) \Uparrow (\forall Z <: Y, X \rightarrow Z) \\
$$

I don't remember Pierce's presentation and I don't have the book here, but I think the reason XA-other has the premise that $T$ must not be a type variable is to make these rules syntax-directed: there's another rule that allows deriving judgement $\Gamma \vdash T \uparrow T$ when $T$ is a type variable. This is a presentation choice.

¹  A metavariable is a variable that is used to describe the system, for example $X$, $T$, $T'$ and $\Gamma$ in the rule (XA-PROMOTE). We use the term metavariable to distinguish this concept from a variable, which refers whatever the language calls a variable.


Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$? $$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$
The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{n}{8}\cdots\frac{n}{n}$. This equals $n^{\log n}$ divided by what? If the product would just be $n^{\log n}$, then this would make perfect sende since $ \log(n^{\log n})=\log(n)\cdot\log(n)=\log^2 n$. But the divisor equals $\frac{1}{2}\cdot\frac{1}{4}\cdot\frac{1}{8}\cdot\frac{1}{16}\cdots\frac{1}{n}$ so I don't get it.

Assuming $n$ is a power of $2$, you have:
$$
\sum_{i=0}^{\log n} \log \frac{n}{2^i} =
\sum_{i=0}^{\log n} \left( \log n - i \right) =
\sum_{i=0}^{\log n} i =
\frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n).
$$


What is the difference between "algorithm," "process" and "program"? I am currently studying algorithms and algorithmic design, and I am confused those terms. What is the difference between them?

Thank you.

These terms are often used very loosely and to mean different things. The definitions below uses Wikipedias definitions as an outset, but tries to make them more clear and formal. Being this strict is usually not needed in practice.

Program

Computer Program: A collection of instructions that performs a specific task when run$^{1}$ by a computer [Wikipedia].

These instructions can be expressed in low level assembly or in some high level language in the source code. To be able to run the program the instructions must be represented as machine instructions for the targeted CPU.

Process

Computer Process: An instance of a computer program that has been "loaded" to virtual memory$^2$ [Wikipedia].

In contemporary operating systems a process can be in several states, such as running (i.e., being processed by the CPU) or waiting [Wikipedia].

Algorithm

Algorithm: An unambiguous specification, that can be expressed within a finite amount of space and time, and in a well-defined formal language, for calculating a function [Wikipedia].

Most programs includes one or more algorithms, but they also do other things, such as side effects (e.g., I/O operations) [Wikipedia].

Footnotes

$^1$ The Wikipedia article actually uses "executed" which is a very common verb to use in this case. There is two reasons why "run" or "being processed" could be preferable:

When a CPU is processing instructions it does more than just executing them: the other actions are usually defined as fetching instructions and decoding instructions.
As is shown in the definition for process, the term running is usually used when referring to this.

$^2$ The Wikipedia article actually uses "executed" (again) which is a very common verb to use in this case as well. For the same reasons as above, some other terminology can be preferable if one needs to be precise.

In addition, due to the process states, it might not even be running either, just being in the virtual memory space (i.e., in RAM or swapped).


Are there any "complete" languages in $coNP -NP$? Suppose $coNP \neq NP$

language B would be called "complete" in $coNP-NP$ if:

$B\in coNP - NP$
$A\in coNP-NP \implies  A\leq_pB$

Are there any "complete" languages in $coNP - NP$?

If we are assuming that $coNP≠$,

we can conclude that every language that is $co
NP$ complete is not in $NP$ (a contradiction to your given assumption).

Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.


Defining decision-problem complexity classes by counting branches of a polynomial-time NTM This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) use that term to refer to complexity class like #P of counting problems that count the accepting branches of a polynomial-time nondeterministic Turing machine (NTM). The author of the linked answer seems to be using the term to mean a complexity class C for decision problems such that C can be defined in terms of this count. Am I understanding this correctly?

If so, then I believe that all of the following counting complexity classes (in the latter sense of the term) can be defined in the form "C is the set of decision problems for which there exists a polynomial-time NTM such that ...". Am I completing the sentences correctly for each counting complexity class?

P: if the answer is yes then every branch accepts, and if the answer is no then every branch rejects. (My answer below explains why this definition is equivalent to the usual one.)
RP: if the answer is yes then a fraction $p$ of the branches accept, where $p$ is a positive number that does not depend on the input size. If the answer is no then every branch rejects.
co-RP: if the answer is yes then every branch accepts. If the answer is no then a fraction $p$ of the branches reject, where $p$ is a positive number that does not depend on the input size.
BPP: if the answer is yes then a fraction p of the branches accept, where $p > 1/2$ does not depend on the input size. If the answer is no then a fraction q of the branches reject, where $q > 1/2$ does not depend on the input size.
NP: if the answer is yes then at least one branch accepts. If the answer is no then every branch rejects.
co-NP: if the answer is yes then every branch accepts. If the answer is no then at least one branch rejects.
C$ _=$P: if the answer is yes then exactly half the branches accept. If the answer is no then the fraction of accepting branches does not equal $1/2$.
PP: if the answer is yes then most branch accept, and if the answer is no then at least half the branches reject.

One advantage of this formulation is that it makes obvious the class inclusions P $\subset$ (co-)RP $\subset$ BPP (using this trick) $\subset$ PP and (co-)RP $\subset$ (co-)NP $\subset$ PP (using Buchfuhrer's trick here).

Note: In order to make this question clearer and more useful for future viewers, I have edited it to make every definition correct. The definitions in the original version of my question (available in the question history) had a few errors, which Ariel pointed out in their answer.

In the abstract of Counting classes: thresholds, parity,
mods, and fewness”, by Beigel and Gill, any class of languages whose membership of some input $x$ can be determined by some function of $\#M(x)$ (the number of accepting paths of the NTM $M$ on input $x$) is considered a counting class.

In regards to your "counting description" of some known classes, your characterization of $\mathsf{ZPP}$ is actually a description of $\mathsf{P}$ (there is no mentioning of the power of expected polynomial time over worst case polynomial time). Additionally, your description of $\mathsf{P}$ is not very clear, a Turing machine can be either deterministic or non deterministic (those are different models of computation), so there is no NTM which is "actually deterministic". It is not clear how to give a counting characterization of $\mathsf{ZPP}$, since it differs from the rest of the classes by relaxing the polynomial time property.

Additionally, note that in the NP/coNP case you have an equivalence, i.e. $x\in L$ iff there exists some accepting path/ iff all paths are accepting. Requiring only one implication results in a stronger class.


Break keyword outside a loop is syntax error or semantic error? I am designing a simple compiler for my university project. In my programming language, the break keyword is allowed.
I want to know whether break keyword occurs outside a loop should be a syntax error or semantic error. I want to know what is the best approach.
If it is a syntax error I can do it in the grammar file. But if it is a semantic one then I can do it in a pass. But I don't know which one is the better approach.

Both work, so how you do it is up to you. But there are a couple of reasons to consider doing it during a post-parse analysis:

While it is certainly possible to define two different types of block, one in which break is legal and the other one in which it isn't, the result is a lot of duplication in the grammar, and a certain complication because you have to allow break inside blocks which are themselves contained inside a looping construct. If you allow compound statements without explicit blocks, like if (condition) break;, then you also need to define different if statements, etc. This rapidly gets out of hand unless you have a tagged formalism like that used in ECMAScript.

Detecting the error in a post-parse scan will allow you to produce better error messages. Rather than just presenting the user with some kind of syntax error message (which might be "unexpected token 'break'"), you can actually provide a meaningful error message like "'break' statement cannot be used outside of a loop."


Regular expression for words where the same symbol can repeat at most two times consecutively? Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?

For example, I can't have ${baaab}$ nor ${abbba}$, but I can have ${abbaabba}$.

Every string over $\{a,b\}$ can be decomposed into runs of the same letter. For example, $$ abbaabba = a^1 b^2 a^2 b^2 a. $$
Since the alphabet is binary, the runs just alternate between the two letter. In your case, every run has length 1 or 2. We can distinguish between four types of words in your language, depending on which run is first and which run is last; additionally there are some corner cases. The set of words in your language in which the first run is $a$s and the last run is $b$s corresponds to the regular expression $((a+aa)(b+bb))^+$.

I'll let you figure out the rest.


How exactly do you calculate the hidden layer gradients in the backpropagation algorithm? I have been going through the description of the backpropagation algorithm found here. and I am having a bit of trouble getting my head around some of the linear algebra.

Say I have a final output layer $L$ consisting of two visible units, and layer $L-1$ consists of four hidden units. (this is just an example to illustrate my problem)

my understanding is that the weight matrix for this final layer ($w^L$) should be a 4 x 2 matrix.

the reference says to calculate the output error $\delta^{x,L}$ given by:

$\delta^{x,L} = \nabla_a C_x \odot \sigma'(z^{x,L})$

where:

$z^{x,L} = w^La^{x,L-1} + b^L$,

$a^{x,L} = \sigma(z^{x,L})$, and

$\odot$ is the hadamard product.

evaluating $\delta^{x,L}$ gives a 1 x 2 vector, as it should given there are two output units.

my problem is when calculating the hidden layer gradients (eg. $L-1$) given by:

$\delta^{x,L-1} = ((w^L)^T\delta^{x,L})\odot\sigma'(z^{x,L-1})$

now if $w^L$ is a 4x2 matrix and $\delta^{x,L}$ is a 1x2 vector then wouldnt $(w^L)^T\delta^{x,L}$ be a multiplication of a 2x4 matrix and a 1x2 matrix, which is impossible?

i feel like i have missed something vital in my understanding, but i cant work out what it is.

is it just as simple as making it $\delta^{x,L}(w^L)^T$? this would be a 1x2 matrix multiplied by a 2x4 matrix, which is perfectly legal. but the formula has it around the other way.

can anyone see where my understanding is flawed? any help would be greatly appreciated

You've transposed the sizes of both $w^L$ and $\delta^{x,L}$.  $w^L$ should be 2x4 and $\delta^{x,L}$ should be 2x1.  $(w^L)^T$ is a 4x2 matrix that will be multipled by a 2x1 matrix yielding a 4x1 matrix suitable for the next step of backpropagation.
In general for neural nets the activation units are represented as column vectors and the weights are matrices of dimension |L+1| x |L|, where L is the current layer and L+1 is the next layer (in the forward direction).


Sorting an array of strings by length in linear complexity I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity.
The max length of the strings is known.
Because of that, I tried using counting sort, but I failed to do in O(1) space complexity. Because multiple strings might have the same length, I need to store the strings in some kind of 2D array for each possible length, and that is O(n) space in the worst case of all strings having the same length.
How would I go about solving this problem?

Assume the maximum length of strings is $k$, which is less than some constant.

Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement.

Assume the input is an array $s[0], s[1], \cdots, s[n-1].$

Count the number of strings of length $i$. Store it in $a[i]$. We can imagine that $s$ is split into $k+1$ blocks of size $a[0], a[1], a[2], \cdots$. In the following steps, the $i$-th block will store the strings of length $i$.

Let $b$ be the partial sums of $a$, i.e., $b[0]=0$, $b[i+1]=b[i]+a[i]$ for all $0\le i\le k-1$. Note that $b[i]$ is the index of the first string in the $i$-th block.
Let $t[0], t[1], t[2],\cdots,$ be an array of $k$ numbers. We will use $t[i]$ to track the next available position to settle the next string of length $i$. Initially, $t$ is a clone of $b$.
Let $j=0$, the index of the first unsettled string. Loop the following.

Suppose the length of $s[j]$ is $i$.

If $j\neq t[i]$, switch $s[j]$ and $s[t[i]]$. Now $s[t[i]]$ is a settled string. Increase $t[i]$ by 1.
If $j= t[i]$, increase $t[i]$ by 1. Keep increasing $j$ until either we find the next unsettled string or we have passed all strings, in which case we return $s$ and stop the algorithm.

How can we increase $j$ efficiently and correctly? We can keep another integer that tracks which block $j$ is in. Note that all strings from index $b[i]$ to $t[i]-1$ inclusive are settled while all strings from index $t[i]$ to $b[i+1]-1$ inclusive are not settled.

It is clear the algorithm runs in linear time. The spaces used besides the original array $s$ are arrays $a,$ $b$ and $t,$ several looping variables, one temporary place needed to switch two strings. In total, the working memory is less than $3(k+1)+c+k=O(1)$.

Exercise. Improve the memory usage of the algorithm by reusing array $a$ for $b$.


Is mutual inductive type definition essential in coq core language? I'm studying Coq's core language and I found that mutual inductive type definition is in it.
https://coq.inria.fr/refman/language/core/inductive.html#theory-of-inductive-definitions
Before I read the material, I had supposed that Coq translates mutual definitions in Gallina into nonmutual ones in its core language, since it allows the core language to be smaller. But it wasn't and then I started to wonder why.
For instance, even and odd can be defined mutually as follows.
Inductive even : nat -> Prop :=
| even_O : even 0
| even_S : forall n, odd n -> even (S n)
with odd : nat -> Prop :=
| odd_S : forall n, even n -> odd (S n).

However, one can write another definition without with keyword.
Inductive even_or_odd: (is_even: bool) -> nat -> Prop :=
    | even_O : even true 0
    | even_S : forall n, even false n -> even true (S n)
    | odd_S : forall n, even true n -> even false (S n).

Definition even := even_or_odd true.
Definition odd := even_or_odd false.

I agree that the former looks better than the latter. However, What I wonder is if it is always possible to rewrite any mutually defined inductive type in a nonmutual way. If then, Coq does not necessarily include the mutual definition syntax in its core language.
Does the mutual definition allow more expressions to be defined?
Is there any mutually defined type that can't be translated to a nonmutual one?
Or there isn't, but my concern about minimal core language is not a big deal?
Also, I am so sure that mutual fixpoints always can be translated to nonmutual ones. It looks much more clear to me compared to the case of inductive definition. Am I right?

It is always possible, as you noted, to translate a mutual inductive family into a non-mutual family, in much the same way as you described.
A couple of difficulties though:

If your mutual inductives are not parametrized, say you have

Inductive Foo := foo : Bar -> Foo
with Bar := bar : Foo -> Bar

(with some constants if you want to make the types non-empty)
Then you have 2 non-dependent types, for which induction, recursion and pattern matching are rather straightforward. But the translation you suggest involve creating a FooBar : bool -> Type which now needs dependent pattern matching everywhere. It's not impossible to cope with this as well, but it makes the elaborator quite a bit more involved.

Even worse are mutual inductives with different parameters: Imagine now

Inductive Foo : nat -> Type := ...
with Bar : bool -> Type := ...

Now we need to define a type FooBar : forall b : bool, I b -> Type where I true = nat and I false = nat. I'll let you imagine the case of multiple, possibly dependent parameters.
All these complications add up to a system that is quite complicated: I think it's a reasonable decision to add special support in the core to handle mutually inductive families, and it's the decision the Coq developers have made.
The Lean developers originally made a different decision, see here for instance.
However my understanding is that the complexities outlined above, along with the difficulty of hiding all this to the user, has made them re-think their position (I believe, but at the moment I can't find the reference of how things are in Lean 4).


Design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$ I need to design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$.
$w^R$ is the reverse of $w$.

I don't have a good idea yet how to do that, I know I should check:

the length of the word must be equal $0\mod 3$

$ww^R$ is a palindrome

the prefix $w$ equal to the suffix $w$.

I thought maybe to divide the word to three parts and use non deterministic TM to move from one part to another.
Need help with the algorithm.

I suggest a deterministic solution using some basic TM trickery.

First you need to identify the parts. Suppose we tag the 0,1 symbols by replacing them by symbols, e.g. A,B (A~0, B~1) - so that we know what we already "tagged" but keep the data "intact". The TM works in a simple loop: move far left, tag the first untagged element, move to far right, tag first two untagged elements. If at some point the tags from left and the tags from right meet, we have found the end of W prefix. If the tags don't meet well, then the length of the input is not divisible by 3 and the TS says NO. Suppose we used A,B tags on left and C,D tags on right (so we can always find the end of W prefix). We split in the C,D part into WR and W in a similar way.

Suppose that the first part now consist of A,B symbols, the middle of C,D symbols and the last of E,F symbols. The TS now reads the three sections in parallel (while the middle one is read in reverse) and compares them in a simple loop, while rewriting the correct parts with some special # symbol. First, move to the left to find the first non-# symbol (which is either A or B). Remember it (use two sets of states, one corresponding to A and one corresponding to B) and replace the symbol by #. Move right until you reach the end of C,D section (the first symbol E,F or # signifies the end), and check if the previous symbol corresponds to the remembered value (A~C, B~D). If it does not, answer NO. Otherwise replace it by # and move to the first E/F-symbol and again check (A~E,B~F) and replace with #. Repeat until there are no non-# symbols left. Once that happens, the answer is YES.


Can a shortest-path tree be a also maximum spanning tree? If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example!

I tried every combination I could come up with using connected graphs with cycles on them (so that there is more than one possible path) and used Dijkstra's algorithm. No luck!

Let A-B-C be connected graph with edges like shown (AB and BC) the shortest path (the only possible) from A to C is through B. To include all vertices in the maximum spanning tree all vertices are needed, so this is small example (the smaller, A-B is also valid).

Maximum spanning tree have maximal weights, but may be not unique for given graph. The shortest path tree (which I assume is the weighted one) have path weights but also is not guaranteed to be unique.

From the definitions finding graph with cycles will be harder - taking minimal example, a full graph with vertices D, E, F and distances |DE| = 3, |EF| = 2, |DF| = 3, the shortest path from E to F is 2, but the maximal spanning tree will not contain this edge.
The two structures may overlap when there are no cycles or weights are equal, otherwise they will get opposite edges when possible.


A new definition of recursively enumerable set? Given a Turing machine $M$, we associate a partial function $f_M : \Sigma^{\ast} \to \Sigma^{\ast}$ to it (this is called the function computed by the machine), where $\Sigma$ denotes the finite input and output alphabet, defined as
$$
 f(u) = v :\Leftrightarrow \mbox{The machine halts on input $u$ with output $v$}.
$$
Then we say an arbitrary partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ is called computable iff $f = f_M$ for some Turing machine $M$.

Then we define a language $A \subseteq \Sigma^{\ast}$ to be recursively enumerable iff it is the domain of some computable function. Clearly with the above definition $\operatorname{dom}(f_M) = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts on input $w$.} \}$, i.e. this is equivalent to say that a language is recursively enumerable iff we can find a machine that halts exactly for the words in the language.

But on other sources I found the following definition, a language $A \subseteq \Sigma^{\ast}$ is recursively enumerable, iff there exists a Turing machine such that
$$
 A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts in an accepting state} \}
$$
or
$$
 A = \{ w \in \Sigma^{\ast} \mid \mbox{The machine halts and outputs a specified output } \}.
$$
Both notions, by special state or special output, are clearly equivalent. But they do not require the machine to run forever if $w \notin A$. This could be fixed, by letting the machine enter an endless loop if it enters a non-accepting state after finishing its computation. But this seems quite unnatural to me.

But I think a better definition, more closely at the definition by acceptance states or special output, in terms of computable functions, would be to call a language $A$ recursively enumerable iff there exists a computable partial function $f : \Sigma^{\ast} \to \Sigma^{\ast}$ such that $A = f^{-1}(B)$ for some $B \subseteq \Sigma^{\ast}$.

Surely with the above definition we can enlarge $B$ always by values not in the range of $f$, so $B$ is not unique, but it would be no problem that the machine halts on some other input $\notin B$ and we would have $A \subseteq \operatorname{dom}(f)$.

So is this definition used anywhere, does it make sense? I could not find it, so I am asking here. Also nobody discusses the two definitions together, either in books they always work with Turing machines, or they work with primitive and $\mu$-recursive functions.

Your definition makes no sense because according to it every language is recursively enumerable. Given any $C \subseteq \Sigma^*$, take $B = C$ and $f(x) = x$, the identity function, which is computable. Then $f^{-1}(C) = C$, therefore $C$ is recursively enumerable.

We can fix your definition by observing that the following theorem holds:

  Theorem: A language $A$ is recursively enumerable if, and only if, there is a partial computable $f$ and a recursive set $B$ such that $A = f^{-1}(B)$.

You are close to reinventing the notion of many-one reduction, by the way.


How do we define a tree in a directed graph? I am trying to solve the exercise 3.3 in Approximation Algorithms by Vazirani, pg 34. It states

  3.3 Give an approximation factor preserving reduction from the set cover
  problem to the following problem, thereby showing that it is unlikely to have a better approximation guarantee than $O(\log{n})$.

  Problem 3.14 (Directed Steiner tree) $G = (V,E)$ is a directed graph
  with nonnegative edge costs. The vertex set $V$ is partitioned into two sets, required and Steiner. One of the required vertices, $r$, is special. The problem is to find a minimum cost tree in $G$ rooted into $r$ that contains all the required vertices and any subset of the Steiner vertices.

My (related) questions

How do we define a tree in a directed graph? I searched on the Internet and found that a tree is defined for only undirected tree, in particular on Wikipedia.
What does it mean "rooted into $r$"? Does it mean out-degree of $r$ is zero?

Sometime there isn't a completely agreed upon meaning of terms, it is more useful to look at the context to see which definition is appropriate.

In this case, instead of searching for definition of general directed tree, it is better to look for directed steiner tree.

A quick search pulled up this paper which has this diagram showing an example of directed steiner tree:

While not explicitly defined, it coincides with my intuition of what a default directed tree should look like --- A directed graph with exactly one directed path from a distinguished root vertex to any other vertex in the graph (tree).


Minimal edge cover of the hypergraph We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?

The polynomial algorithm for "classical" graph is based on a maximum matching algorithm completed with the isolated nodes. 3-dimensional matching is known to be NP-complete (https://en.wikipedia.org/wiki/3-dimensional_matching). This is a case of minimal edge cover for hypergraph. Thus the answer is no.


Can we count the number of inversions in time $\mathcal{O}(n)$? It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).

Is there more asymptotically efficient way to do it? $\mathcal{O}(n)$?
Or is there any proof that’s not possible?

There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper Optimal algorithms for list indexing and subset rank, and Chan and Pătraşcu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper Counting inversions, offline orthogonal range counting, and related problems. Chan and Pătraşcu also gave an $O(n)$ algorithm for finding a $1+\epsilon$ approximation, for any $\epsilon>0$.

If you only allow comparisons, then there is an $\Omega(n\log n)$ lower bound, see this question on cstheory.


Is SAT is in NL?( under certain conditions) Consider a certicate for 3SAT that lists an assignment for each occurrence of a variable in the order
of appearence,e.g. 100000 for ($x\bigvee$$y\bigvee$z)$\bigwedge$($\neg(w)$$\bigvee$$y\bigvee$z). This certicate is of polynomial length and can
be read once to check the satisability of the given formula. Does this prove that SAT is in NL?

The certificate could have linear size, and you need to remember it for the entire verification process. That is, you need to store in on the work tape and reference it as you read the clauses. You can't guess a satisfying assignment for each clause separately - under this model, every 3CNF is satisfiable. The oracle tape is consumed by each read - you can't go back and reread a previous symbol, which might be what's confusing you.


Lower bound of disjointness by discrepancy? I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$.
Disjointness is defined as

$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$

The discrepancy for a function is defined as  $Disc_\mu(f) = \max_R \{Disc_\mu(R,f)\}$ over all rectangles $R$ and further

$$Disc_\mu(R,f) = |\Pr_\mu [(x,y) \in R \wedge f(x,y)=1] - \Pr_\mu[(x,y) \in R \wedge f(x,y) =0] |.$$

I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.

The problem is given as an exercise without a solution in the book Communication Complexity by E. Kushilevitz and N. Nisan on page 40.

You asked two questions.  I'll answer the second.  A rectangle is a set $R$ of the form

$$R = \{(x_1,\dots,x_n) : \ell_1 \le x_1 \le u_1, \dots, \ell_n \le x_n \le u_n\}$$

for some $\ell_1,\dots,\ell_n,u_1,\dots,u_n$.


Are all possible programming languages a formal system? Based on the Wikipedia page for a formal system, will all programming languages be contained within the following rules?

A finite set of of symbols.

(This seems obvious since the computer is a discrete machine with finite memory and therefore a finite number of ways to express a symbol.)

A grammar.
A set of axioms.
A set of inference rules.

Are all possible languages constrained by these rules? Is there a notable proof?

EDIT:

I've been somewhat convinced that my question may actually be: can programming languages be represented by something other than a formal system?

Technically, yes, because you can make your formal system have a single axiom that says “the sequence of symbols is in the set $S$” where $S$ is the set of programs in the programming language. So this question isn't very meaningful. The notion of formal system is so general that it isn't terribly interesting in itself.

The point of using formal systems is to break down the definition of a language into easily-manageable parts. Formal systems lend themselves well to compositional definitions, where the meaning of a program is defined in terms of the meaning of its parts.

Note that your approach only defines whether a sequence of symbols is valid, but the definition of a programming language needs more than this: you also need to specify the meaning of each program. This can again be done by a formal system where the inference rules define a semantics for source programs.


Should Kolmogorov complexity include all resources or just program size? I've been thinking about pi and Kolmogorov complexity (Kc).

As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program.  Through the prism of Kc, it would seem that a generating program (e.g. Gauss-Legendre algorithm) is much smaller than the output sequence hence characterising pi as not random.

The usual semantics revolving around Kc only mention program size so the above definition holds.  Running the Gauss-Legendre algorithm comes at the cost of huge storage, processing power and some electricity.  These resources increase (towards infinity) in some relation to the number of digits generated.  If Kc is redefined as overall resources and not program size, pi becomes random.

Should Kc be restated as being resource based and not solely program size based, or is that an abstraction too far?

P.S. This is not a question of whether pi is random, but about a definition of Kolmogorov complexity.

Should Kc be restated as being resource based and not solely program size based?

No.  If you change the definition like that, you get a different concept, and the different concepts deserves its own different name.  If you want to examine that concept, you should give it its own name.  Kolmogorov complexity is a standard term with an accepting meaning; trying to "change" its meaning would only cause confusion.

Instead, if you want to study that alternative concept, give it a new name, and then study its properties.  There's no need to change the existing definition of Kolmogorov complexity: Kolmogorov complexity is an interesting and useful concept to have in one's vocabulary.  Removing it from our mental toolbox would only make our intellectual scope poorer.

To give you an analogy: If curves of the form $y=ax^2+bx+c$ are more useful in a practical application than lines, should we re-define the term "linear" to mean a function that can be expressed as $y=ax^2+bx+c$?  No, that would only cause confusion.  Instead, we give a different name (quadratic) to the different concept.


Code to get java code complexity I have Java function as input and want to get it's order for example O( n )
I search in the internet very hard but didn't find any thing can help me, is there any algorithms or package may help me.

No. There's no algorithm to analyze the asymptotic complexity of a piece of code given as input. Being able to do that would tell you whether the code halted and that's undecidable.


Maximum value of $\{ i \land n \mid a \leq i \leq b \}$ I was doing problems in "Leetcode" and found a problem that I could not solve.

Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \leq b$ and among those find the maximum value of $n \& i$ where $\&$ means bitwise and.

I could only solve when $a=0$ by finding the most significant bit location  in $b$ and in $n$ and comparing both and find that $i$ should be $b$ or let location of most significant bit be $k$ from right then it must be $1111111.......1$ $(k-1)$ times.

But when $a \neq 0$ I am struck.  Can anybody help me?

P.S : I am finding the question and I will post it's link by tomorrow.

Here is how to reduce this to the case you already know how to solve.

If $a = b$, there is nothing to do. Otherwise, the binary expansion of $a,b$ is of the form $a = x0\alpha$ and $b = x1\beta$, where $|\alpha| = |\beta|$. If the bit of $n$ corresponding to the differing bit of $a,b$ is $0$, then the corresponding bit of $i$ should be $1$, and vice versa (more significant bits are forced to $x$).

In the first case, we are looking for a solution in the range $x10^{|\beta|}$ to $b$, which reduces to $0^{|\beta|}$ to $b$; that you already know how to solve.

In the second case, we are looking for a solution in the range $x0\alpha$ to $x01^{\alpha}$, which reduces to $\alpha$ to $1^{|\alpha|}$; that should have a solution analogous to the case you're familiar with.


Implications of Pessiland Consider 3COL (three colourability), Travelling Salesman, 3SAT and 2SAT. Which of these problems can be solved in polynomial time if we happen to live in world 3 (Pessiland).

My Thinking - We know that 2SAT is a P problem and so we can solve it in polynomial time even though we are in Pessiland however I am unsure on what the implications are for 3COL, travelling salesman and 3sat!

5 Worlds I refer to - http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html

The only world in which NP-complete problems (e.g. 3sat, 3colorability, traveling salesman)  are solvable in polynomial time is Algorithmica, i.e. $P=NP$.

The rest of them refer to various conjectures that might hold within $P\neq NP$, for example $NP$ problems are hard/easy on average, or one way functions do/don't exist.


Multiplication of polynomials in value representation as done for Fast Fourier Transform I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the  multiplication of 2 polynomials using their value representation works.
The screenshot below is from a Reducible video (at time 6:39) that explains the Fast Fourier transform. I see that we need 5 points to get $C(x)$, which is of degree $4$, but I don't see how multiplying say the first point of $A(x)$ and $B(x)$, that is, $(-2,1) \times (-2,9)$ gives $(-2,9)$
There's a similar answer here but the steps aren't provided just the final answer, which still baffles me.

If $P, Q, R \in \mathbb{R}[X], R = PQ$, then for any $x \in \mathbb{R}$, $R(x) = P(x)\times Q(x)$.
It means that if the value representation of $P$ is $[(x_1, P(x_1)); (x_2, P(x_2)); …, (x_n, P(x_n))]$ and the value representation of $Q$ is $[(x_1, Q(x_1)); (x_2, Q(x_2)); …, (x_n, Q(x_n))]$, then the value representation of $R$ is $[(x_1, P(x_1)Q(x_1)); (x_2, P(x_2)Q(x_2)); …, (x_n, P(x_n)Q(x_n))]$.
In your example, $(-2, 1)$ represents a couple $(x_i, P(x_i))$ and $(-2, 9)$ is $(x_i, Q(x_i))$, so it's normal that $(x_i, R(x_i))$ is $(-2, 1\times 9) = (-2, 9)$.


Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor The input: a binary tree and a list $L$ of vertices in that tree.
The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of minimal length it is OK to output any one of them.
We could just check all the possible sublists of $L$ but that seems inefficient.
Is there an algorithm for this problem whose running time grows polynomially with respect to the length of $L$?
One idea that doesn't work is checking for each vertex in $L$ whether removing it changes the lowest common ancestor and then simply removing the "useless" vertices. If it worked the running time would be linear.
Another idea that might work but I haven't verified in detail is to pick one vertex removing which doesn't change the lowest common ancestor, then remove it and again pick one vertex etc. This has a quadratic time.

Consider your binary tree as a binary search tree on the integers $1$ through $n$ to find that the answer for some given list $L \subseteq [1, n]$ will be $\{\min L, \max L\}$. In case you are not given a BST, you can traverse the given tree in-order to find those values in linear time (though that might be dependent on the data structure used to store $L$).


Spanning tree with chosen leaves NP-Complete proof I want to prove that the problem described here

Spanning tree with chosen leaves

is NP-Complete.

Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how would that work?

The question you link to shows that the problem can be solved in polynomial time.  If the problem was NP-complete, then this would prove that P = NP.  Of course, it's a famous open problem to prove that P = NP or P != NP.  Therefore, you shouldn't expect anyone to know of any such proof.

Also, many computer scientists expect P != NP; if they're right, then the problem you list is not NP-complete.


Constructing Noneterministic Finite Automata (NFA) with a "not" condition I have a question about some theoretical CS. Particularly, designing an NFA diagram (nondeterministic finite automata) from some conditions.

I think I understand how to construct NFA's under most simple circumstances, however, the types that I am struggling with are not conditions.

Here is one that has me really stumped:

Σ = { a, b, c }

Consider the language L:

L = { ω | ω ϵ Σ*, ω does not contain "cbac" }

I'd like to use the lambda-transition (λ-transition) to simplify this a bit. I am struggling with. How do I consider this condition?

Any help would be greatly appreciated!

First construct the DFA which accepts any string that DOES contain "abaa".  Then interchange final vs non-final!  (note: this only works with a DFA, not an NFA)  The rest you have already figured out.


What happens when an alphabet is not listed in a Turing Machine? I was given a quick lesson on Turing Machines which I found interesting. However, I came up with a problem which made me think a bit on a problem and since it's not an actual class, the answer was not given. First, let me give you some background info on a Turing Machine:

A Turing machine is a quadruple (K, sigma, small delta, s), where
  K is a finite set of states, not containing the halt stage h;
  sigma is an alphabet, containing the blank symbol #, but not containing symbols L and R;
  s is in K is the initial state;
  small delta is the rate of change.

With that info in mind, I have the following problem:

Consider the Turing machine M = (K, sigma, small delta, s), where
  K = {q0,q1} //only has two states
  sigma = {a,#} //only has a and the blank symbol
  s = q0 //will start at 10

and small delta is given by the following table.
  q      small sigma      small delta(q,small sigma)
  q0      a                 (q1,#)
  q0      #                 (h,#)
  q1      a                 (q0,a)
  q1      #                 (q0,R) //move one cell of the tape to the right

With this info and the following example, we have:

a|a|#

Let's check the first cell, it's a and we are in the initial state. If it's a, change it to #.

#|a|#

We're still on the same cell, but we changed states, q1. The alphabet is #, so let's go back to the initial state and go one cell to the Right.

The next cell has an a as well, so we change it to #. Go to state q1 and check if the alphabet is blank. It is, so we go one cell to the right.

#|#|#<we're in this cell now.

Now we go to the initial state and check if the alphabet is a, it isn't so let's check if it's blank. It is, so we halt the whole thing.

We have

#|#|#

Pretty straightforward, right? Well, I have thought of one thing. What if the tape had something that was not taken into consideration?

Something like

a|b|a|#

Would the Turing machine crash or would it ignore it?

Thank you for your time.

The behavior of the Turing machine is not defined in this case.  So, the mathematical formalism does not predict or require anything about how the machine will behave in such a circumstance.

Since a Turing machine is only a mathematical construct anyway, it's perfectly reasonable to impose such a limitation and only think about what happens when you run it on a tape that follows all the rules.

Put another way: If it's possible for the symbol b to occur in the tape, then it's your job to make sure that b is included in the alphabet.


why is $O(n^2)$ equal to $n^{1.5}$? I am learning this MIT course, which gives this formula

$$O(n^2) = n^{1.5}$$

is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ?

what x takes would have O(x) give $c \cdot n$  where c is a constant,

The formula is wrong. The notation $f = O(g)$ is asymmetric, and has the meaning $f \in O(g)$. For more, check our reference question on Landau notation. Other relevant reference questions are this one and this one.


Recursive definition of Matrix Like Linked-list for Array, is there a recursive counter-part for Matrix?

Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?

Multiple Dimensions

For a recursive counterpart for matrices, we need dependent types.

Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of columns and likewise all columns need to have the same number of rows for a matrix to be (conventionally) meaningful. I mean, for example, usually no one thinks of, say, two rows that have two different length columns as being a matrix.

A Quick Implementation

So for concatenation, we need to keep track of the lengths. We can do so by using a language that supports dependent types, such as Idris or Agda. Haskell can mimic them, but a difficult task onto itself. So here's a naive implementation in Agda.

data Matrix (A : Set) : (rows columns : ℕ) → Set where
  ∣_∣ : A → Matrix A 1 1
  _Φ_  : ∀ {r c₁ c₂} → Matrix A r c₁ → Matrix A r c₂ → Matrix A r (c₁ + c₂)
  _⊝_  : ∀ {c r₁ r₂} → Matrix A r₁ c → Matrix A r₂ c → Matrix A (r₁ + r₂) c

The first constructor embeds the type A into 1-by-1 matrices and the other two constructors are for horizontal and vertical concatenation. Notice that the natural numbers are used to keep the matrices meaningful. For example, you can stick two matrices side-by-side to produce a wider matrix precisely if the two have the same number of rows.

For example, the 2-by-2 identity matrix

id₂ : Matrix ℕ 2 2
id₂ = (∣ 1 ∣ Φ ∣ 0 ∣) ⊝
      (∣ 0 ∣ Φ ∣ 1 ∣)

Map

In one of the above comments, you remark that its troubling that we cannot pattern match and define recursive functions. Well, we can :-)

For example, the usual map of lists has a matrix counterpart.

map : ∀ {A B} (f : A → B) → ∀ {c r} → Matrix A r c → Matrix B r c
map f ∣ x ∣ = ∣ f x ∣
map f (m Φ m₁) = map f m Φ map f m₁
map f (m ⊝ m₁) = map f m ⊝ map f m₁

toString : ℕ → String
toString zero = "Zero"
toString (suc zero) = "One"
toString _ = "just no"

map-test : map toString id₂ ≡ (∣ "One"  ∣ Φ ∣ "Zero" ∣) ⊝
                              (∣ "Zero" ∣ Φ ∣ "One"  ∣)
map-test = refl

More Involved Example

As a more complicated example, let's consider matrices made by a single constant ---compare to Haskell's repeat operation that takes an element e and returns a list [e,e,...,e].

 : ∀ {A} → A → ∀{r c} → Matrix A (suc r) (suc c)
 e {0} {0} = ∣ e ∣                     -- 1x1 singleton matrix
 e {0} {c + 1} = ∣ e ∣ Φ  e             -- row-vector of length r+1
 e {r + 1} {0} = ∣ e ∣ ⊝  e             -- column vector of length r+1
 e {r + 1} {c + 1} = (∣ e ∣ Φ  e) ⊝  e -- (∣ e ∣ ⊝  e {m} {0}) Φ  e {m+1}{c}

The last one says:

                   (    e  |  e   )
 e {r+1} {c+1} =  (  ------------- )
                   (  e {r} {c+1} )

Indeed any × matrix can be construed as the vertical concatenation
of an -row vector above an (-1)× matrix ---note a recursion!
In this case, our row vector is the element e followed by an r-row vector of e's.

Example usage:

test :  5 {2} {2}
   ≡   (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣)
test = refl

Sources

Of course, the implementation was brief and just to answer your question.
A more full account can be found in the elegant lecture notes of Richard Bird.

Hope this helps!