I only skimmed the paper for 10 seconds, but AFAICS, the fundamental idea (and the reason why it is called the Hexastore) is that the relationship triple (Subject, Relationship, Object) is stored in all 6 of its permutations separately:

(Subject, Relationship, Object)
(Subject, Object, Relationship)
(Object, Relationship, Subject)
(Object, Subject, Relationship)
(Relationship, Subject, Object)
(Relationship, Object, Subject)

Now, you can ask any question you want and the answers will only require a prefix search on the index.

Want to know about any relationship between Anna and Billy? Search for (A, B) or (B, A) (order doesn't matter since both are stored). Want to know all of Anna's Friends? Search for (A, f). Want to know about all married couples? Search for (m) and throw away every odd result. And so on.

Whether you are trying to find relationships between two fixed persons, finding a person that a fixed person has a fixed relationship with, finding all pairs of persons that have a particular relationship, finding all relationships a particular person has with anybody, all of that is fast because all of that is just an index search.

The paper does not actually store all six of those in the same index, rather they use six indices. (Whereas I believe the Redis article suggests to use a single index.)


In principle, what is the relation between Artifical Intelligence and Turing machine?

Turing machines are a model of computation, one way of formally defining the concept of an algorithm. While Turing machines are usually defined using barebones input/output capabilities, it is not difficult to extend them so that they can apply to the kind of problems that AI is after.

The relation between AI and Turing machines is thus:

  Artificial intelligence is implemented by algorithms. Algorithms can be described by Turing machines.

Note, however, that Turing machines are not a great model for describing practical algorithms, since they work rather differently than actual machines, and as a consequence the complexity of algorithms is somewhat different when implemented in Turing machines compared to their real-world implementations. You should replace Turing machines with your favorite programming language.

Now I can answer your actual questions:

1) What a formal definition would relate both of them? Artificial intelligence is not a formal concept, so none.

2) Can I say that both algorithms of AI and a table of rules of a Turing machine are the same? Artificial intelligence is about algorithms performing some tasks, and Turing machines are a way of describing algorithms. So the answer to this question is positive.

3) Can I also say that AI is about choosing the best solution between different solutions to the input and Turing machine just shows a [sic] solution of the input? No, this is a false dichotomy. Algorithms implementing AI and algorithms implemented on Turing machines (with I/O) are exactly the same. There is absolutely no difference. Also, there is no such thing as a "best solution". So the answer to this question is negative.


Rice's theorem only applies for nontrivial properties, which are properties which are not always true or not always false. Your property is trivial, since it's always true.


Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X

Notations :

$b(x)$ is the beauty of $x$.
$S_c(n) = \sum_{x = 0}^{2^n-1} (b(x)+c)$ where $c\in\mathbb N$
$\tilde O(\log t)$ : polylogarithmic in $t$

Argument :

Let's first show that $S_c(n)$ is easy to calculate for any $c,n\in\mathbb N$. Each number in $[\![0, 2^{n-1}]\!]$ has at most $n$ bits, and for each $i\in[\![1, n]\!]$, exactly half of the numbers below $2^n$ have the $i$-th bit set to 1. Therefore, we can rewrite
$$\sum_{x =0}^{2^n-1} b(x) = \sum_{i = 1}^n 2^n/2 = n\cdot 2^{n-1}$$
(in 0, the result is 0). This leads to :
$$ S_c(n) = 2^{n-1}\cdot (c+2n)$$
Since $S_c(n)$ grows exponentially and is computable in $O(n)$, it takes $\tilde O(\log X)$ time to find the (unique) $n$ such that \begin{equation}S_c(n)\le X< S_c(n+1)\end{equation}

We'll note $n_0$ this $n$ for $c = 0$. One should notice that this $n_0$ is the index of the leftmost bit set to 1 in $N$
$$\sum_{x = 0}^N b(x) = \sum_{x = 0}^{2^{n_0}-1} b(x) + \sum_{x = 2^{n_0}}^N b(x)$$
Moreover, $N<2^{n+1}$, so each $x$ in the rightmost sum has $n$ bits and the leftmost bit set to 1, i.e. :
$$\sum_{x = 2^n}^N b(x) = \sum_{x = 0}^{N-2^n} b(x) + 1$$

We therefore get a recursive call : we can find the index of the leftmost bit set to 1 in $N-2^n$ by finding $n_1$ such that $S_1(n_1)\le (X- S_0(n_0)) \le S_1(n_1+1)$

This lends the following algorithm :

s(n,c) =
    if n = 0 then c
    else (2^(n-1)*(c+2*n))

smallest_n(x,c,n) = //We shall call this function with n = 0
    if s(n+1,c) > x then n
    else smallest_n(x,c,n+1)

sum_beauties_above(x,c) =
    if x = 0 then 0
    else
        let n = smallest_n(x,c,0) in
        let n' = sum_beauties_above(x - s(n,c),c+1) in
        2^n + n'
sum_beauties_above(x,0)

the first function takes $O(n)$ time, the second takes $\tilde O(\log X)$. The main function calls itself as many times as $N$ has bits set to $1$, which is bounded by $\log N\le \log X$, and each call has complexity $\tilde O(\log X)$, so we keep a polylogarithmic complexity in $X$.

However, this has been written in functionnal programming style, and is not tail-recursive, therefore, it is highly suboptimal, but this way of writing seems easier to understand, and one should take care of optimization.


What publication first introduced the concept of a non-deterministic Turing machine?

This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far.

Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the following year), but I could not find any mention of a nondeterministic two-way automaton (let alone a Turing machine) there.

The next paper (in chronological order) in which both nondeterminism and Turing machines appear is "On computability by certain classes of restricted Turing machines" by Fischer, 1963. In it, he defines general machines and also allow them to be nondeterministic. However, in the proof of Theorem 5 there he curiously states that some results (regarding deterministic and nondeterministic machines) are "well-known" to be equivalent for Turing machines. Hence, one is lead to believe the notion must have arisen sometime between the Rabin and Scott paper and Fischer's paper in 1963. Fortunately, Fischer gives a clue as to where he has those results from:

  The author is indebted to Dr. J. Evey for many of the ideas contained herein. He has worked closely with the author in this area and, in particular, is responsible for the results constituting parts (c) and (d)
  of Theorem 3 and for the main construction in part (e).

Theorem 3 in case is the computational equivalence of DTMs and NTMs.

Indeed, roughly a month after Fischer's paper Evey published "Application of pushdown-store machines," in which we also find nondeterminism applied to general machines (including Turing machines), and in which he proves the result that Fischer mentions (and extending it to some other types of machines). Fischer's work is actually listed in the bibliography there as well, but as far as I can tell there is no explicit citation of it in the text. The paper is most likely a summary of Evey's doctoral thesis (similarly titled), but I could not find it online; maybe someone with access to it can confirm that.

What I conclude then is that, unless I have made a gross oversight somewhere, the notion of an NTM must have just been evident to the research community once Rabin and Scott had brought nondeterminism to the table. Evey deserves credit for proving the computational equivalence of DTMs and NTMs, but it is hard to tell from the evidence at hand if he was the first to mention NTMs as a concept too (possibly in his doctoral thesis).


Is there an algorithm to detect race conditions in logic circuits?

However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

There are two different problems here. The simple solution (the one you should implement, in my opinion) is to simply look at the connection graph of the gates, and detect if the graph contains any cycles. If yes, simply reject the input.

The problem logisim refers to, which would amount to solving the halting problem, is one where you allow cycles, but reject sequential circuits.

This is different, because not every cycle in the graph affects the output, or worse, it affects the output but not in an sequential way.

  However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

Initially I disagreed, but after some more thinking, I agree. Do note that we have infinite time here - we can supply infinite sequences of inputs to the circuit in an attempt to get sequential behavior.

Under the condition that we always let a circuit stabilize before changing the inputs (or rejecting the circuit as sequential in case it never stabilizes), a finite circuit is a finite state machine. The crux is that the output of the circuit depends on the input plus the internal state of every gate in the circuit.

To prove that a circuit is non-sequential you can use the following algorithm:

Add the all-zero internal state to a queue.
While the queue is not empty, pop an internal state from the queue and construct the truth table for all inputs using that initial internal state. Also add the internal state to some set tracking internal states we have handled. For each internal state reached from this internal state while computing the truth table, add it to the queue if it's not inside our handled set.
If at any point in 2 a circuit does not stabilize, return sequential. If at any point during 2 the generated truth table does not equate the one from the all-zero internal state, return sequential. Otherwise return non-sequential.

Since there are a finite amount of possible internal states, this algorithm always terminates. And it fully explores all reachable states. Nevertheless, this algorithm is very, very much infeasible.


"Inhabited" is the properly constructive notion of "non-empty". The idea is that to demonstrate that a type is inhabited requires exhibiting a particular construction with that type, while 'non-empty' means merely demonstrating that it is impossible to demonstrate that there are no such constructions.
"Uninhabited" is the negation of this, and so is equivalent to being empty, even constructively.
Haskell does not have an uninhabited type. For instance undefined is a valid term of every type. C, Java and any language with general recursion is not going to qualify either, although C and Java have many other problems even being considered analogues of formal logic. Python doesn't even have types in the type theoretic sense (or it has a single type that classifies everything trivially).
The reason why void does not really qualify is that it is not a 'type with no values', but a type where you disallowed from naming/manipulating values, because those values would be trivial. It is analogous to the unit type, with one featureless value.


Is every regular/context free langauge decidable in LogSpace?

For regular languages, we have
    $$ \text{REG = DSPACE}(O(1)) = \text{NSPACE}(O(1))$$
where REG is the class of regular languages. This can be easily seen from the equivalent formalisms of regular languages. A language is a regular language iff it is the language accepted by a deterministic finite automaton. A language is a regular language iff it is the language accepted by a nondeterministic finite automaton.

In fact, $\text{REG = DSPACE}(o(\log \log n))$. That is, $Ω(\log\log n)$ space is required to recognize any non-regular language [1].

For context-free languages, please see the answer by Yuval Filmus.


If the strings of a language can be enumerated in lexicographic order, is it recursive?

Lexicographic order is not such a good order since its order type is not $\omega$. Instead of explaining formally what that means, let me give an example. Consider the language $(a+b)^*$. If you enumerate the words in lexicographic order, you get
$$
\epsilon, a, aa, aaa, \ldots, ab, \ldots
$$
The first $\ldots$ signify infinitely many terms. So it isn't really clear what it means to enumerate a language in lexicographic order. There could be two interpretations: either the language $L$ doesn't suffer from this problem, or you really mean a slightly different order. Since the precise answer doesn't matter for all that follows, we will just assume that you can effectively enumerate $L$ in some (effective) order whose order type is $\omega$ (i.e., when the problem above doesn't happen).

The proof that $L$ is recursive can be a bit subtle, due to a certain ambiguity: what happens if $L$ is a finite language? There are two reasonable interpretations of effective enumerability in this case: either the enumerator will eventually halt, or it won't, but at some point would stop outputting strings. Fortunately, this ambiguity doesn't affect the proof.

For the proof that $L$ is recursive, we consider two cases. If $L$ is finite, then it is trivially recursive. If $L$ is infinite, then to decide whether $x \in L$ and wait until either $x$ is output, or a string larger than $x$ is output (if $x \notin L$ then this will happen eventually since $L$ is infinite). In the first case $x \in L$, in the second $x \notin L$.

To see that $L$ is not necessarily context-free, you can consider your favorite non-context-free language $\{c^nb^na^n : n \geq 0\}$ which is effectively enumerable in (plain vanilla) lexicographic order.


You are correct in your understanding of the construction: For every transition arrow, say from state $A$ to state $B$ in the GNFA labeled by a regular expression $R$, you replace that transition by the NFA, $N$, for $R$, with an $\epsilon$-transition from $A$ to the start state of $N$ and $\epsilon$-transitions from the final states of $N$ (which you then "un-finalize") to state $B$. Do this for every transition in the GNFA and you'll wind up with an ordinary NFA.

To show that the two accept the same language, it's enough to rely on the previous result (Lemma 1.55 in Sipser) that any regular expression denotes a language that is recognized by a NFA.


An iterative algorithm for finding the partitions of a set into subsets of a fixed size

Let's first describe a notation for our partitions. Let $p_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p_i$ as  $$p_i=b_{i,1},b_{i,2},...b_{i,S/2}$$

In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p_i$, each pair in $p_i$ must be sorted. The pairs must also be sorted among themselves i.e.

$$b_{i,j}[0] < b_{i,j}[1]  \;\;\text{and} \;\; b_{i,j} < b_{i,j+1} \;\;\forall j$$

The ordering of the partitions is then defined similarly to other lexicographic orderings.

$$p_i > p_{k} \iff \exists j \;\; \text{s.t.}\;\; \forall j'\in[1, j) \;\;  b_{i,j}=b_{k,j} \land  b_{i,j'}>b_{k,j'}$$

Now, given some partition $p_i$, we can return the next lexicographically larger partition $p_{i+1}$ by using logic similar to the algorithm for obtaining the next permutation of a set of elements. Let us first describe a function $swap(p_i, j)$ and $sort(p_i, j)$.

$swap(p_i) \rightarrow \;\;$ Find the largest $j$ such that there exists a larger element in any of the pairs $b_{i,j'}$ for $j'>j$. Let $x$ be the smallest such element i.e. $x = \min(\{x'\in b_{i,j'} | j' > j \land x' > b_{i,j}[1]\}).$

Then swap $b_{i,j}[1]$ and $x$ and return $j$.

$sort(p_i, j) \rightarrow \;\;$ Sort all of the elements from $b_{i,j}[0]$ to $b_{i,S/2}[1]$ i.e. after calling $sort(p_i, j)$, the sequence $b_{i,j}[0], b_{i,j}[1], ..., b_{i,S/2}[0],b_{i,S/2}[1]$ should be non-decreasing.

Now, we claim that given a partition $p_i$, we can obtain $p_{i+1}$ by running $sort(p_i, swap(p_i)+1)$. The reasoning is identical to that of the "next permutation algorithm" - We must find the largest $j$ such that we can swap $b_{i,j}[1]$ with the next largest value while not changing anything in $b_{i,j'}$ for $j' < j$. After the swap, we must sort the remaining elements to ensure that it is the smallest increase possible. If the remaining elements were not sorted, then by sorting them we would obtain a partition greater than $p_i$ but less than $p_{i+1}$, which is a contradiction.


Why does NTIME consider the length of the longest computation?

Because you don't know ahead of time whether or not any given input is a 'yes' instance — that is, whether there exists any accepting path — it makes sense for the sake of uniformity to bound the run-time independently of any particular feature of the computational paths. Thus, it makes sense to require the worst-case behaviour to be polynomial time, regardless of whether or not any accepting paths exist.


"Note on fast polylogarithm computation" by R. E. Crandall contains an explicit algorithm for computing the polylogarithm.


Is there a method to compress all data without loss (lossless compression)?

There are $2^n$ bitstrings of length $n$, but only $2^n-1$ bitstrings of length smaller than $n$. Hence there is no one-to-one mapping which maps every bitstring of length $n$ to a bitstring of strictly smaller length. In other words, for any (lossless) compression scheme there will always be a string which it doesn't compress.


How are words assigned in machine language?

LDA gets translated by the assembler to bytes that the machine can interpret.

The contents of these bytes are set by the instruction decoder, and often made to make the decoder as simple as possible. For example some bits may get passed straight to the execution unit so add and subtract differ by a single bit which triggers inverting the second operand and sets the carry in bit. The bits that decide which registers to use would be common to all instructions, stuff like that

The 3 letter acronyms are just shorthands set by whoever was in charge of writing the assembler.


How to draw a graph to disprove this statement?

You have made a mistake interpreting the wording of the question compared to the Stackoverflow question (link in case of later editing).

Notice that in options (a) and (b), the phrasing is a minimum weight edge, whereas in the Stackoverflow question the phrasing is the minimum weight edge. In your question, there's no guarantee that the edge is the only edge with that weight, in the Stackoverflow question, there is exactly one edge with the lowest weight.

Thus the mistake is assuming that (b) is true, when in fact it is false. The two true options are (a) and (c), which is why you can't find a counter example to (c).

In both (a) and (c) however, the proof is very similar to that in the Stackoverflow question. In fact (c) is given by applying that proof inductively. (a) is given by basically the same argument, but you show that the tree made by adding the given edge and removing some other edge from the cycle can't have higher weight (because the new edge has minimum weight).

To see that (b) is false, just take the graph $K_{n}$ where all edge weights are the same. Any spanning tree is a minimum spanning tree.

For (d), consider the following graph; take a tree on $n$ vertices, give all these edges weight $1$. Then add all non-edges, give these new edges weight $2$.  Clearly there's only one MST, but there's $\binom{n}{2} - n + 1$ edges with the same weight.


The essential difference between spiking neural networks and earlier generation ANN's

Yeah; each neuron in the spiking network integrates its input, instead of just summing the input of the previous timestep as in the old analog model.


Upper Bound on Runtime of Memoized DP Algorithms

A general trick that works for a lot of DP problems is to look at the parameters in your recursion -- the run time is then $O(n \times max(parameter_1) \times \dots \times max(parameter_k))$ where $n$ is the number of iterations (or, the number of inputs).

Consider for example a DP to solve the subset sum -- the recursion is given by $Q(i,s) := MIN(Q(i − 1,s), Q(i − 1,s − x_i)) $ where $0 \leq s \leq T$ and $T$ is the target sum.

The run time is then $O(n \times max(s)) = O(nT)$. And of course, this trick works with memoization only. If you have not done memoization, it is truly exponential (not pseudo-polynomial).

Why does this work? In each iteration $i$, we have to look at at-most $T$ different sub-problems (post memoization) before we hit the base case.


Your problem is known as group testing. An essentially optimal algorithm for your problem is Generalized binary splitting. There are also pretty good non-adaptive algorithms (such algorithms fix all queries ahead of time).


Prove the Droid Trader Problem is NP-complete

You can find a simple reduction from Knapsack or from the Partition Problem (which itself reduces to Knapsack).

Let's do it from the Partition Problem:

  Given $n$ integers $S = \{a_1, a_2\ldots, a_n\}$ with even total sum, does there exist a subset whose sum is exactly half the sum of all elements ?

So suppose you are given an instance of the Partition Problem. We construct an instance of the Droid Trader problem as follows:

There will be $n$ types of droids, one for each integer in $S$. There will be two planets $s$ and $t$, with a directed edge from $s$ to $t$.
On planet $s$, the player can buy a single droid of each type $i$ for a price of $a_i$, and can sell nothing.
On planet $t$, the player can sell droids of every type $i$ for a price of $2\cdot a_i$, and can buy nothing.
The player starts with $z$ equal to half the sum of all elements in $S$.

Then, it is easy to see that, the player can never end up with more money than $\sum S$. Moreover, he can achieve $\sum S$ if and only if he can buy $\frac{1}{2}\sum S$ worth of droids on the first planet, i.e. there exists a subset of $S$ with sum $\frac{1}{2}\sum S$.

So the original question on the Partition Problem instance is equivalent to asking if the player can end up with $\sum S$ money in the corresponding Droid Trader problem.

Because this is a polynomial time reduction, this proves the claim.


Is there a meta text processing concept in CS?

You should look into Theory of Automata, Languages and Computation:
These are the theoretical foundations of scanning, parsing and processing text (and furthermore constructing formal languages and grammars).

Components of the theory, are, for example:

Pushdown automaton
Context free grammars
Parsing techniques such as recursive decent, LL or SLR parsing.

Classical introductory textbook on this subject is "Introduction To Automata Theory, Languages, and Computation" by John E. Hopcroft,Rajeev Motwani and Jeffrey D.Ullman.


Decidable languages and unrestricted grammars?

A language is decidable, iff it is semi-decidable and its complement is semi-decidable. Moreover, a language is recursive-enumerable iff it is semi-decidable and thus you can find an unrestricted Grammar. Therfore:

A language $L$ is decidable iff there is both an unrestricted Grammar $G$ with $L(G) = L$ and an unrestricted Grammar $\bar G$ with $L(\bar G) = \bar L$.


Time complexity of this solution to N-queens problem

Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an upper bound, but it is an upper bound that vastly overestimates the effort needed.


How to restore diagonal-symmetric matrix that has been shuffled?

First, note that the matrix can only be restored up to a permutation of the diagonal.
To illustrate on your example, when we swap two bottom rows and two left columns, the resulting matrix is also diagonal-symmetric:

133 199 101 121                             199 133 101 121
142 133 199 101        transforms to        133 142 199 101
156 142 133 199                             156 108 142 133
108 156 142 133                             142 156 133 199

So, the good news is, instead of searching for a row permutation and a column permutation, we can fix the order of the rows and permute only columns.
Indeed, if we took the original matrix and permuted the rows in any fixed order,
by permuting the columns in the exact same order, we get a diagonal-symmetric matrix.

Next, note that, before the permutations, the multiset of numbers in row $1$ was exactly the same as the multiset of numbers in column $1$.
The same holds for row $2$ and column $2$, and so on.

After permutations, say row $1$ landed at row $i$, and column $1$ landed at column $j$.
Then, the multiset of numbers at row $i$ is still the same as the multiset of numbers at column $j$.

Importantly, the problem seems to be about some large and more-or-less real data, so it is likely that the converse also holds: for any two rows, the multisets of numbers in them are different.
If not, perhaps what follows can be tricked to fail by constructing the appropriate data.
Anyway, the check is straightforward.

Having noted the above, I propose the following simple algorithm:

Write down the multiset of numbers $S_1$ in the bottom row.
(A sorted array will suffice for storage and comparison.)
Search for the column which contains the exact same multiset of numbers $S_1$.
Swap this column with the leftmost one.
Proceed with the next-to-bottom row and find its multiset $S_2$.
Search for the column except the first one which contains the exact same multiset of numbers $S_2$.
Swap this column with the second-to-leftmost one.
Et cetera.

The algorithm can run in $O (n^2 \log n + n^2)$, with some hashing.
First, for each of the $n$ rows and each of the $n$ columns, calculate a hash of the multiset of numbers in it (for example, make a sorted array in $O (n \log n)$ and get its polynomial hash).
Then, we can consider hashes instead of the rows and columns of the real matrix.
After we find the needed permutation of rows, apply it once in $O (n^2)$.


Grover's Algorithm result when the desired element is not present

When it is absent, it will just output one arbitrary state.

As it is not the desired element, you may repeat the search algorithm again (even in the case it was present, you could have measured another computational basis – the algorithm uses probability after all so that's why it may be necessary to repeat) and you will finally conclude that it is not present.

The inversion about average operator changes the amplitudes of the states $\alpha_i$ to
$$ - \alpha_i + 2 \langle\alpha\rangle\,, $$
where the last term is the average of the amplitudes. You see in the case of no marking, it has no effect, so all computational bases will have the same probability of being measured.

You can check the explanation in Nielsen and Chuang's book.


"Programming computers to learn from experience should eventually eliminate the need for much of this detailed programming effort"
Samuel, A. L. (1959), “Some Studies in Machine Learning Using the Game of Checkers” in IBM Journal of Research and Development  (Volume:3, Issue: 3), p. 210


Termination of Z combinator with call-by-value

I don't think you're doing the reduction wrong, but the problem isn't the Z combinator. The problem is $\text{iszero}$. Branching constructs in call-by-value cannot just take the direct terms for each branch as arguments like they can in call-by-name (or similar), because both branches will be evaluated regardless of the test. This clearly interacts poorly with recursion, but it's also undesirable in general.

Instead, branching constructs in call-by-value should take explicitly delayed arguments. So something like: $$\text{iszero}\ n\ (λ\_. 1) (λ\_. \text{mul}\ n\ (f\ (\text{pred}\ n))$$ this way the recursive evaluation can be avoided unless it is actually necessary. You could, of course, leave $\text{iszero}$ as is, always use it this way, and provide an extra argument yourself, but I think normally it would be defined to expect delayed arguments.


My view is that vernacular would consider that S is not empty,
i.e. $\emptyset \neq S\subseteq T$, while mathematical language would
consider that S can be empty, i.e. $\emptyset\subseteq S\subseteq T$.

Lay people do not speak of empty sets, while mathematicians are
aware of their role in their work.

That means that the sentence is not ambiguous, but the meaning depends
on the community where it is used.

Of couse, people aware of the two readings can play games with it. But
that is yet something else.

You may notice that I did not specifically mention English, because
the same is probably true of many "languages".

To think that English  (or German, or French) is a well defined language is
unrealistic. Actually, I doubt you can find two people who
agree on what is English and the meaning, or on the ambiguity, of its sentences,

It might be interesting to ask the linguists.


How to design a Turing Enumerator which either ends with 011 or is of odd length?

I'm assuming you're looking for a Turing machine that decides the language $L$ consisting of all words ending with 011 or of odd length.

Hint: You're lucky since $L$ is regular. Construct a DFA for $L$ and rephrase it as a Turing machine.


The space complexity of recognising Watson-Crick palindromes

Disclaimer: The following algorithm does not use the standard model for sublinear space complexity (see WP:DSPACE), because it writes to the input tape. Furthermore the set of (Watson-Crick) palindromes is not in $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$. Nevertheless, it's an in-place solution for many practical purposes (e.g. if each letter is a char in C).

To show that a problem has a specific space complexity, one generally needs to come up with an algorithm that has that space complexity. This may require trial and error, but a better approach is to have a good understanding of the problem you are looking at and a good amount of experience in algorithms and complexity.

For this particular example, there is a third algorithm that does not need any additional space and requires $O(n^2)$ time complexity. This algorithm would be constant space.

Hint: why use additional space, when you can use the space occupied by the input?

Hint: zip back-and-forth across the string checking one character at a time – use the state of the Turing Machine to remember which character you are checking and erase characters you've already checked.


Simplification of regular expression and conversion into finite automata

At the point of writing, your NFA is still a bit off. One version of a correct answer looks like this:

So this NFA is design in an ad hoc manner, but there's still some basic organisation to it. You can see that there's three basic bits, the $a,b$ loop on the start state, a forced $ab|ba$, followed by two 2-step loops, then a forced $a$ to the final state, with an $a$ loop. The first loop takes care of the $(a+b)^{\ast}$, the next little clump does the $(ab+ba)^{+}$, then the tail end does the $a^{+}$.

The key thing to practice when doing things this way is breaking the RE down into a sequence of smaller REs, that you then stick together. This is essentially a 'casual' version of the systematic method.

The systematic way is simple, but a bit fiddly. It's a relatively long explanation as to how to do it systematically, and as you haven't reached that bit in your reading yet, I'll refrain from working through the details here, however just as a quick reference, this explanation is pretty thorough and reasonably well explained.


How to generate random adjacency matrix with given number of components in graph

What you need is to take advantage of disjoint set, a very efficient data structure.

Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component.

MakeSet of size $n$.
Choose two random vertices that has not been connected by an edge.
Union these two vertices. That means adding the edge between them. Use an implementation of the union operation that tells you if two different components are unioned.
Stop if the number of components become $m$. Go back to step 2 otherwise.

There are existing implementations of disjoint set in C/C++, Java, Python, or just about every popular language.

You can implement step 2 in various ways.

You can use rejection sampling. Choose two random vertices. Repeat if the edge between them has been added.

This method is about the simplest to implement. It is efficient when the number of components is greater than a fixed proportion of the number of vertices. It takes little time if the number of vertices is not large.
You can also keep track of the degree of each vertex. Choose a vertex whose degree is not $n-1$. The choose an edge from that vertex.

You can vary step 3 as well. Step 3 above is aimed to produce a random graph with given number of components and the "minimal" number of edges.

One way to get random number of edges is to continue adding some random number of random edges after step 3 as long as no two different components become unioned/connected.
One way to get denser graphs is to not add the edge when it connects two different component with some probability $p$. The larger $p$ is, the more edges.

In the special case of one component (connected graph) and many vertices, you can also generate a random tree using Prüfer sequence, followed by adding some random edges.

As you have mentioned, you could also generate $m$ random connected graphs with given numbers of vertices, the joining them together. Each connected graph can be generated using either disjoint set or Prüfer sequence.

Note that for all above variations, the distribution of the generated graphs is probably different from each other. It is your task to choose an implementation whose randomness/biasness is what you want. Or roughly.


$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc.

This serves, for instance, to distinguish between $\{ \langle M \rangle \mid \text{$M$ is a TM} \}$, which contains encodings of TMs (e.g., their Gödel numbers or representations in binary), and $\{ M \mid \text{$M$ is a TM} \}$, which is the set of Turing machines themselves (as mathematical objects). The underlying motivation is that it is not clear how a TM (as an object) can be passed as an input; what you do is provide its "program", that is, its states and transition function.

When multiple objects are encoded together as a single string (i.e., to be seen as a single object), it is usual practice to denote it as $\langle x_1, \ldots, x_m \rangle$. Again, it is not immediate what the encoding is. It could be simply concatenating the encodings of each $x_i$ and separating them (e.g., $\langle x_1, \ldots, x_m \rangle = \langle x_1 \rangle \# \cdots \# \langle x_m \rangle$); it could also be that the encoding of $x_i$ is altered in some way (e.g., each $0$ or $1$ in $\langle x_i \rangle$ is doubled and each such representation is separated by $01$); it could even be that the entirety of the representation is compressed (so as to reduce its length) or that it is subject to some predetermined enumeration (e.g., as a vector over some countable space).

Generally, if they are relevant to the context at all, these descriptions should be made precise beforehand, as most textbooks do. In computability theory, except when covering Gödelization, they usually are not; this is because the actual length of the input is irrelevant to computability questions. Things are different in complexity theory—though it usually does not get much attention there either (besides coming up in a preface or similar); most objects are encoded in binary anyway, and multiple objects with only a constant stretch, which suffices for almost all complexity-theoretical topics.


If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).

In general, you compute the LL(1) parse table and use it to answer the question. Your grammar is LL(1) if each cell in the table has at most 1 grammar rule. In other words, at least one table entry has more than 1 rule implies that your grammar is not in LL(1): http://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL.281.29_parsing_table


TSP when cost depends only on location in sequence

Your problem is the same as minimum-weight perfect matching in a bipartite graph. If there are $n$ cities, consider the bipartite graph in which one side consists of vertices $p_1,\ldots,p_n$, the other side consists of vertices $c_1,\ldots,c_n$, and the weight of the edge $(p_i,x_j)$ is the cost of city $j$ at position $i$.

A minimum-weight perfect matching in a bipartite graph can be found efficiently (this is known as the assignment problem). In particular, the problem is not NP-hard unless P=NP.


What is the explicit definition about the computablity of non-deterministic Turing machine?

One should not confuse function problems like FNP and FP with the different types of functions computable by deterministic, non-deterministic, alternating, probabilistic, or ... Turing machines.

Instead of starting by looking at functions $f:\Sigma^* \to \Sigma^*$, it is easier to start by looking at functions $f:\Sigma^* \to \mathcal{P}(\Sigma^*)$. A function $f:X\to\mathcal{P}(Y)$ is equivalent with to a subset $R\subset X\times Y$ of the cartesian product of $X$ and $Y$, i.e. to a binary relation.

Since we can assume that the decision problem is already defined, using the decision problem for $R$ gives one reasonable definition for the computable functions (of this form). However, that definition would force the different Turing machines to compute each output-bit separately and independently, which is a small speed penalty. One can allow the different machines to produce the output in a way more suitable to their capabilities, to avoid that penalty.

The more annoying problem is that the form of output is different from the form of input. One could combine that with a stupid translation function $g:S\to \Sigma^*$ for $S\subset \mathcal{P}(\Sigma^*)$ to bring the output into the same form as the input. But if the output was produced in a way more suitable to the different capabilities of the Turing machines, such a stupid translation function might need to be more powerful than desired. Even accepting the small speed penalty would not allow to avoid that problem, since the functions computable by the different Turing machines are often not closed under composition. That problem might be partly solved by using monads (and accepting $\mathcal{P}(\Sigma^*)$ as the form of output), but then the fact that functions computable by deterministic or alternating Turing machines were actually closed under composition gets hidden.


Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time

You should look into R-Trees.

  R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

The parts that apply the most to your case are the ones described on the Search subsection. This operation on this kind of trees have a complexity of   O(logMn):

  In range searching, the input is a search rectangle (Query box). [...] the elements are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

Good luck!


Deciding Recursive/Recursively Enumerable when given Turning machine encoding as a language

As you note, both languages are undecidable, so neither are recursive. Then the remaining possiblities are recursively enumerable or not.

Note that $L_{1} = \overline{L_{2}}$, so if they were both recursively enumerable, then they would both be recursive, so we know at least one is not even recursively enumerable.

It turns out that $L_{1}$ is recursively enumerable, given an input $\langle M\rangle$ we can simulate $M$ on all strings over the alphabet by interleaving the execution of $M$ on each string. It may take a long time, but if $M$ accepts something, we eventually (in finite time) find it, so we can recognise that $\langle M\rangle \in L_{1}$.

Then simply by logical deduction, $L_{2}$ can't be recursively enumerable, as it is already co-r.e., but not recursive.


If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$?

When we say "Simulate $M_A$ on the query string $s$", we simply mean execute $M_A(s)$. Note that you construct a non-deterministic machine for $L$, thus you are able to simulate other non-deterministic machines. If both $M_A(s)$ and $M_{\overline{A}}(s)$ output $0$, then stop and reject $x$ (the initial input). Only when one of the machines outputs $1$, you can be sure about whether or not $s\in A$, and can continue simulating the oracle machine for $L$.

Note that this newly constructed non-deterministic polynomial time machine, $M(x)$, may accept its input $x$ only in computations where for each query $s$ raised during the computation, either $M_A(s)$ or $M_{\overline{A}}(s)$ output 1. Using this observation, you can simply show that $M$ indeed decides $L$.


Scan the entire array to check each cell to see whether it is a local minimum.

There's no algorithm that is asymptotically better; this is optimal to within a constant factor.  (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum.  So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)


Why do most scientists believe that P≠NP?

An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving any NP-complete problem $X$ quickly, you can take any other NP-complete problem, transform it into an instance of $X$, and solve that quickly as well.

Several smart researches have spent a lot of time on researching these hard problems. Despite all the efforts and years, we still don't have a polynomial time algorithm for any of the NP-complete problems. We also have conditional results of the form "if you can do this faster/better, then P=NP".

As for proving the claim, we don't perhaps know much for sure. What we do know is that whatever the proof looks like, it can't be of a certain type. So at least if there ever was a proof, it will have to address how it avoids some known difficulties.

For more details, you could first have a look at Sipser's book, and then the Arora-Barak book.


When are binary trees better than hashtables in real world applications?

Hash tables can only tell you if an element is present or not.

Here are somethings you can do with a binary tree that you can't do wiht a hash table.

sorted traversal of the tree
find the next closest element
find all elements less than or greater than a certain value

See this wikipedia article on K-d trees for an example of a real world data structure that makes use of the special properties of binary trees.
http://en.wikipedia.org/wiki/K-d_tree


Define a DFA that accepts all even length binary strings that don't contain the substring "111"?

Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$.
and so on...

Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$, and you've read odd number of letters ($\epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$, and you've read odd number of letters.

And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states

Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.


How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

Here is the idea. We can always write the string in the form $w_1\#\cdots\#w_n$, for some strings $w_i \in \{0,1\}^*$. If the input string is not of the form $b_1\#\cdots\#b_n$, then one of the following must happen:

$w_1 \neq 1$.
One of the $w_i$'s is empty.
One of the $w_i$'s has a leading $0$.
For some $i$, $w_i+1 \neq w_{i+1}$.

The first three cases are easy. In the first case, the string is empty or starts with $\#,0,10,11$. In the second case, there is a substring $\#\#$. In the third case, there is a substring $\#0$.

For the fourth case, let $x = w_i$ and $y = w_{i+1}$. Here are some things which are not supposed to happen:

$x$ ends with $1^m$ and $y$ ends with $10^{m-1}$.
$x$ ends with $01^m$ and $y$ ends with $0^{m+1}$.
$x = 1^m$ and $y = 0^m$. (Actually this is ruled out by requiring no leading zeroes.)
$x$ starts $\{0,1\}^ib\{0,1\}^*0$ and $y$ starts $\{0,1\}^i \overline{b}$.

Unless I missed some case, if none of these things happen, then $y$ is the encoding of $x+1$. Indeed, the first two constraints guarantee that if $x=z01^m$ then $y=w10^m$ (the third constraint takes care of the corner case $x=1^m$, in which case $y=10^m$), and the fourth constraint guarantees that $z=w$.

Each of these subcases corresponds to a context-free language – once again, there are some corner cases to consider (if $x = w_1$ and if $y = w_n$).


Proving a language is not decideable using a reduction from Busy Beaver?

Hint: Why is the busy beaver function difficult (rather, impossible) to compute? Consider the following algorithm: given $n$, run all $n$-state Turing machines, and whenever one of them halts, update your estimate on the maximum number of steps. Eventually you will have found $BB(n)$, but you wouldn't know, since some of your machines are still running. Will any of them terminate, or have you discovered $BB(n)$? The function $F(n)$ given to you in the question could help in that respect.


Context free grammer for $L = \{a^i b^j a^n b^m \mid i + j = n + m\}$

The idea is to use non-terminals $X_{\alpha\beta}$, where $\alpha,\beta \in \{a,b\}$, that support the production $X_{\alpha\beta} \to \alpha X_{\alpha\beta} \beta$. You have to combine them somehow so that you obtain the language $L$, but I'll leave the details to you.


Proof of the undecidability of the Halting Problem

Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) and anything at all for $b$, $H(a, b)$ acts as follows

If the program represented by $a$ halts when given $b$ as input, $H(a, b)$ will answer "yes". On the other hand, if the program described by $a$ runs forever when given input $b$ then $H(a, b)$ will answer "no".
Importantly, program $H$ will always halt and give the correct answer for any pairs $(a, b)$.

The argument that $H$ is impossible to build relies on the action of a particular "perverse" program, $P$, one which uses $H$ as a subroutine. $P$ takes as its input a listing of any program, $x$, and does the following:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

It's not hard to see that

  $P(x)$ will halt if and only if the program $x$ will run forever when given its own description as an input.

So far so good: $P$ will certainly be a program as long as its subroutine $H$ is a program.

Now return to the picture. What happens if $P$ is given its own description as input? The picture describes just that scenario: Let $p$ be the description of program $P$, then, substituting into the highlighted part above, we'll have

  $P(p)$ will halt if and only if the program $P(p)$ will run forever.

Clearly, this paradoxical behavior is impossible, so we're forced to the conclusion that the subroutine $H$ cannot be a halt tester, since it fails in the one case, where it's given $(p, p)$ as input. There might be other cases where $H$ works as it should, but since $H$ fails in at least one situation, it cannot be a complete halt tester, as required.


Relationship between depth and the vertical displacement of the object between two frames

Yes.  This all comes down to some simple trigonometry.  An object that is at horizontal distance $x$ and vertical distance $y$ from the camera's viewing direction will be at angle $\tan^{-1} (y/x)$ from the viewing direction, and the distance to the object will be the length of the hypotenuse, i.e., $\sqrt{x^2+y^2}$ (draw a picture).

So, if the object starts at height $y_1$ and then moves upward to height $y_2$, the distance to the object will increase from $\sqrt{x^2+y_1^2}$ to  $\sqrt{x^2+y_2^2}$.  Now you can compute the absolute or relative change in the distance to the object, if you know $x,y_1,y_2$.  For instance, if you know the distance to the object originally and the original angle $\theta_1$ from the camera's viewing direction, you can compute $x,y_1$; if you know how much it moved upward, you can compute $y_2$; and that will let you compute the new distance.


Assigning $m$ balls to $n$ buckets - recursive algorithm

An assignment of balls into $n$ bins falls into either one of the following two cases.

Every bin has as last one ball. So let us assign one ball to each bin first. What remains to do is to assign the remaining balls to the bins.
Otherwise. That is, there is at least one bin that has no ball. This case is the same as assigning all balls into $n-1$ bins.

Exercise. Verify that we are counting without duplicates and without missing assignment.


Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin

For the set $\{K_i \mid 1 \leq i \leq n\}$ to form a partition of $B^*$, it is necessary, that all $K_i$ are pairwise disjoint and every element in $B^*$ is cointained in some $K_i$. You already showed that they are disjoint, as is is possible to split two overlapping $K_i$ into three disjoint ones by using the parts that don't overlap and the intersection instead. The second condition, that everything is contained, is achieved by adding $(B^* \setminus \bigcup_i K_i)$ to the set $\{K_i \mid 1 \leq i \leq n\}$ so $n$ is incresed by one and still is finite. And this $(B^* \setminus \bigcup_i K_i)$ contains everything that was not previously contained.

As $\{K_i \mid 1 \leq i \leq n\}$ forms a partition, everything in $B^*$ is contained in some $K_i$ and is, therefore, also contained in the complement of another one, which means, it doesn't change anything to use the complement of the $K_i$s.


what is variable capture in nominal logic?

Variable capture is the phenomenon which "breaks" things when you do your substitutions in a naive way. For example:

Correct: in the expression $$\int_0^1 (a + x)^2 dx$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + x)^2 dx.$$
Correct: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + u)^2 du$$ (we renamed the bound variable $t$ to $u$ on the fly to avoid capturing $t$).
Incorrect: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + t)^2 dt.$$ (We ended up with a different intergral because $t$ was captured by $dt$).

Similarly, in $\lambda$-calculus:

Correct: $(\lambda x . \lambda y . y x)) y = \lambda z . z y$
Incorrect: $(\lambda x . \lambda y . y x)) y = \lambda y . y y$   (because $y$ was captured).


Are cache contents specific to a process?

It depends, there are several kinds of caches.

Some caches, known as PIPT (physically indexed, physically tagged) operate entirely on the physical address. The cache subsystem is independent of virtual memory, so it doesn't matter which process is accessing the cache: all processes share all cache entries.

Some caches, known as VIVT (virtually indexed, virtually tagged) operate entirely on the virtual address. In this system, a cache entry is only valid for a given process. There are several ways to ensure that a cache entry will not be used in the wrong process:

The operating system may flush the cache at each context switch. This requires no hardware support but is obviously inefficient unless context switches are rare.
The operating system may assign disjoint sets of addresses to distinct processes. This again requires no hardware support, but is a heavy burden on the operating system (it means that the MMU is effectively as a mere MPU (memory protection unit)).
The MMU and cache may contain an extra label which is set by the operating system to an identifier for the process that owns each page or cache entry. ARM and Intel call this label ASID (address space ID). Each cache entry is only valid for a virtual address with the matching label.
There are also VIPT caches (virtually indexed, physically tagged). The physical tagging ensures that the cache entry will only be served to a request for the correct chunk of memory. The virtual index means that if a page is shared at different addresses in different processes, the cache entries will not be shared.

See the “Address translation” section in the Wikipedia article for more information on these kinds of caches.

Cache types typically vary between processor families within the same processor architecture. Even on a given processor, data and instructions caches may have different types, as can L1 vs L2 (and more) caches.


Add type checking/inference to my programming language

You could start with the simple cases of Swift. Literals have type “Literal”, for example, and known variables have their known types. When you evaluate an expression you may know what type you want and evaluate accordingly, or you don’t know and get the type from the expression.

(Anyone not knowing the language: let x: Int = 7/2 assigns 3. let x: Double = 7/2 assigns 3.5 because assignment to Double wants a Double expression, therefore / wants two Double operands, therefore the literals 7 and 2 are Double).

Keep in mind you can always report an error if you can’t handle a situation, as long as the code can be changed to work without complaints.


How many comparisons do we need to find min and max of n numbers?

You're dividing badly. If you look at your execution tree, you'll notice that most of the leaves on the last level are 3's. This means you'll need 3 comparisons here. For the same cost you could also compare 4 elements. Your efficiency here is 75%.

Your partial trees have to be full to be the most efficient. So you'll need to divide into trees with numbers of elements that are powers of two.

In your case dividing into a left oriented tree it's

T(100) = T(64) + T(36) +2
       = T(64) + T(32) + T(4) + 4
       = 94 + 46 + 4 + 4
       = 148


Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

Hint. Consider a word a length $\geqslant k$ accepted by $M$ and a successful path for this word. Now prove that this path goes at least twice through the same state, thus producing a loop.


What is the Haskell-style type signature called (i.e., who is it named after)?

Is it Hindley-Milner type system by any chance?


Matching each unique pokemon with a unique move

While your description of the problem is not super clear. I can guess that you're looking at a maximum bipartite matching problem. Which by the way, can also be viewed as a degenerate case of maxflow problem. Both problems are classic, you should have no problem finding resources on them. For example, this.


How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

The largest 12 digit number in base 10 is $10^{12} - 1$.  In general the largest $n$ position number in a base $b$ is $b^{n} - 1$.  So in your case you need a base large enough that $b^{9} - 1 > 999,999,999,999$ $(10^{12} - 1).$  Solving for $b$:

$$b^{9} - 1 > 10^{12} - 1$$
$$b^{9} > 10^{12}$$
$$b^{9/9} > 10^{12/9}$$
$$b > 10^{12/9}$$
$$b > \sqrt[9]{10^{12}}$$
$$b > 21.54$$

So make your base 22 and your numeric data will fit in 9 positions.


What is the relation between First Order Logic and First Order Theory?

First-order logic is a mathematical subject which defines many different concepts, such as first-order formula, first-order structure, first-order theory, and many more. One of these concepts is first-order theory: it is a set of first-order formulas. Often we consider the first-order theory generated by a finite number of axioms and axiom schemes. Such a theory is closed with respect to logical derivations, and we usually only consider theories satisfying this condition.

A first-order theory is complete if for every statement $\sigma$, it contains either $\sigma$ or its negation. Not every theory is complete. Indeed, Gödel's incompleteness theorem highlights the fact that many interesting first-order theories are necessarily incomplete.

A model of a first-order theory is a valid interpretation of the theory (we leave the exact definition for textbooks). For example, the first-order theory of groups consists of all statements that follow from the group axioms. Every group is a model of the first-order theory of groups.

For every given model, very given sentence is either true or false. Gödel's completeness theorem states that if a first-order sentence is true in all models of a first-order theory, then it is provable from a finite number of sentences in the theory. For example, every first-order statement in the language of groups which holds for all groups is provable from the group axioms.

LIA is (presumably) a first-order theory which is interesting enough to be incomplete due to Gödel's incompleteness theorem. However, in the standard model – the "true" integers – every sentence is either true or false. In particular, if $\sigma$ is a statement such that neither $\sigma$ nor $\lnot \sigma$ belong to LIA, then either $\sigma$ or $\lnot \sigma$ holds for the true integers, but this fact isn't provable in LIA.


Any notions of operations in basic postulates of lambda calculus

You can think of application $MN$ as an algebraic operation, where the operator has been elided for convenience. Instead of $MN$ some people write $M @ N$, or even
$$
apply(M, N)
$$
So $apply(\cdot, \cdot)$  is a binary operation, and, as @chi points out,
 $apply(\cdot, \cdot)$ is is neither associative nor commutative. The precise nature of what $apply(\cdot, \cdot)$  does depends on exactly what $\lambda$-calculus you have in mind.


Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

I guess, I have found the answer myself: no.

Let $q$ be a shortest program that generates $x$: $K(x)=l(q)$. It is enough to concatenate any incompressible string $s$ not sharing information with $q$ and setting $p=\bar{q}s$. Let $m$ be the number of a Turing machine $T_m$ in the standard enumeration, that takes $p$, executes $q$ and discards $s$. Then, $U(\langle m,p\rangle)=T_m(p)=x$.
However, $K(p)\ge l(q)+l(s)+O(1)>l(q)=K(x)$. We thus have constructed a $p$ that contradicts the claim.


Does a megabyte represent (2^8)^1000000 bits in base2? Isn't that more than enough combinations to represent everything?

A megabyte represents $8\cdot10^6$ bits. We can write $2^{8\cdot10^6}$ bit-strings using this much memory. But, this number is not the same as how many such bit-string we can store! Well, we can only store a single bit-string of size  $8\cdot10^6$ bits in $1$ megabyte.

To understand this better: consider a single page of a document. On a single-spaced page with 12 point font, we can put around 3000 characters. The number of possible pages that can be written in English on this single page of the document would be $26^{3000}$. But, how many characters can we actually write on such a page? quite simply 3000.


how to express an intertemporal implication constraint in integer linear programming (ILP)?

Base yourself on the fact that $x_{d,i} \land x_{d',j} $ happens iff $ x_{d,i} + x_{d',j} =2  $.

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \leq \sum\limits_{i<j<k} a_k + (j-i)(2-x_{d,i} - x_{d',j}) $

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \geq \sum\limits_{i<j<k} a_k + (j-i)(x_{d,i} + x_{d',j} - 2) $

Check these equations in two cases : $ x_{d,i} + x_{d',j} =2 $ and $ x_{d,i} + x_{d',j} < 2  $

Depending on your $a_k$ and problem, you may get a better multiplicative constant than $(j-i)$. If you can, do it, otherwise the continuous relaxation is going to suck.


What is the correct way to define time constructible functions?

The two definitions are probably equivalent (perhaps $f(n)$ need be not too small): given $f(n)$ in binary you can write $1^{f(n)}$ in $O(f(n))$ time, and vice versa. The ideas are as follows.

Binary to unary: Inductively construct $1^{b_m b_{m-1} \ldots b_{m-t}}$, where $b_m\ldots b_0$ is the binary representation of $1^{f(n)}$. At each step we need to roughly double the string of 1s, and in stage $t$ this takes roughly $O(f(n)/2^{m-t})$ time. Taking into account all stages, we get roughly $O(f(n))$.

Unary to binary: Construct the binary representation of $f(n)$ from LSB to MSB by repeatedly dividing $f(n)$ by two. The $t$th division by two requires time $O(f(n)/2^t)$, so overall this runs in time roughly $O(f(n))$.

As to why the input is in unary rather than in binary, this ionly affects small $f(n)$; as we have seen, converting between $1^n$ and $n$ should take time $O(n)$, and this is affordable as long as $f(n) = \Omega(n)$.


Why can't we say that NP is closed under complement given that we can say it is closed under intersection

There are several ways to describe the semantics of nondeterministic Turing machines. Perhaps the most colorful is the "guess and verify" semantics. We enhance a vanilla Turing machines with a guess tape, whose exact semantics will be explained below. Our Turing machine communicates its computation with the user by means of the state at which it halts. Some states are marked ACCEPT, the rest are marked REJECT. The semantics of the machine are as follows:

A nondeterministic machine accepts an input $x$ if there exists a string $y$ such that if we run the machine with $x$ on the input tape and $y$ on the guess tape, then it accepts (i.e., halts at a state marked ACCEPT).
Conversely, the machine rejects an input $x$ if whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tape, it always rejects (i.e., halts at a state marked REJECT), whatever we wrote on the guess tape.
A nondeterministic machine accepts a language $L$ if it accepts all $x \in L$ and rejects all $x \notin L$.
A nondeterministic machine runs in polynomial time (polytime for short) if there is a polynomial $p(n)$ such that whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tapes, it always halts within $p(|x|)$ steps.

(We are slightly cheating here: the definitions of acceptance and rejection are complementary only if the machine is promised to always halt, which is indeed the case for machines running in polynomial time.)

When describing the operation of a nondeterministic machine, we will often use the keywords "guess" and "verify". They have the following meaning:

Guess $w$: Copy a string $w$ (delimited in some fixed way) from the guess tape to the work tape.
Verify property $A$: Check whether property $A$ holds. If so, continue with the execution of the algorithm. Otherwise, halt at once at a state marked REJECT.

Another important convention is:

If the algorithm runs its course without rejecting, then the machine halts at a state marked ACCEPT.

Here is an example, a machine for SAT:

Input: A formula $\varphi$ in conjunctive normal form.
Operation: Guess an assignment $a$, and verify that it is a satisfying assignment.

A more exact description of the machine would be:

Copy an assignment $a$ from the guess tape to the work tape.

Check whether $a$ satisfies $\varphi$.

If $a$ doesn't satisfy $\varphi$, halt at a state marked REJECT.

Otherwise, halt at a state marked ACCEPT.

Let us now consider the proof that NP is closed under intersection. Let $M_1,M_2$ be polytime nondeterministic Turing machines accepting languages $L_1,L_2$ (respectively). The following polytime nondeterministic Turing machine $M$ accepts $L_1 \cap L_2$:

Verify that $M_1$ accepts the input.
Verify that $M_2$ accepts the input.

In more detail:

Decode the contents of the guess tape into two guess words.
Run $M_1$ on the inputs and the first guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
Run $M_2$ on the inputs and the second guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
Enter a state marked ACCEPT and halt.

Why does this work? Let $L$ be the language accepted by this machine. We have to show that $L = L_1 \cap L_2$.

$L_1 \cap L_2 \subseteq L$: Suppose that $x \in L_1 \cap L_2$. Since $x \in L_1$, there exists a string $y_1$ such that $M_1$ accepts when run on $x$ with $y_1$ on the guess tape. Similarly, since $x \in L_2$, there exists a string $y_2$ such that $M_2$ accepts when run on $x$ with $y_2$ on the guess tape. If we run $M$ on $x$ with $(y_1,y_2)$ on the guess tape, then it will accept, and so $x \in L$.

$L \subseteq L_1 \cap L_2$: Suppose that $x \in L$. Thus there is a string $y = (y_1,y_2)$ such that when $M$ is run on the input $x$ and $y$ on the guess tape, it accepts. The machine $M$ verifies that $M_1$ accepts when run on the input $x$ and $y_1$ on the guess tape, and that $M_2$ accepts when run on the input $x$ and $y_2$ on the guess tape. Therefore $x \in L_1$ and $x \in L_2$, and so $x \in L_1 \cap L_2$.

Now let us try to prove that NP is closed under complementation. Let $M$ be a polytime nondeterministic Turing machine accepting a language $L$. We construct the following Turing machine $M'$:

Run $M$. If $M$ accepts, reject. Otherwise, accept.

Let us see what are the semantics of this machine. The machine $M'$ accepts an input $x$ if there exist a string $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects. Conversely, the machine $M'$ rejects an input $x$ if $M$ accepts $x$ regardless of the contents of the guess tape.
This is not quite what we want, and to demonstrate it, let us consider the machine $M$ accepting SAT described above. Recall that the machine interprets its input as a formula $\varphi$, and the contents of the guess tape as an assignment $a$. The machine $M$ accepts iff $a$ satisfies $\varphi$. The corresponding machine $M^c$ has the following semantics:

The machine $M^c$ accepts a formula $\varphi$ if some assignment $a$ doesn't satisfy $\varphi$.

The machine $M^c$ rejects a formula $\varphi$ if all assignments $a$ satisfy $\varphi$.

In other words, the machine $M^c$ accepts the language of all formulas which are not tautologies. This is not what we were aiming for: we wanted $M^c$ to accepts the language of all unsatisfiable formulas. As an example, $M^c$ accepts the formula $x_1 \lor x_2$ even though it is satisfiable, because it's not a tautology (if $x_1$ and $x_2$ are both false then $x_1 \lor x_2$ is also false).


The maximum decimal integer that can be stored in memory of 8-bit word processor computer?

I got the same question in my technical informatics exam. The right answer was also 127, my professor explained signed integer is the default format, therefore the range would go from -128 to 127. You can display 256 distinct value, but the maximum would still be 127.


How is A* search superior to Dijkstra's algorithm

Consider providing driving directions from an origin to a destination. Although sometimes traveling away from the destination for short distances is required (think highway on ramp), in general it is best to travel toward the destination. In this case A* is likely to outperform Dijkstra's algorithm because it (probably) will traverse less of the graph.

Dijkstra's algorithm uses a single heuristic, $g(n)$, which is the distance from the origin. In selecting the next road to evaluate, the road with the least $g(n)$ is selected; however, this road may travel away from the destination. A* adds an estimate of the remaining distance, $h(n)$, to bias the search towards the destination. The full A* heuristic is $f(n) = g(n) + h(n)$. Note that as the search progresses, $f(n)$ must monotonically increase or else the path found may not be the shortest.  Thus, $h(n)$ must be optimistic and never underestimate the remaining distance (in the directions example, assume the remainder of the trip can be a straight line).


Significance of parameters in Tiny Mersenne Twister algorithm

You can generate parameters for the PRNG using the provided program tinymt32dc. You should generate these parameters once and for all for each application. Each time you call the PRNG, you use the same parameters but a different seed. The reason that you don't want to vary the parameters is that generating them is (apparently) time consuming, while initializing the PRNG from just the seed is designed to be quick.

There might be some constraints on these parameters, but since you're not the designer of TinyMT, you're not aware of them. Instead, you should just use the provided program that generates legal parameters.


Is it a sufficient condition to be in NP?

You can obtain a non-deterministic polynomial-time Turing machine $T$ for $D$ as follows:

Since $D \le_p SAT$, there is a polynomial-time Turing machine $T'$ that maps any instance of $D$ into an instance of $SAT$. Simulate the $T'$ on $x$, where $x$ is the input of $T$.
Use any non-deterministic polynomial-time algorithm to decide SAT (e.g., guess the value of all the variables in the SAT formula and check if the formula is satisfied). By definition of Karp reduction, $T$ will accept if and only if $x \in D$.

This shows that $D \in \mathsf{NP}$.


As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does not imply that $a$ has physically caused $b$ (to happen).

Such causality used in Lamport's paper is often called potential causality. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/performance of distributed systems.

To address these issues, we can consider explicit causality, or application-specified causal dependencies. One common example is social network applications: Alice has read 100 comments in a conversation thread and replied to 5 of them with a single comment. Her comment's immediate happens-before dependency could only consist of these 5 comments (instead of all these 100 comments with potential causality).

Which is the better causality? Well, it depends. For example, potential causality prevails in the research area of debugging multi-threaded programs. There are two main reasons (in my opinion): First, we have no context/semantics which tells whether two events ($\textsf{read}$ or $\textsf{write}$ operations) are effectively causally-related or not. Secondly, we want to capture all possible causality among events and reveal as many debugs as possible.

For more discussions about potential causality and explicit causality, please refer to this paper: The Potential Dangers of Causal Consistency and an Explicit Solution.


Recover PRNG description from consecutive outputs

There's no single method to determine the type of the PRNG.  Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs solely by looking at their output.

Instead, for each of the schemes that you list, there is a way to recover the seed and predict future bits from its output.  The way to do that is different for each type of PRNG.  So, the natural approach is: for each candidate type, try the method for recovering the seed that works for that type of PRNG, and see if you're successful.  If you are, you've figured out the type of PRNG.

I don't think there's a more efficient or general technique.  And, frankly, I don't think a more efficient one is needed.  For the types you list, there are very efficient algorithms for cryptanalyzing them, given enough output.  So, I suspect it's going to be hard to beat the "try all schemes" approach.

This works if your set of PRNG types contains only PRNGs that are cryptographically weak, i.e., where it is possible to predict future outputs given enough past outputs.

For details of how to do this for any specific type of PRNG, I suggest you ask a separate question focused on that one type of PRNG.  Here are some resources on some of the PRNG types you listed:

LFSR: See the Berlekamp-Massey algorithm, which is very efficient.  See also https://crypto.stackexchange.com/q/5293/351.
Linear congruential generators (LCG): There are very efficient ways to recover the seed, based on modular arithmetic.  See https://security.stackexchange.com/q/4268/971.
Multiply with carry (MWC): If you have enough output, it's easy to check whether the output appears to be consistent with a MWC generator: see https://crypto.stackexchange.com/q/10359/351.  If you don't have much output, I'm not sure it is possible (for information-theoretic reasons, since the seed and internal state is so large).


DFA & RE from descriptive definition of given regular language

You can always use the current state of the automaton to remember the last three characters you've seen.  Now, you can implement two phases.  In the first phase, you're happy if you're ever in the situation where the last three characters were $010$.  In the second phase, you become unhappy if you ever see $010$ again.


How to find expected number of slots of a certain size k in hash table?

I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution.

From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table with $M$ slots and $N$ entries is

$\binom{N}{k} \left ( M-1 \right )^{N-k} / M^N$

Assuming "ideal" hash function, however practical real-world hash functions are often very good and could be considered as "ideal" for applying theoretical results.

Applying famous $e$ representations via limits and Stirling's approximation, I derived that the probability in terms of $α=N/M$ (load factor) is approximately equal to k-th value in Poisson distribution with parameter $λ=α$, i. e.

$\alpha^k e^{-\alpha}/k!$

Seems reasonable and was my first assumption before analysing the formula from TAoCP, because average chain length is obviously $α$, which correspond Poisson distribution expected value.

If $α$ (load factor) is equal to 0.75, then probabilities of slot chains to be of the specific length are:

k = 0 -- 0.47
k = 1 -- 0.35
k = 2 -- 0.13
k = 3 -- 0.03
k > 3 -- 0.01


Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Matrix multiplication algorithms are analyzed in terms of arithmetic complexity. The computation model is straight-line programs with instructions of the form $a \gets b \circ c$, where $\circ \in \{ +,-,\times,\div \}$, $a$ is a variable, and $b,c$ could be either variables, inputs or constants. Additionally, certain variables are distinguished as outputs. For example, here is how to multiply two $2\times 2$ matrices using the usual algorithm, with input matrices $a_{ij},b_{ij}$ and output matrix $c_{ij}$:

$$
\begin{align*}
x_{11} &\gets a_{11} \times b_{11} & y_{11} &\gets a_{12} \times b_{21} & c_{11} &\gets x_{11} + y_{11} \\
x_{12} &\gets a_{11} \times b_{12} & y_{12} &\gets a_{12} \times b_{22} & c_{12} &\gets x_{12} + y_{12} \\
x_{21} &\gets a_{21} \times b_{11} & y_{21} &\gets a_{22} \times b_{21} & c_{21} &\gets x_{21} + y_{21} \\
x_{22} &\gets a_{21} \times b_{12} & y_{22} &\gets a_{22} \times b_{22} & c_{22} &\gets x_{22} + y_{22}
\end{align*}
$$
The complexity measure is the number of lines in the program.

For matrix multiplication, one can prove a normal form for all algorithms. Every algorithm can be converted into an algorithm of the following form, at the cost of only a constant multiplicative increase in complexity:

Certain linear combinations $\alpha_i$ of the input matrix $a_{jk}$ are calculated.
Certain linear combinations $\beta_i$ of the input matrix $b_{jk}$ are calculated.
$\gamma_i \to \alpha_i \times \beta_i$.
Each entry in the output matrix is a linear combination of $\gamma_i$s.

This is known as bilinear normal form. In the matrix multiplication algorithm shown above, $x_{jk},y_{jk}$ function as the $\gamma_i$, but in Strassen's algorithm the linear combinations are more interesting; they are the $M_i$'s in Wikipedia's description.

Using a tensoring approach (i.e. recursively applying the same algorithm), similar to the asymptotic analysis of Strassen's algorithm, one can show that given such an algorithm for multiplying $n\times n$ matrix with $r$ products (i.e. $r$ variables $\gamma_i$), then arbitrary $N\times N$ matrices can be multiplied in complexity $O(N^{\log_n r})$; thus only the number of products matters asymptotically. In Strassen's algorithm, $n = 2$ and $r = 7$, and so the bound is $O(N^{\log_2 7})$.

The problem of finding the minimal number of products needed to compute matrix multiplication can be phrased as finding the rank of a third-order tensor (a "matrix" with three indices rather than two), and this forms the connection to algebraic complexity theory. You can find more information in this book or these lecture notes (continued here).

The reason this model is used is twofold: first, it is very simple and amenable to analysis; second, it is closely related to the more common RAM model.

Straight-line programs can be implemented in the RAM model, and the complexity in both models is strongly related: arithmetic operations have unit cost in several variants of the model (for example, the RAM model with real numbers), and are otherwise related polynomially to the size of the numbers. In the case of modular matrix multiplication, therefore, arithmetic complexity provides an upper bound on complexity in the RAM model. In the case of integer or rational matrix multiplication, one can show that for bilinear algorithms resulting from tensorization, the size of the numbers doesn't grow too much, and so arithmetic complexity provides an upper bound for the RAM model, up to logarithmic factors.

It could a priori be the case that a RAM machine can pull some tricks that the arithmetic model is oblivious to. But often we want matrix multiplication algorithms to work for matrices over arbitrary fields (or even rings), and in that case uniform algorithm should only use the arithmetic operations specified by the model. So this model is a formalization of "field-independent" algorithms.


Reason programming language B was named "B"?

B was designed by Dennis Ritchie and Ken Thompson, as a cut-down version of BCPL, the Basic Combined Programming Language. Ritchie [1] says,

  [B's] name most probably represents a contraction of BCPL, though an alternate theory holds that it derives from Bon, an unrelated language created by Thompson during the Multics days. Bon in turn was named either after his wife Bonnie, or (according to an encyclopedia quotation in its manual), after a religion whose rituals involve the murmuring of magic formulas.

[1]  Dennis Ritchie, The development of the C language. ACM SIGPLAN Notices. 28 (3): 201–208, 1993.


Simplest combination of logic gates to produce a given set of outputs

This problem is discussed in Circuit Minimization Problem, by V. Kabanets and J.-Y. Cai.

Obviously the decision version is in NP (does there exists a circuit of size $\le k$ which agrees with the given truth table), since you could provide the circuit $\mathcal{C}$ and verify that $\forall x\in\left\{0,1\right\}^n : \mathcal{C}(x)=f(x)$. This can be done in polynomial time (relative to the input's size), since the size of the truth table is $2^n$.

It's an open question how hard the problem is.  The above paper shows that any proof that this problem is in $P$, or any proof that it is $NP$-complete, would extend our current knowledge and imply a solution to long-standing open problems in complexity theory.

If the Circuit Minimization Problem is in $P$, then it is shown that $BPP=ZPP$ (so for now, showing your problem is in $P$ is open).

Since this is believed to happen anyway (under the assumption that $P=BPP$), they give more consequences which are less likely. For example, it is enough to show $2^n/n$ circuit lower bound for the class $E$ to obtain a $2^{c\cdot n}$ lower bound (If high circuit complexity functions exist in $E$, then very high circuit complexity functions exist too). They also show how to factor Blum integers efficiently on average (Which, they say, is the strongest evidence for the fact that this problem lies outside of $P$).

If the Circuit Minimization Problem is $NP$-hard (under what they call a "natural reduction", where the reduction's output size depends only on the input's size and not structure) then $BPP\subseteq SUBEXP$ and $BPP=P$ unless the exponential time hypothesis fails.


"Is there a two-state NPDA that accepts the same language?"

Yes, every PDA can be replaced by one that has two states, one accepting and one non-accepting. In general one uses three steps to prove this formally:

Every PDA (with empty stack acceptance) can be transformed into a CFG. The construction is sometimes known as the triplet construction: a single nonterminal of the CFG codes two states and a stack symbol of the PDA.
Every CFG can be transformed into a PDA with a single state and empty stack acceptance. That equivalence is quite straghtforward.
PDA with empty stack acceptance are equivalent to PDA with final state acceptance. But, where the stack-PDA may have a single state, the state-PDA usually uses one more, for acceptance.

Always, when discussing PDA, be explicit on the acceptance mode. (But that might be a silly request when your textbook considers only one of these types.)

PS. By the way, your machine seems to have the basic counting ideas implemented.


Problem is in NP

You can easily verify an answer to your problem: if a path is given, and it is goes from $s$ to $t$ and has $k$ edges with distinct vertices, then it is correct.

Reduction from Hamiltonian Cycle Problem

You can pick any vertex as $s$, and then for each neighbor, $(s,t_i)\in E$, attempt your algorithm, with $k=\left|V\right|-1$ after cutting that edge. If the algorithm succeeds for any attempt with $(s,t_i)$, then you have found a Hamiltonian cycle. This means Hamiltonian path reduces to your given problem.

Given that it is in NP, and the Hamiltonian Cycle Problem can be reduced to it, it is NP-complete.

EDIT
I suppose an even simpler reduction is just to set $s = t$, and for any vertex in $V$, with $k=\left|V\right|-1$.

Though I am unsure of how one would solve this problem given $s,t,k,V,E$ in the general case. Nor do I know how to reduce this problem to the Hamiltonian cycle problem. A roundabout way would be to reduce this problem to 3-SAT, and then reduce the result back down to Hamiltonian cycle. However, as I pointed out above, you can easily see it is NP-complete, due a reduction from Hamiltonian cycle to this problem, in conjunction with the fact that the problem is in NP (you can verify the answer easily).

k-Stroll / k-Tour

A similar problem is named the k-Stroll problem in Approximation Algorithms for the Directed k-Tour and k-Stroll Problems:

  The input to the k-Stroll problem is a directed $n$-vertex graph with nonnegative edge lengths, an integer $k$, and two special vertices $s$ and $t$. The goal is to find a minimum-length $s$-$t$ walk, containing at least $k$ distinct vertices.

Also related is the k-Tour problem, which is the case where $s=t$.


Human computing power: Can humans decide the halting problem on Turing Machines?

It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.

You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.

After taking propositional and then predicate calculus  I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."

There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.

Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines
http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments


Why "Choice Points" introduce non-determinism in a program?

Nondeterminism is an inherently unphysical concept. If you think about the various definitions of nondeterministic computation, they always say something like one of the following:

the computation is structured as a tree and, if any of the paths through the tree succeeds, the computation succeeds, regardless of how many failures there are on other paths;
the computer "magically" considers all the options in parallel, even though there might be exponentially many of them;
the computer only considers one option but it "magically" knows which one will lead to success, if any of them will, and chooses that one.

In principle, the "choice" operator achieves nondeterminism – at least, it would, if we could implement it using one of the above schemes. Unfortunately, in the real world, we don't know how to do that, so we have to pick an option, see if it works out, and backtrack if it doesn't. Maybe we could do something a bit smarter than just trying the options in order but, at the end of the day, we don't know any efficient way of implementing nondeterminism on a real, deterministic, computer (which is why we don't know that $\mathrm{P}=\mathrm{NP}$).


Set of all rational numbers less than given computable real number is decidable

I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$.

If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between rationals, which is decidable.

Otherwise, we can assume $a$ is irrational. Our algorithm performs the following.
First, we take the candidate $x\in\mathbb{Q}$ as input.
We then query $f$ (the function which approximates $a$ as requested) repeatedly with $q=2^{-n}$ for every $n>0$.
Eventually, for some $n$ we will obtain one of

$$
f(2^{-n}) + 2^{-n} < x
\qquad \lor\qquad
x < f(2^{-n}) - 2^{-n}
$$
Indeed, this will happen as soon as $2^{-n} < |x-a| / 2$, which is a possibility because we know $x \neq a$.

In the first case, we return $x > a$ ($x \notin A$), in the second we return $x<a$ ($x \in A$).

The correctness comes from
$$
a \leq f(2^{-n}) + 2^{-n}
\qquad \land\qquad
f(2^{-n}) - 2^{-n} \leq a
$$
being true for all $n$.

Note that this solution is not uniform in $a$. That is, we only prove that there is an algorithm for any computable $a$, taking a candidate rational $x$ as input. We do not show that there is a single algorithm that, given both $a$ and $x$ as input is able to decide $<$ (indeed, that would be undecidable).


How to position images within a canvas while avoiding overlapping

If there is a place for the new image to fit, there must be a place where the left edge of the new image is aligned with either the left edge of the canvas or of some previous image. The same true for the top edge of the new image.  So, if you've already placed 2 images, you only have to try 3 possibilities for the left edge and 3 possibilities for the top edge, or a total of 9 candidate positions in total.  Given a candidate position, you should be easily able to test whether a new image can be placed there without overlapping any prior image.


Checking claim in paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al

The claim in the paper is true (I never doubt about it, but just wanted to know why) because only the dependencies between the reads and writes of concurrent transactions determine if these are serializable, but not their commits (nor their aborts, obviously).

In the example above, extracted from the paper's claim, the fact that PostgreSQL aborts T2 has nothing to do with serializability between T1 and T2, but only with some design decision in PostgreSQL that I ignore (if someone knows I, please write a comment to this answer).


What's relation between Kolmogorov complexity and pseudorandomness?

The standard notion of pseudorandomness is about a process.  You can say that the process (the pseudorandom generator) is pseudorandom, or not.  The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.

Kolmogorov randomness is a property of a bit-string.  You can say that a particular bit-string (sequence) is Kolmogorov-random, or not.  Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.

If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random.  Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.

That's the relationship.

Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string.   Knowledge is irrelevant.  What matters is existence: whether or not exists a program that generates the string.  If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.

You asked about compressibility.  Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random).  There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.

The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run.  Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter.  The catch is that $C$ takes a very long time to run: it takes exponential time.  In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one.  This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.

Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable.  For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression.  (Why?  Truly random bit-strings are, with high probability, not compressible by $C$.  If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.)  So in practice, outputs of a pseudorandom generator are not compressible.

Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness.  Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time).  Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string).  "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).


What does the R superscript notation mean in regular/formal languages?

Reverse. So for example $(001)^{R} = 100$. Or to overdo it, for an string $s = s_{1}s_{2}\ldots s_{n}$, the reverse $s^{R}$ is $s_{n}s_{n-1}\ldots s_{2}s_{1}$.


Proving $a^{2+n}a^{n}$ is regular using the Pumping Lemma

Noooooo!

Usage of the pumping lemma to prove regularity is remarkably rare, and certainly won't happen with a direct application.

Let's review the formal statement, with particular emphasis on the quantifiers:

$$\forall \ L \subseteq \Sigma^* ( \ L \ \text{is regular} \Rightarrow  \exists \ p \ge 1 \ \ \forall \ w \dots \ \ \exists \ x, y, z \dots \ \ \forall \ i \dots \ )$$

Two notable observations are that being regular is part of the hypotheses and that nothing is said about the converse, which is in fact false (a number of classical counterexamples can be found in literature).

In other words, even if you managed to somehow prove the $\exists \forall \exists \forall$ block, it still wouldn't say anything about the regularity of $L$. The way the pumping lemma is normally used is in its contrapositive form. You may recall from basic logic that $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$. Using that principle, we can derive the following logical consequence:

$$\forall \ L \subseteq \Sigma^* ( \ \forall \ p \ge 1 \ \ \exists \ w \dots \ \ \forall \ x, y, z \dots \ \ \exists \ i \dots \Rightarrow L \ \text{is }\textbf{not }\text{regular} \ )$$

Notice how this is a tool to prove non-regularity, and that, even there, nothing can be said about the converse.

I'm afraid your attempt of proof is just entirely misguided.


$k$ vertex-disjoint paths cover in Directed Acyclic Graph

TL;DR- The problem can be solve optimally using min-cost flow algorithms, such as the Successive Shortest Path (SSP) algorithm. The run time of the algorithm is $O(k\cdot (|E|+|V|\log |V|))$, which is polynomial by the size of the graph (note that $k \in O(|V|)$).

First, note that the problem can be converted into finding $k$ edge-disjointed paths problem, covering the maximum number of vertices. We simply split every vertex $v$ into $v^{in}$ and $v^{out}$ such that: 1) If $(u,v)\in E$ was in the original graph $G=(V,E)$, than $(u^{out},v^{in})\in E'$ is in the transformed graph $G'=(V',E')$. 2) There is an edge  $(v^{in},v^{out})\in E'$ for every vertex $v \in V$.  A set of $k$ edge-disjointed paths, covering the maximum number of vertices in $G'$ is equivalent to a set of $k$ vertex-disjointed paths, covering the maximum number of vertices in $G$.

Second, we add a source $s$ and a sink $t$ to $G'$. Then, we connect $s$ to all vertices with zero indegree ($d^{in}(v^{in})=0$), and connect all vertices with zero outdegree ($d^{out}(v^{out})=0$) to $t$. We associate every edge $e$ in $G'$ to have capacity $c(e)=1$, and the cost of every edge $e=(v^{in},v^{out})$ is equal to $w(e)=-1$, and for every other edge the cost is $w(e)=0$. We set the required flow between source $s$ and sink $t$  to be equal to $k$.  The corresponding min cost flow is simply a union of $k$ edge-disjointed paths in $G'$, which cover the maximum number of vertices. Thus, deriving the min cost flow will imply  the corresponding $k$ vertex-disjointed paths in $G$, which cover the maximum number of vertices, as required.

The graph $G'$ is acyclic, even after adding $s$ and $t$. Thus,  we can use the SSP algorithm for acyclic graphs with negative weights (more information can be in [1]). The run time of the algorithm will be $O(k\cdot (|E|+|V|\log |V|))$.

[1]-https://www.cs.tau.ac.il/~yuvalroc/YuvalRochmanThesis.pdf, page 70.


Implementing an efficent priority queue using only stacks

Unfortunately, it's not possible.  The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be removed in an order that depends on the value of the items.


Turn MST of G to MST of G with one new edge

Please see my answer to the question "Updating an MST $T$ when the weight of an edge not in $T$ is decreased".

Before we add $e'$ with weight $w(e')$, let us add $e'$ with weight so large (or, for example, larger than the weight of every other existing edge) that $e'$ will not be in any $MST$. In particular, $T$ remains an MST with this addition.

Now let us change the weight of $e'$  to $w(e')$. Then this question becomes the same question in the linked answer above.