# Question
Title: Describing language generated by grammar
S -\> aSb | A | B

A -\> aS | a

B -\> Sb | b

is this the language generated by this CFG? Or am I missing something?

# Answer
A technique that can be useful here is to eliminate some of the variables. Since $A$ can only be replaced by $aS$ or $a$ and $B$ by $Sb$ or $b$ we have the equivalent grammar $$ S\rightarrow aSb\mid aS\mid a\mid Sb\mid b $$ Now notice that in any sentential form in a derivation we can only add $a$s to the left of $S$ and we can only add $b$s to the right, so any string of terminals derived from the start variable must have the form $a^mb^n$. Finishing off, we see that $S$ must eventually be replaced by one of $a$ or $b$, so we see that your proposed answer was almost correct: $$ L(G) = \\{a^mb^n\mid m,n\ge 0\text{ and }m,n\text{ not both }0\\} $$ or, if you prefer a slightly nonstandard regular expression-ish version $$ a^\*b^\*\setminus\epsilon $$
> 0 votes

---
Tags: formal-languages, context-free, formal-grammars
---


title: Array accesses and basic operations

text:
# Question
Title: Array accesses and basic operations
I was looking through some lecture slides on algorithm analysis and found that in general an array access counted as a basic operation, but it did not seem to count as one when accessing the first element (e.g. `A[i]` is a basic operation but `A[0]` isn't). Does only accessing the first element count as a basic operation, and if it doesn't, does accessing an array by a predefined index (e.g. `A[5]`) count as one, and why is this the case?

# Answer
> 4 votes
It usually doesn't matter, since we're usually only interested in the order of growth of the number of steps. As long as we both agree that evaluating `A[i]` is a constant number of steps, independent of `i`, it doesn't actually matter what that constant is and we don't need to agree that it's the same constant. We'll both agree that the algorithm is, say, $\Theta(n^2)$, even if I think the running time is $45n^2 + 16n + 18$ and you think it's $68n^2+25n+21$. (And, in reality, neither of us is likely to be able to evaluate the running time to that level of precision.

So, it's usually fine to say that `A[0]` is a single step, as is `A[5]` (any sane compiler would compute "five cells beyond `A[0]`" at compile-time anyway) and `A[i]` where `i` is some variable. It won't make any difference to most analyses if you say that `A[5]` and `A[i]` are two operations due to having to compute the offset.

In some models of computation, things might be a bit more complicated because, if `i` is an arbitrary integer, it might not be sensible to assume that you can manipulate it in a constant number of steps. For example, on a standard Turing machine, you need to read $\log\texttt{i}$ tape cells just to know what `i` is. But that doesn't look much like what a real computer does.

---
Tags: algorithms, algorithm-analysis, time-complexity
---


# Question
Title: Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law
If I have the sum-of-products expression `B~CD + ACD` how would I convert this so it could be implemented using 3-input NAND gates through DeMorgan's Law? Would this not generate the expression: `~(~(B~CD) ^ ~(ACD))`?

It would seem I could implement this and use a 3-input NAND gate with 3-C inputs to act as a NOT gate but this seems wrong.

If this isn't the right place for such a question, let me know and direct me elsewhere if possible, I'll remove it.

# Answer
You have the basic rule that (a or b) = not (not a and not b), so you use that repeatedly. The first application gave you B~CD + ACD = NAND(~(B~CD), ~(ACD)). You're almost there:

NAND(~(B~CD), ~(ACD)) = NAND (NAND (B, ~C, D), NAND (A, C, D)) = NAND (NAND (B, NAND (C, C, C), D), NAND (A, C, D))
> 0 votes

---
Tags: circuits, boolean-algebra, digital-circuits
---


# Question
Title: Determining if a langage defined by a given context-free grammar is finite using the pumping lemma
Here is a question that I found into an old exam:

> Describe an algorithm that, given a context-free grammar $G$, can determine if the language $L(G)$ produced by $G$ is finite or infinite.
> **Hint**: use the pumping lemma.

While I found several possible solutions to the problem (mostly exploiting the presence or non-presence of cycles in the grammar or automata) none of them implies the use of the pumping lemma (that was given as hist). For this reason I believe that none of the solutions that I found corresponds to the intended one.

Is there any way an algorithm could exploit the pumping lemma in order to solve this problem?

# Answer
Here is the corresponding result for regular languages:

> Given a DFA with $n$ states, its corresponding language is infinite iff it contains a word whose length is between $n$ and $2n-1$.

This implies an inefficient algorithm for determining whether the language is infinite.

The proof uses the pumping lemma in its following formulation:

> If a regular language $L$ is accepted by a DFA with $n$ states, then any word $w \in L$ of length at least $n$ can be decomposed as $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

In one direction, if the DFA accepts some word $w$ of length at least $n$, then the pumping lemma shows that there is some decomposition $w = xyz$ with $y \neq \epsilon$ such that the infinitely many words $xy^iz$ belong to the language.

In the other direction, if the language is infinite then it contains some word whose length is at least $n$. Let $w$ such a word of minimal length. The pumping lemma show that there exists a decomposition $w = xyz$, with $0 \< |y| \leq n$, such that $xz$ is in the language. Since $|xz| \< |xyz|$, it follows that $|xz| \< n$, and so $|w| = |xyz| \< 2n$.

If you use the pumping lemma for context-free languages in a formulation in which the pumping constant is related to the size of a context-free grammar for the language, then you can use similar reasoning to come up with an algorithm that determines whether the language generated by a context-free grammar is infinite.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: using pumping lemma prove this language is not a context-free-language
How can one prove that the language below is not context-free using the pumping lemma?

$$\\{ a^i b^m a^j b^m a^k b^m \mid i,j,k,m \geq 0 \\}$$

# Answer
> -1 votes
Suppose that $a^\* b^m a^\* b^m a^\* b^m$ is context-free. Applying the inverse of the homomorphism defined by $a\mapsto a$ and $b,c,d \mapsto b$, we see that $a^\* (b+c+d)^m a^\* (b+c+d)^m a^\* (b+c+d)^m$ is also context-free. Intersecting with the regular language $b^\* a c^\* a d^\*$, we see that $b^m a c^m a d^m$ is also context-free. Applying the homomorphism defined by $a \mapsto \epsilon$ and $\sigma \mapsto \sigma$ for $\sigma=b,c,d$, we see that $b^mc^md^m$ is also context-free. But we know that it's not context-free.

---
Tags: formal-languages, context-free
---


# Question
Title: How much does regularization prevent overfitting?
I've been curious why machine learning algorithms with high VC dimension, such as XGBoost and deep learning, do well in practice. The answer appears to be regularization significantly restricting the parameter space, but the only justifications I've seen are references to Occam's razor.

Is there quantitative/theoretical understanding of how much regularization can prevent overfitting in a model?

Background: I've taken a course in machine learning and covered the theory behind regularization and a couple techniques, such as lasso and ridge regression. I understand the principle that regularization can reduce the VC dimension by minimizing or zeroing weights in the model.

But, that principle does not clarify in my mind whether regularization is adequate to counteract the high VC dimension in models used by XGBoost and deep learning.

I am asking for some sort of quantitative theory that provides justification that even with high VC dimension regularization can reduce the dimensionality enough to provide a decent guarantee of generalization.

Alternatively, providing a method I can use to figure this out myself is also acceptable.

# Answer
> 4 votes
Moritz Hardt's *excellent* blog outlines extensive research into the idea that stability in machine learning methods is related to the idea of generalization. Interestingly, we find that regularization *implies* stability.

Formally, given observations $S = (z\_1, \dotsc, z\_n)$ and algorithm $A$, stability is defined as the expected difference between the risk and empirical risk $$\mathbb{E}\[R - R\_e\] = \Delta,$$ where $R\_e = \ell(z, S) = \frac{1}{n} \sum\_i \ell(z\_i, A(S))$ is the empirical risk and $R = \mathbb{E}\_{z \sim D}\[\ell(z, A(S))\]$ is the risk.

The post details how to obtain bounds on $\Delta$ and its implications much better than I ever can. I highly recommend reading that post along with all of his other posts.

A much more practical argument is that regularization constrains the problem space to a very specific subset of models; namely, regularization methods can be recast as constrained optimization where $\\|\beta\\|\_p \leq c$ for some value of $p$. This is equivalent to using prior knowledge about the problem and forcing the solution to be within some constrained space.

---
Tags: machine-learning
---


title: What is Memory Mapping in Cache?

text:
# Question
Title: What is Memory Mapping in Cache?
People all over the internet are asking "What are the different Memory Mapping Techniques in Cache", but i couldn't find anywhere the answer to "What is Memory Mapping exactly?".

Please tell what do you mean by memory mapping?

# Answer
> 1 votes
Memory mapping is the (complex) process that associates an address value (usually a 32 or 64 bits number) to some existing physical location in the hardware. This location can be in RAM, in a cache of some level, or even on the hard disk ! During program execution, data can move from one location to another, and possibly be duplicated.

The system keeps track of that and makes the mapping transparent so that the program can keep using the same address. Things get tricky when the values are modified and coherence between the copies must be guaranteed.

---
Tags: computer-architecture, cpu-cache, memory-management
---


# Question
Title: Why half of the medians are greater than the median of medians?
I already saw similar question Counting elements that are greater than the median of medians but I couldn't find my answer in there.

CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. This is the algorithm:

> 1. Divide the $n$ elements of the input array into $\lfloor n/5\rfloor$ groups of 5 elements each and at most one group made up of the remaining $n$ mod 5 elements.
> 2. Find the median of each of the $\lceil n/5\rceil$ groups by first insertion-sorting the elements of each group (of which there are at most 5) and then picking the median from the sorted list of group elements.
> 3. Use SELECT recursively to find the median $x$ of the $\lceil n/5\rceil$ medians found in step 2. (If there are an even number of medians, then by our convention, $x$ is the lower median.).
> 4. Partition the input array around the median-of-medians $x$ using the modified version of PARTITION. Let $k$ be one more than the number of elements on the low side of the partition, so that $x$ is the $k$th smallest element and there are $n-k$ elements on the high side of the partition.
> 5. If $i = k$, then return $x$. Otherwise, use SELECT recursively to find the $i$ th smallest element on the low side if $i \< k$, or the .$(i-k)$th smallest element on the high side if $i \> k$.

My problem is the steps 2 and 3. It claims

> at least half of the medians found in step 2 are greater than or equal to the median-of-medians x.

Some thing that I can't understand very well. May be there is a misunderstanding in the `median-of-median` term. What I understand of the median-of-median is in the following:(Every group of five elements is sorted increasing)

> There is a list $A\_1 \cdots A\_{75}$ of input array

**Step1: Sort every group of five elements** $$\overbrace{A\_1A\_2A\_3A\_4A\_5}\overbrace{A\_6A\_7A\_8A\_9A\_{10}}\overbrace{A\_{11}A\_{12}A\_{13}A\_{14}A\_{15}} \cdots \overbrace{A\_{71}A\_{72}A\_{73}A\_{74}A\_{75}}$$ **step 2 of algorithm (get medians)** $$ \overbrace{A\_3 A\_8 A\_{13} A\_{18}A\_{23}}\overbrace{A\_{28}A\_{33}A\_{38}A\_{43}A\_{48}}\overbrace{A\_{53}A\_{58}A\_{63}A\_{68}A\_{73}} $$ **Then repeat recursively (median of medians)** $$ \overbrace{A\_{13},A\_{38},A\_{63}} $$ $$ x = A\_{38} $$

From what I understand, in the last level we can guarantee that $A\_{63}$ is greater than $x$. In step 2 only $A\_{68}, A\_{73}$ are greater than $A\_{63}$ so they are greater than $x$ as well. Since in step 2 $A\_{43}, A\_{48}$ are greater than $A\_{38}$ So at most five elements among 15 elements in step 2 are greater than the $x$. **Then why CLRS claims that half of the medians in step2 are greater than $x$?**

thanks in advance.

---

# update

If the algorithm of finding median of medians is not what I did above, How can I find the median of medians of step2 in $O(n)$?

# Answer
> 2 votes
Because $x$ is the median of all the $\lfloor n / 5 \rfloor$ medians obtained in Step 2, it is smaller than or equal to half of those medians by definition of median. See the figure below (from CLRS, the 3rd edition; Figure 9.1).

***The problem with your example*** is that you are finding the median-of-medians $x$ recursively, however, *without* completing all the recursive steps. You should not stop at Step 3 (the "median of medians" step) in the recursion. Continue the remaining steps. In particular, in Step 4, you will use the "Partition" procedure to establish relationships between the medians obtained in Step 2 and this median-of-medians $x$.

***For your added problem:*** You find it recursively. Why is the time complexity $O(n)$? Well, you can follow the analysis in CLRS.

# Answer
> 1 votes
The answer is easy: because the median-of-medians is... the median of the medians. (By definition, the median of a set of values is larger and smaller than half of these values.)

But the important property in the design of the algorithm is that the median-of-median is also guaranteed to be larger and smaller than a quarter of the values in the array (not just the medians), so that it is a good partitioning pivot. (This guarantees that the number of remaining elements after a partition decreases exponentially.)

---
Tags: algorithms, algorithm-analysis
---


title: Finite automata for sum of digits?

text:
# Question
Title: Finite automata for sum of digits?
How can I construct a finite automata ,which accepts numbers which has sum of digits = 3 ? Alphabet = {0,1,2,3}

# Answer
> 1 votes
i think this is it. if i have some mistakes let me know.

# Answer
> 2 votes
Define one state per sum achieved so far (i.e. $0,1,2,3,\>3$).

Then from any state, it is obvious which is the next state.

---

In terms of regular expressions, you accept

$$0^\*10^\*10^\*10^\*|0^\*10^\*20^\*|0^\*20^\*10^\*|0^\*30^\*$$

---
Tags: automata, finite-automata
---


# Question
Title: $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable?
I have known that:

> A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.

Now I am considering about the partial functions. Is it the fact that:

> A partial function $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive if and only if its graph is a recursively enumerable subset of $\Bbb N^2$.

If it is true (or one direction is true), may I please ask for a proof? Or some reference would be also appreciate (I searched it but did not obtain any useful result).

**Note**: It is from a math course (and I have asked in the math site). And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine and I have no skill of coding). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please? Thanks!

I have done some search but I cannot find some helpful material. Any reference would be appreciate to. Thanks a lot.

# Answer
> 1 votes
A $k$-ary relation $R \subseteq \mathbb{N}^k$ is recursively enumerable if its indicator function $f\_R$ defined by

$$f\_R(n\_1,\ldots,n\_k) = \begin{cases} 1 & \text{if } R(n\_1,\ldots,n\_k) \\ 0 & \text{otherwise} \end{cases}$$

is a partial recursive function.

So if $f: \mathbb{N} \rightarrow \mathbb{N}$ is a partial recursive function, it is easy to see that the graph

$$R\_f = \\{ (m,n) \mid f(m) = n \\}$$

is a recursively enumerable set. We have $f\_{R\_f}(m,n) = 1 - \mathrm{sg}(f(m) - n)$, where $\mathrm{sg}(n)$ is the primitive recursive function that is $0$ for $n=0$ and $1$ otherwise. Since we can express the indicator function $I\_{R\_f}$ of the graph as the composition of partial recursive functions, we therefore conclude that it is also a partical recursive function.

Conversely, if $$R\_f = \\{ (m,n) \mid f(m) = n \\}$$

is a recursively enumerable set with indicator function $I\_{R\_f}$, then

$$f(m) = \mu n. \[ (1 - I\_{R\_f}(m,n)) = 0 \] $$

Here $\mu n.P(n)$ denotes unbounded mineralization over the unary predicate $P(n)$.

---
Tags: graphs, computability, recursion, enumeration
---


# Question
Title: Drawing a DFA for a language/regular expression
how would you draw a DFA for the language over **{a,b,c}** of all words where every occurrence of **b** is preceded **and** followed by **a**.

My thinking of this is that the regular expression for this is **a\* c\* (aba)\* a\* c\*** although I am not too sure. Any help would be appreciated thanks

# Answer
So, first, your regular expression

$$a^\* c^\* (aba)^\* a^\* c^\*$$

is not correct. We need to give it the capacity to deal with many $aba$s, any of which can be surrounded by $a$s and $c$s. So, that would give us

$$(a^\* c^\* (aba)^\* a^\* c^\*)^\*$$

Of course, we still have a few more problems. First, we might have no $b$s, which could still fit into the language you've specified. We can fix that by pulling out the first set from our larger expression:

$$a^\* c^\* ((aba)^\* a^\* c^\*)^\*$$

We can't know the order of the $a$s and $c$s, so we need to use the **union** operator, which behaves essentially like an **or** in regexes:

$$(a\cup c)^\* ((aba)^\* (a\cup c)^\*)^\*$$

We're not done yet, as Thumbnail pointed out, we still need to allow $ababa$, so this gives us Thumbnail's structure, which allows any number of $baa^\*$s after an $a$.

$$(a \cup c \cup a (b a a^\*)^\*)^\*$$

Now, as for your DFA, begin with a start state, and let it accept the empty string:

Clearly, we can have as many $c$s as we want without changing our accept state:

$b$s are a little different, because they may be the start of an $aba$ pattern. This means that we need a new state to encode that we've encountered n $a$:

Now, if we arrive at a $c$, then our $a$ was not the start of an $aba$, and we can return home. If we get *another* $a$, then we may still be at the start of an $aba$ set:

Finally, we might exit with a $b$, followed by an $a$, which could be the beginning of a new set:

At this point, we are done. What we did not put in were the transitions to the garbage state, which are implicitly anything that wasn't yet defined. If we were to put them all in, we would have a graph that looks more like this:

Notice that one we get to state $g$, there is no way out, and no way to reach an accept state.
> 2 votes

# Answer
Amending @Choirbean's answer to accept $ababa$ and the like, a suitable regular expression is

$$(c \cup a (b a a^\*)^\*)^\*$$

This is abbreviated from the previous ...

$$(a \cup c \cup a (b a a^\*)^\*)^\*$$

... since the initial $a$ can be absorbed in the final $a (b a a^\*)^\*$.

We can now derive a compact set of right linear/regular equations:

$$\begin{align} Q\_0 &= (c \cup a (b a a^\*)^\*)^\*\\ Q\_0/c &= Q\_0 \\ Q\_1 &= Q\_0/a\\ &= (baa^\*)^\* Q\_0 \\ Q\_1/a &= Q\_1 \\ Q\_1/ba &= Q\_1 \\ Q\_1/c &= Q\_0/c \\ &= Q\_0 \end{align}$$

Where $\Sigma/\omega$ is those words $w$ for which $\omega w$ is in $\Sigma$.

* All the other transitions lead to $\varnothing$.
* The equations are equivalent to the DFA in @Choirbean's answer, though I've short-circuited the $ba$ transition through $Q\_2$.
> 1 votes

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: what are the BUS MASTERS in a processor?
I have multiple questions actually..

a)What is a System bus? Is there any other buses in the computer?

b)Is it always the case that , the processor access the memory via the system bus?

c) I read that " another master requests the access ".. What are these masters exactly? Is processor the bus master by default?

P.S. I am reading in the context of 8086 microprocessor

# Answer
(a) "System bus" was a common aggregation term for "data bus" and "address bus". There are a lot of other buses depending on your machine, e.g. between RAM and video card, or between SCSI controller and devices (hard disks, scanner, whatever).

(b) There's no such thing as "the" memory, it's a whole hierarchy of different memory systems, varying in speed/size/cost. For example, the fastest memory part are the on-processor registers. You can transport their content from and to the data or address bus (to move values to and from RAM), but for example the ALU won't access the registers via "system bus".

(c) Other devices which are able to "drive" the bus. For example, consider a SCSI controller, a scanner or a network card wanting to write something (a disk block, a scanned image, a received packet) to a previously assigned RAM area. Of course, the controller has to harmonize it's RAM access with the CPU. So the device will ask (via an extra control wire) to *grant the bus*, and wait. After the CPU acknowledges with a signal, the device becomes temporarily *bus master* and may use data and address bus exclusively (at least for some time), before it has to hand back control. As the CPU is present in every system, but (for example) a network card is not, it's a sensible design choice to make the CPU bus master.
> 1 votes

---
Tags: cpu
---


# Question
Title: Whats the logic between MAR, MBR and Control Bus
Control Unit has MAR and MBR registers. so MAR emits instruction to address bus so that the specific cell in the memory is activated. MAR also emits READ or WRITE command to control bus. MBR emit data for WRITE actions to data bus.

Question is how does the control bus communicate between MAR and MBR to know whether it is a write or read command. And once the cell is activated, how does data is being written or read?

I know CPU is smart... and computer bus is smarter... but there has to be logic to it...

# Answer
The RAM typically has a input pin called *MW* for "memory write" (maybe with inverted logic, then written with an overbar), to distinguish between read and write operations.

Control will probably use an extra wire to the RAM. In theory, you *could* use an usused high address bit for that, too, but I guess that would be considered to be a very questionable design - in fact "invalid" memory addresses are used for other strange things, like talking to non-memory devices such as line printers.

An address decoder will select the appropriate memory cell.

After that, the rest will depend on the *MW* bit... on the writing side, if it's static RAM (SRAM), you can use *MW* for enabling ("gating") the flipflop *S* (set) pin. On the reading side, you could use a transmission gate to connect or disconnect the RAM output from the data bus (logic gates won't do here, as the RAM output has to be *decoupled* from the data bus, unless you are actually reading values).
> 1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Is there an algorithm that given a PDA $M$ decides if there exists a string in $L(M)$ with a suitable decomposition?
I am looking for an algorithm that given a PDA $M$ decides whether there exists $w \in L(M)$ for which there exists a decomposition $w = uvxyz$ that satisfies $|vy| \geq 1$ and $uv^ixy^iz \in L(M)$ for every $i \geq 0$.

# Answer
> 2 votes
In a context-free language $L$, by the Pumping Lemma, there exists a $p \> 0$ such that every $w \in L$ such that $|w| \ge p$ admits a decomposition $w = uvxyz$ such that $uv^ixy^iz \in L$ for all $i \geq 0$.

If $L$ is infinite, it has words of length $\ge p$, and you can pick any of them. If $L$ is finite then no word satisfies the condition (this is not a contradiction with the pumping lemma, because the pumping lemma gives a length $p$ which is more than the length of any of the words in $L$).

It is decidable if a context-free grammar generates an infinite language (see e.g. Is it decidable whether a given context free grammar generates an infinite number of strings?).

Therefore the algorithm is

> On input $\langle M \rangle$, where $M$ is a PDA
>
> 1. Convert $\langle M \rangle$ to the description of an equivalent CFG $\langle G \rangle $
> 2. Check if $L(G)$ is infinite
> 3. If yes, then answer *yes* else answer *no*

---
Tags: automata, context-free, pumping-lemma
---


# Question
Title: What do the commas separating atomic events in a Relational Calculus formula means?
For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" operation? Or a natural join maybe?

# Answer
The notation is defined on page 17 and 18. The authors define a couple notations and state that they will "freely switch back and forth" between them. This example doesn't seem super-consistent, I'd expect $Q(x,x'):\\!\\!-\\,R(x),S(x,y),S(x',y),R(x')$ rather than an equals sign, but presumably it means $Q(x,x') = \exists y.R(x)\land S(x,y) \land S(x',y)\land R(x')$.

It doesn't really make sense to talk about *natural* joins in this context, as those rely on named attributes/columns. But yes, this query includes (equi-)joins. To be clear, the comma stands for conjunction. Any joining is implicit in duplicate uses of a variable. In particular, if all variables were used only once in the right hand side, then there would be no equi-joins, even implicitly. In SQL, the query would look something like:

```
CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
WHERE S1.Field1 IN (SELECT Field1 FROM R)
  AND S2.Field1 IN (SELECT Field1 FROM R)

```

or to be more systematic,

```
CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
INNER JOIN R AS R1 ON R1.Field1 = S1.Field1
INNER JOIN R AS R2 ON R2.Field1 = S2.Field1

```

or going a different direction,

```
CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1, S AS S2, R AS R1, R AS R2
WHERE R1.Field1 = S1.Field1
  AND S1.Field2 = S2.Field2
  AND S2.Field1 = R2.Field1

```
> 2 votes

---
Tags: database-theory, notation, relational-algebra
---


# Question
Title: A path modification problem in directed graphs
We start with a given finite directed graph. It could represent transitive relations such as:

* data transfer paths in social networks,
* transportation connections, etc.

Let us use the notation

* A-\>B to denote a directed edge from node A to node B and
* A=\>B to denote a path from A to B.

Example 1: Social networks. An edge A-\>B can mean: A can send data to B. So if we have edges A-\>B and B-\>C we have a path A=\>C and data can be sent from A to C.

Example 2: Rail connections. An edge A-\>B can mean: there exists a rail connection from A to B. So if we have edges A-\>B and B-\>C we have a path A=\>C and there is a rail connection from A to C.

We would like to locally modify the graph, in order to add or remove directed paths (not just edges). For example, we may wish to add or delete data paths or rail connections. We may wish to make it possible or impossible for C to receive data, directly or indirectly, from A. Or we may wish to make it possible or impossible to go by rail from A to C. We may have several (possibly conflicting) requirements such as these. Local modifications are rarely possible without implying other changes, some of which can be unwanted.

1. Adding paths. Adding a path X=\>Y, is simple because it is sufficient to add an edge X-\>Y. However by doing this we will also add paths from all Z such that Z=\>X to all W such that Y=\>W. Some of these paths may be unwanted. Is the addition of the new path important enough to justify the addition of some unwanted paths? Or: how can the new path be added with a minimal effect on the rest of the graph?
2. Removing paths. For example, if we want to remove a path A=\>C such as A-\>B-\>C we must remove either A-\>B or B-\>C. The removal of either edge may imply the removal of other paths that contains this edge. Hence the need of removing certain paths may force the removal of others, some of which can be wanted. Is the removal of the unwanted path important enough to justify the removal of the others? If there is a choice of paths to be removed, which ones to remove? Or: how can a path be removed with a minimal effect on the rest of the graph?

So in general, locally adding or removing paths can have ripple effects that can involve other paths, possibly the whole graph. After adding some paths, others should perhaps be removed and after removing some, others should perhaps be added. This becomes messy. If several path constraints are present, the problem may be infeasible. This could perhaps be seen as an optimization problem, where we must weigh the relative importance of paths: of those we explicitly want to add or remove and of those whose addition-removal may result.

This seems an interesting practical problem. How can this problem be formulated in a way that may lead to a solution? Has this problem, or similar ones, already been studied? I have found some literature on the problem of adding-removing *nodes*, but I have not found any on the problem of adding-removing *edges*. In any case, this problem is different, as we want to add-remove *paths*.

# Answer
> 0 votes
I am assuming you are using some lists of node pointers at the source nodes for keeping record of outgoing edges and paths.i.e. if you have a source node **A** which has directed edges towards the nodes **B**,**C** and **D** then you have a list containing pointers to **B**,**C** and **D** which is called $edges$ stored in node **A**

```
edges=[B,C,D];

```

and if some other edges lets say **E** ,**F** and **G** have a directed path towards them then you have a list of paths called $paths$

```
paths=[E,F,G];

```

Now let's say you want to delete the paths towards **E** and **F** from **A** then you should remove **E** and **F** from **paths** but still keep it in another list called $forbiddenPaths$.

```
forbiddenPaths=[];// this list will initially be empty

```

Here's how the lists will be updated after you have removed **E** and **F** from $paths$

```
edges=[B,C,D];
paths=[G];
forbiddenPaths=[E,F];

```

This way all you need to do before transmitting data is check if the destination node exists in the $paths$ list.If it does then transmit otherwise don't.You can also keep a $forbiddenEdges$ list in the same manner for avoiding some edges of your choice.

---
Tags: algorithms, graphs, routing, social-networks
---


# Question
Title: What is the difference between superposition and paramodulation?
I am currently writing a paper about automated theorem proving in first-order logic. Equality is not uncommon for mathematical problems and almost every theorem prover like VAMPIRE or SPASS has a calculus for equality. But the most paper are always writing about the term "superposition" calculus. A simple google search did not help to find any information about this term, only the wikipedia website which means "it can be used for first-order logic with equality".

Another paper referneced to the Paramodulation-based theorem proving which describes the concept of paramodulation for theorem proving. It seems that the superposition is some modified version of paramodulation, but I don't understand why and in which way.

So, is there any explanation of this calculus or can someone give me some hints what is different from paramodulation?

# Answer
This is late for you, but probably might be of help to others. I myself had asked this question and I wrote the summary of my findings to the acl2-help mailing list on 8 and 9 September 2013: https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00005.html https://utlists.utexas.edu/sympa/arc/acl2-help/2013-09/msg00006.html

Disclaimer: What follows is my understanding of the subject and I am not an expert.

I assume you are familiar with what is called term-rewriting. Informally its a very simple notion where one uses a rule to reduce or rewrite another expression.

A rewrite rule is usually a universally quantified formula of the form $C \Rightarrow l=r$, where $C$ is a formula and $l$ and $r$ are terms. One says that a rule $R$ applies to another formula $\Phi$, if there is some subterm $s$ of $\Phi$ and some substitution $\sigma$ such that $l\sigma = s$ (this process is called matching) and $C\sigma$ is true. If $R$ applies to $\Phi$, then one can rewrite $\Phi$ to $\Phi\sigma$. Demodulation is another name for unconditional term-rewriting, i.e., $C$ is simply true and so $R$ is just $l=r$.

Rewriting involves matching,i.e., one-way unification. Paramodulation involves full unification. Moreover, the equality ($l=r$) that is used to perform paramodulation, is not directed, either lhs or rhs can be unified with a subterm in the other literal paramodulated upon.

Superposition is a restriction of Paramodulation. In particular, the rules of inference named 'Superposition (left/right)' are restrictions of "ordered" paramodulation, i.e., the paramodulation rule is applied only when equation $l=r$ (to be instantiated/unified) satisfies certain properties: $l \>\> r$ for a given reduction order $\>\>$, $l=r$ is maximal (wrt $\>\>$) in the clause etc etc.

Here are some fundamental papers that are interesting from a historical point of view.

\[1\] The concept of demodulation in theorem proving - L Wos, GA Robinson, DF Carson, L Shalla - Journal of the ACM (JACM), 1967

\[2\] Handbook of Logic and Automated Reasoning - J Harrison.

\[3\] Paramodulation and theorem-proving in first-order theories with equality- G Robinson, L Wos - Machine intelligence, 1969

\[4\] Rewrite-based equational theorem proving with selection and simplification - L Bachmair, H Ganzinger - Journal of Logic and Computation, 1994

\[5\] Simple word problems in universal algebras - DE Knuth, PB Bendix - Computational problems in abstract algebra 1970

\[6\] A superposition oriented theorem prover - L Fribourg - Theoretical Computer Science, 1985 - Elsevier

\[7\] Completion without failure - L Bachmair, N Dershowitz, DA Plaisted -1989
> 5 votes

---
Tags: first-order-logic, automated-theorem-proving
---


title: Finding the bandwidth of a band matrix

text:
# Question
Title: Finding the bandwidth of a band matrix
I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the efficiency of the algorithm, I am trying to exploit the sparsity of the matrix by finding its bandwidth, but I have to run through the matrix a lot of times to find it, and it is taking too long.

The main idea I am using to find the bandwidth is:

* for each row, find the start(row) and end(row): these are the intervals in which the elements are different of $0$;
* to find start(row): iterate from the beginning of the row until the element is not $0$;
* to find end(row): iterate from the end of the row until the element is not $0$;

The problem is that I am running through many unnecessary $0$'s, but I can not figure out how to avoid this and guarantee a solid result. Thanks.

# Answer
> 1 votes
As a sparse matrix is mostly made of zeros. Using a 2-dimensional array for all elements will be an inefficient way to represent such data as more than half of the array will be zeroes which is the reason for the increased time cost for finding bandwidth in your case.

In your case if you have a matrix $M$ of size $n * m$ then you'll be using a 2 dimensional array of size $n\*m$. However it is not necessary to do so

A more efficient way will be to represent only the non zero elements using a 2 dimensional array with only three columns.e.g.

```
------------------------
 R    |   C    | V
------------------------
 0    |  0     |  1
------------------------
 0    |  3     |  4
------------------------
 1    |  5     |  11
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .

```

Where **R** is the row of the nonzero element,**C** is its column and **V** is its value in a given matrix.

In this way if you have $t$ *nonzero elements* in the **Matrix** then you need to access only $3\*t$ elements in the above 2-dimensional array.

Now you can find the maximum and minimum values of **C** for any row **R** and can calculate their difference.

The largest difference you'll come across will be the bandwidth.I hope it makes sense.

---
Tags: algorithms, linear-algebra, matrices, sparse-matrices
---


# Question
Title: Construct a proof tree in Hindley-Milner with function overload
I'm reading Wadler's paper called "How to make adhoc polymorphism less ad hoc". I'm trying to understand the given rules for function overload (over and inst) and I want to create a small example of a proof tree using them. All deductions rules are in Figure 9 and Figure 10.

I decided to proof the following expression/type: $(over\\: eq:: Eq\\: \alpha\\: in\\: inst\\: eq :: Eq\\:Int \\:=\\: eqInt\\: in\\: eq\\:1\\:2)::Bool$.

Some people gave me a tip: construct the tree in bottom-up.

So here is what I did:

I think I'm stuck. I have no idea how to go up in the tree. And I'm not sure if I can, at some point, discharge the assumption about $eqInt$.

I would like to know what I'm doing wrong and how to finish this proof.

---

EDIT: As said in the paper, $Eq\\: \tau$ is a abbreviation for $\tau \rightarrow \tau \rightarrow Bool$.

# Answer
After some time I realized that is not possible to proof \begin{align\*} \vdash (over\\: eq:: Eq\\: \alpha\\: in\\: inst\\: eq :: Eq\\:Int \\:=\\: eqInt\\: in\\: eq\\:1\\:2)::Bool \end{align\*} without suppositions about $1$, $2$ and $eqInt$ ( $\emptyset$ as the context). They need to be bound to the context , because they should be seen as build in to the system. In alternative I could create new rules (like $const$ rules) for the integer numbers ($1$, $2$...) and for $eqInt$, that don't insert stuff to the context.

So, my final result is this proof tree:

I'm not sure if I can use $weakening$ in the context, but I did.

I hope that some one could comment something about my answer. If I'm right or if I created some non-sense.
> 1 votes

---
Tags: type-theory
---


title: Efficient N-Ary GCD Algorithm

text:
# Question
Title: Efficient N-Ary GCD Algorithm
Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for exactly two input values? E.g. `gcd(a, b, c, ...)` vs. `gcd(a, gcd(b, gcd(c, ...)))`

If so, then what is such an algorithm?

If not, then is it known whether there cannot exist such an algorithm?

# Answer
As Wikipedia reports, the fastest currently known algorithm for the gcd of two $n$-bit numbers runs in $O(n f(n))$ time where $f(n)$ is a slow-growing function of $n$ (roughly $\log n \cdot \log \log n$). It is not known whether the gcd of two $n$-bit numbers can be computed in $O(n)$ time.

This means that the iterative algorithm for computing the gcd of $k$ $n$-bit numbers (as described in the question) runs in $O(kn f(n))$ time. Obviously, any algorithm needs at least $\Omega(kn)$ time -- this lower bound follows from the fact that any algorithm needs to read the entire input. This doesn't leave much of a gap between the trivial lower bound and the running time of the iterative algorithm. In other words, it doesn't leave much room for improvement in running time.

---

That's the theoretical answer. From a pragmatic perspective, the $O(n f(n))$-time algorithms only become faster than (asymptotically slower) alternatives once $n$ is fairly large. As a result, if $n$ is not too large, these results might not mean much.

Also, from a pragmatic perspective, we can expect that $\gcd(a,\gcd(b,\gcd(c,d)))$ might be faster than $\gcd(\gcd(a,b),\gcd(c,d))$. They both yield the same answer, but the former might often be faster, because typically one of the two arguments to the gcd will be small. Computing $\gcd(x,y)$ might be faster in practice if $y$ is much smaller than $x$ (because the first step is to replace $y$ with $y \bmod x$) than when $x,y$ are about the same size. So, you might benefit by performing the gcd's in an order that gets you down to a small number as soon as possible.
> 2 votes

# Answer
The runtime of gcd depends on the size of the result relative to the size of the inputs, especially the smaller input.

If you start with inputs of equal size, the runtime depends on the ratio between inputs and final result. Best to calculate x = gcd (a, b), y = gcd (x, c) and so on.
> -1 votes

---
Tags: algorithms, runtime-analysis, number-theory
---


# Question
Title: Is there any K-means analog for regression, not culstering?
Good day Is there any regression Machine learning model, based on k-means? Example (Zillow's Zestimate): I have a lot of houses(with features like sq.feet and location) and prices. I want to estimate price for a new house by averaging k neighbors.

# Answer
> 2 votes
You could use $k$-nearest neighbors regression. It's not based on $k$-means, but it is based on estimating the price of a new house by averaging $k$ neighbors (in particular, the $k$ most "similar" houses in the training set, for some measure of similarity that you define). $k$-nearest neighbors is supported in many machine learning toolkits.

See https://en.wikipedia.org/wiki/K-nearest\_neighbors\_algorithm.

---
Tags: algorithms, machine-learning
---


# Question
Title: Why shuffling by picking random position in all array instead of a part is not correct
There is a famous problem to generate a random permutation of elements in an array - it's called *shuffling*. My understanding of that problem is that I have to put every element in an array into a random position. So for each element in an array I can generate a random position and put it there by swapping:

```
for (let i = 0; i < a.length; i++) {
    const position = rand.nextInt(a.length);
    const tmp = a[i];
    a[i] = a[position];
    a[position] = tmp;
}

```

This is almost what the improved Fisher–Yates shuffle algorithm is doing. However my solution is not correct. According to the link I need to generate numbers from the `0..i` range, not from `0..length`. Can anyone please explain me why it is so?

In my implementation all the numbers are still put into random positions, so what's the problem?

# Answer
There is a simple mathematical argument that your algorithm *cannot* pick each permutation with equal probability: There are $n^n$ possibilities how your algorithm can choose random numbers, each with equal probability, and each producing some permutation. There are $n!$ possible permutations. But $n^n$ is not divisible by $n!$ if $n ≥ 3$, therefore the permutations cannot all be the result of the same number of random choices.

Yuval gave the example for n = 3: There are $3^3=27$ possible choices of random numbers, and $3! = 6$ possible permutations. $27/6 = 4.5$. It is not possible that each permutation is the result of 4.5 different choices of random numbers. As Yuval's table shows, there are three permutations each being produced by 4 and by 5 choices of random numbers, so some permutations *must* be more likely than others.

For n = 2 this argument doesn't show any problem since $2^2 = 4$ is divisible by $2! = 2$, and indeed the algorithm produces a random permutation.
> 3 votes

# Answer
Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$. Therefore your algorithm could work only if $n^n/n!$ is an integer, which is only the case when $n \leq 2$.

More concretely, if you shuffle the array $1,2,3$, then you get the following results: $$ \begin{array}{c|c} \text{array} & \text{probability} \\\hline 1,2,3 & 4/27 \\ 1,3,2 & 5/27 \\ 2,1,3 & 5/27 \\ 2,3,1 & 5/27 \\ 3,1,2 & 4/27 \\ 3,2,1 & 4/27 \end{array} $$
> 9 votes

# Answer
Well, you are putting the numbers in random positions, although this is not the correct implementation of Fisher–Yates shuffle algorithm (if you intended to). You are basically using a slightly different algorithm such that:

If **n = a\[i\]** is swapped with **m = a\[position\]**, the algorithm can still generate **position = i** and swap **m = a\[i\]** with another number **a\[i+1\]**. In Fisher–Yates shuffle algorithm this wouldn't happen as it would use **i+1 ... a.length-1** as possible values for **position**. So **m** wouldn't be swapped again.

EDIT: You should also check this question and understand the concept of **uniform shuffle**.
> 1 votes

---
Tags: algorithms, arrays, randomized-algorithms
---


# Question
Title: Flipping all incoming/outgoing edges from a vertex in a DAG
I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that resulting graph is still a DAG. Am I correct?

# Answer
> 2 votes
This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus.

Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal):

1. After flipping all incoming(outgoing) edges from vertex `v` in a DAG `G`, we get another graph that is not a DAG (it has a cycle).
2. Since we only changed the direction of the vertices incident to `v`, the only way we loose the acyclic property is if there is a new cycle going through vertex `v`.
3. Since we flipped directions of all incoming(outgoing) edges from vertex `v`, all edges incident to vertex `v` are now outgoing(incoming), so it is not possible for any cycle to go through vertex `v`, which contradicts 2.

---
Tags: graphs, dag
---


# Question
Title: Representing Integral domains in computer memory?
Earlier I wrote this question about an algorithm computed on an integral domain. However as commented I didn't suggest any particular ways of storing an integral domain in computer memory. I set out to do this but found it a particularly difficult task.

It is in fact impossible to store all the integral domains in memory because the fields are uncountable1 and are a subset of the integral domains. However I am not concerned with fields because they don't have any primes anyway.

How might one represent non-field integral domains in computer memory? Is the set of all non-field integral domains countable? If it is uncountable is there any useful subset of them that can be represented in computer memory?

1: The rationals are a field. Every polynomial extension of a field is also a field. Thus the number of polynomial field extensions of $\mathbb{Q}$ is the powerset of the irreducible polynomials on $\mathbb{Q}$ which is uncountable.

# Answer
In general this question has no precise answer: the class of integral domains is not even a set, much less a countable set! (For example, for each set $A$, we can find an integral domain $D\_A$ larger than $A$, e.g. $\mathbb{Z}\[A\]$, which is sufficient to show that integral domains can't be all gathered into a set).

In general you need to specify *something* to describe the elements of the set, and how to compute multiplication and addition.

A popular choice, which covers a large portion of the interesting examples, is to take a known ring or field $R$, typically $\mathbb{Z}$ or $\mathbb{Q}$, or some finite field $\mathbb{F}\_q$, and look at some quotient ring of the form $D = R\[X\_1,\ldots,X\_n\]/(P\_1,\ldots,P\_k)$, where the $P\_i$ are polynomials in the $X\_j$.

Now it's not even clear that $D$ is an integral domain, which is equivalent here to the fact that $I=(P\_1,\ldots, P\_k)$ is irreducible. This can be determined using the Gröbner basis method as explained here.

Now there is an obvious representation for the elements of $D$: every element is represented by a polynomial, which we know how to represent, and do addition and multiplication on. The only issue is equality, since it needs to be modulo $I$. But this also is possible using known techniques, similar to the Gröbner basis ones.

It would be great if someone had implemented all of this up somewhere, though. Oh but they have! The Sage mathematical software toolchain builds on all of these observations to offer a ton of ways to concretely work with these kinds of rings. They even have an `is_integral` method for quotient rings!

Sage is a fantastic piece of software that I highly recommend, which probably does a lot of what you want.
> 3 votes

---
Tags: group-theory
---


# Question
Title: Why aren't computables used for numerical calculations?
In programming languages like Haskell you can use lazy evaluation to delay calculations.

Why isn't a similar approach being used for numerical methods (I understand that there would be memory implications).

The approach would be that non-integer values would be stored as how they are calculated, so that the next digit can be found when requested.

This kind of approach should allow every value to be calculated to the correct number of significant figures.

Sorry that this is slightly garbled.

# Answer
A similar approach *is* used, and in Haskell! Here is a page with some references:

https://wiki.haskell.org/Exact\_real\_arithmetic

Great minds think alike. As David Richerby notes, exact computation on reals is *astronomically* slower than with machine-backed floats, which are probably here to stay.

See also this question:

https://cstheory.stackexchange.com/questions/32011/computation-of-reals-floating-point-vs-tte-vs-domain-theory-vs-etc
> 2 votes

# Answer
It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased precision. But, for almost all applications, 64-bit floating point is more than enough and the speed of being able to do calculations with single CPU (or GPU!) instructions is a huge win.
> 6 votes

# Answer
This probably isn't exactly what you're looking for, but perhaps nevertheless interesting.

There have been proposals for different kinds of computables, for example these by Bill Gosper: Continued Fraction Arithmetic (hardware support is described at the bottom, for Continued Logarithms).

Doing calculations in software with continued fractions has seen many implementations, though they frequently have trouble computing anything that results in an exact integer, evaluating an infinite number of terms in an attempt to find the next digit but never finding anything because the number "ended", a condition which is impossible to test for with "black box" generators (which has a strong "neatness" appeal): given two black boxes that *just happen* to represent the same infinite CF, there is no way to tell whether they're actually the same or diverge after the billionth term. Lazily generated infinite lists of digits have the same problem and, on top of that, have to be *actually* infinite more often than CFs (which can represent anything in $\mathbb{Q}$ with finitely many terms).

Apart from that, such symbolically-represented CFs suffers the more obvious problem that building up a big computation symbolically takes a lot of memory, and evaluating a big structure is inherently slow. The slowness can be mitigated to some extend by "merging" the main calculation "boxes" when possible. Eg `(x + 3)(y + 4) / (x - y)` can be evaluated with one "box", which can be computed from the "boxes" that implement the sub-expressions, but even if everything merges down to one "box", each merge is slower than a typical hardware-implemented floating point operation and there's the final evaluation to worry about too.

It is possible to speed it up by periodically converting the symbolic representation to an approximate explicit one, but then it loses most of the appeal - both the exactness (even for rationals!) and the lazyness are sacrificed, leaving behind something that doesn't seem so interesting anymore.

The Continued Logarithms proposed by Gosper have even been implemented in hardware, though as far as I know it has never become more than a curiosity.
> 4 votes

---
Tags: enumeration, numerical-algorithms
---


# Question
Title: Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function
A boolean-valued function defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n\_{min}\le n \< n\ast\\1, &n\ast\le n\le n\_{max} \end{cases} ; n \in \mathcal Z $$

$f(n)$ is computationally expensive and it's analytical form (a closed-form equation producing these binary-valued outputs is unknown, since it is the result of a time-domain simulation of complicated system of non-linear PDEs meeting certain exit conditions etc.). Furthermore, $\frac{\partial{f}}{\partial{n}}$ is also obviously not available.

The goal is to compute $n\ast$, i.e. the first occurrence of the integer-valued function input, $n$ that produces a Boolean $1$. Needless to say, this can be trivially achieved in computer code by using a simple $for$ loop and rejecting the values of $n$ one by one, until we hit $n\ast$.

The lower and upper bounds, $n\_{min}$ and $n\_{max}$ are known apriori.

However, given the expensive nature of computing $f(n)$, I am looking for an efficient algorithm beyond this naive implementation, especially one that requires small number of function evaluations. A pseudo-code implementation of your proposed solution would be much welcome too.

A conceptual schematic/visualisation of the problem is also shown here, purely to aid the understanding of the task at hand

# Answer
Use binary search.

You know that the correct value is somewhere in the range $\[n\_\min,n\_\max\]$, so pick $t = \lfloor (n\_\min+n\_\max)/2 \rfloor$ (the point halfway in the middle), and evaluate $f(t)$. This will either tell you that $n^\*$ is in $\[n\_\min,t\]$ or that $n^\*$ is in $\[t+1,n\_\max\]$. Now you can repeat on the smaller interval. Each time, the width of the interval decreases by a factor of two, so after $\lg (n\_\max-n\_\min)$ iterations, you will find the correct value of $n^\*$. This is much faster than trying all $n\_\max-n\_\min$ possible values of $n^\*$.
> 2 votes

---
Tags: optimization, search-algorithms, integer-programming, binary-search
---


title: how is data in a tree stored in memory?

text:
# Question
Title: how is data in a tree stored in memory?
I am not so familiar with trees.

How is a tree stored in memory? what is the data structure type used for storing it?

As a string?linked list? stack (!)?

Or is there some kind of data storage model for trees?

# Answer
Usually it's stored as an adjacency list. Which is basically a linked list for every single node. So the linked list of a node `u` contains every node `v` such that `(u,v)` is a valid edge of the tree.

The adjacency list of this tree would be:

```
 1 ->
 3 -> 1, 4
 4 ->
 5 -> 3, 8
 7 ->
 8 -> 7, 10
10 ->

```

It can also be stored using an adjacency matrix. But that's used when the nodes of the tree are less (since it requires more memory). Adjacency list is better for sparse graphs.
> 3 votes

# Answer
the simplest data representation is Nodes and Links; so a list of Nodes such as 1,2,3,4,5, and a list of links such as 1:2, 1:3, 2:4, 2:5 would represent the tree below:

```
        1
      /  \
     2    3
    / \
   4   5

```

This data representation also allows additional meta-data to be defined and stored at any of the elements \[ie Nodes\], or relationships \[ ie Links\] For example: Age of a node can be added as an Attribute. or PostalAdress of Node can be added as a set of attributes \[ie Struct\] Beyond that Nodes can be typed, and Links constrained or defined to link certain types only - and hence may carry different set of attributes depending on type of link or types of Nodes joined by that type of link. Traversing the tree is following it from any node in any direction . In reverse directions we would optimize by storing the Link 1:2 as well as the alt-Link 2:1 .
> 3 votes

# Answer
It depends on what data structure you want to represent it with.

I'll illustrate how it's represented and how it's stored in memory for a linked list implementation.

```
             Linked-list representation of the tree on the left.

```
* The left link points to the first node in the linked list of its children

It's clear the root node has three children, so the left link point to its first child, whose right link points to the 2nd and 3rd children, and so for the other sub-tress.
* Right links of nodes point to siblings

The right link of the first child points to its next siblings and so on (am considering from left to right).

That's how they are stored in memory for this implementation. And hence the binary tree can be traverse. eg, in-order (visit the left sub-tree, then the parent node, and then the right sub-tree) this is done recursively.
> 2 votes

---
Tags: data-structures, trees
---


title: Link-cut trees: how to code cut(u,v)

text:
# Question
Title: Link-cut trees: how to code cut(u,v)
In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree.

The pseudo-code and code for this is:

```
cut(x):
   access(x);
   parent(left(x)) = null
   left(x) = null

void cut(Node *x){
   access(x);
   x->left->parent = 0;
   x->left = 0;
}

```

> How can we define cut(u,v) for an arbitrary (u,v)?
>
> I.e. how can we code cut(u,v) in such a way that
>
> 1. If (u,v) is not an edge in the represented tree, then do nothing;
> 2. If (u,v) is an edge of the represented tree, cut the edge in the represented tree.

The following function may help, it determines the root of the represented tree that contains the node x.

```
root(x):
   access(x)
   while(left(x) =/= null)
      x = left(x)
   splay(x)

LCT *root(LCT *x){
   access(x);
   while((*x).left != NULL){
       x = (*x).left;
   }
   splay(x);
   return x;
}

```

Additional reference (code): https://github.com/saadtaame/link-cut-tree

Thanks in advance.

# Answer
The function $cut(v)$ is only defined for cutting $v$ from its parent for a reason, because this is the **only** possibility. The *represented tree* is first and foremost a **Tree**. By definition, edges will only exist from a parent to a child. Therefore, the only edge you would ever need to cut is from parent to child.
> 2 votes

---
Tags: data-structures, trees, search-trees, balanced-search-trees
---


title: Some problem about regular language

text:
# Question
Title: Some problem about regular language
Let's say $\alpha$ is *simple* word if it couldn't be represented as $\beta^{n}$($n$ times concatenation of $\beta$), where $\beta \ne \alpha$

Consider two sets: $p\_{N}(L) = \\{\alpha^{n} | \alpha \in L ; n \in N\\}$ and $SL = \\{ \alpha | \alpha$ - simple word, $\alpha^{n} \in L; n \ge 1 \\}$, where $N \subset \mathbb{N}$.

Prove that $p\_{N}(L)$ is regular language if and only if $SL$ is finite.

As I said in comment , possibly we could make a contradiction about finiteness of $SL$, when $p\_{N}(L)$ is regular. For example , we could construct a word , which doesn't apply $p\_{N}(L)$.

# Answer
> 2 votes
Please have a look at the paper *Roots and Powers of Regular Languages* by Horváth, Leupold and Lischke (DLT 2002, LNCS 2450, doi 10.1007/3-540-45005-X\_19) which states in the abstract:

> For a set $H$ of natural numbers, the $H$-power of a language $L$ is the set of all words $p^k$ where $p \in L$ and $k \in H$. The root of $L$ is the set of all primitive words $p$ such that $p^n$ belongs to $L$ for some $n \ge 1$. There is a strong connection between the root and the powers of a regular language $L$ namely, the $H$-power of $L$ for an arbitrary finite set $H$ with $0, 1, 2 \notin H$ is regular if and only if the root of $L$ is finite.

Note the special provision for the numbers $0,1,2$.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Does proofs are programs apply to any functional program?
Does Curry howard correspondence, apply to all Functional Program, e.g. in Haskell. i.e. Is it possible to write Equivalent Haskell programs, to COQ proofs?

# Answer
In Haskell there are *more* programs than there are Coq proofs because Haskell has general recursion whereas Coq does not. (In fact Coq allows you to extract proofs into Haskell code.)

The reason that Coq does not have general recursion is that with it we can "prove" anything, simply by saying "to prove $t$ just make a recursive call to itself":

```
proveAnything :: t
proveAnything = proveAnything

```

In some languages, for instance in OCaml, you can't do it this way so you have to go indirectly through a recursive function call:

```
let rec proveAnythingAux _ = proveAnythingAux ()
let proveAnything = proveAnythingAux ()

```

This shows that type theory can be used for many things, two of which are *programming* and *logic*. The difference between these two is general recursion: we want it in programming but it makes logic inconsistent.
> 2 votes

# Answer
The Curry-Howard correspond is an observation that the structure of type systems mirrors the structure of logics, specifically propositions. Under this view, we can see similarities between an expression of a certain type, and a proof of a proposition.

Of course, there are many type systems (and logical systems) under the sun, and it is not an *exact* correspondence. Some type systems are stronger than other. Some languages that call themselves functional don't even have type systems (e.g. Lisp).

Moreover, the mapping is not always intuitive: what does it mean to say that the type of natural numbers is a proposition? It would be more accurate to say that *some* types can be considered propositions.
> 0 votes

---
Tags: functional-programming, interactive-proof-systems
---


# Question
Title: How does RAM is shared in multi core environment?
I learnt that multi core processors have more than one processing units( i.e. the main executing units ALU etc.) and they are better at performance. I want to know how they share Physical memory. I'll take following example to make my question clearer - Say, There is a memory location M in physical memory and Two threads T1 and T2 running on different cores. Is it possible for T1 and T2 to access M at the same instance of time or do they have to wait for one other to complete access i.e. do they share the same memory bus so that they have to wait, for one another or Can they read M at same instance of time from two different memory buses? If former is the case, There is not much performance gain right, as they have to wait for memory bus to be free?

Summarising, Are memory operations independent of other cores or each core can only make a physical memory access when memory bus is free?

# Answer
> I learnt that multi core processors have more than one processing units

Well having more than one processing unit is something present even outside multi-code processors. Processors which are able to start the execution of several instructions in the same clock cycle are called super-scalar (the first super-scalar processor of Intel in the x86 family is the first Pentium).

Multi-core processors are in fact several processors on the same chip. (Sharing between cores is limited to cache, when sharing more you have architectures called with names like SMT -- simultaneous multi-threading -- or hyperthreading -- which is the name Intel is using).

> I want to know how they share Physical memory.

Modern processors have usually cache (in the x86 family, that started again in the early 90's) so when a core need data, it is usually fetched from the cache without needing to access the main memory. There is several levels of cache. The lowest one being used only by a core. The other can be shared (and how depend on the details of a given model, for example you can have a four core processors with level 2 caches shared between 2 cores).

> There is not much performance gain right, as they have to wait for memory bus to be free?

If one need to access the main memory, it's slow (my rule of thumb: level 1 cache access is 3-5 cycles, level 2 is 20-25 cycles, main memory is 100-150 cycles but again details may vary and I've not looked at them recently).
> 3 votes

# Answer
Memory access is *not* fully independent.

As long as the cores work on different memory ranges (with distance considerably larger than the size of a "cache line", which caches consecutive memory values), coordinating bus access would be the only problem... in theory.

In practice, cores (usually) have some local caching memory. This leads to two subproblems.

1. If core A is writing to address X, the update might get stuck (for some time) in the local cache of A. Core B, using address X one moment later, might or might not get the updated value at X. A simple solution might be to *write through*, i.e. to commit write operations immediately to the RAM. Of course this will lead to degraded performance.
2. Even if the processor is using *write-through*, core B already might have the contents of cell X in its local cache... this is, the outdated contents. Therefore, core B cache has to *snoop* on the address bus. Whenever there is write(!) access to a memory cell which is cached locally, core B has to mark the pertaining cache lines as "invalid". This is usually done at cache-line level, not on byte-level. This will further degrade performance.

Imagine to tell core A to write some bytes to all the odd, and core B to write to the even addresses *in the same range*. The accesses are disjunct, the result is well-defined, but performance will be *dramatically* worse than doing the same operation on a single core.

Cores perform best if operations involve local data (e.g. register operations), and, at large, memory accesses do not overlap.
> 4 votes

---
Tags: memory-management, memory-access, threads, cpu
---


# Question
Title: Proving the algorithm that orders an array according to the specified positions
I have the following task:

> Given an array `a` holding positions and array `b` holding values, order the elements in the array `b` according to the positions in the array `a`. For the input:
>
> ```
> a = [3, 0, 1, 2];
> b = ['a', 'b', 'c', 'd'];
>
> ```
>
> the output should be
>
> ```
> [ 'b', 'c', 'd', 'a' ]
>
> ```

I have written a simple algorithm which simply an item into the specified position by swapping:

```
// a.lenght -1 since the last element will end up in the correct vacant position
for (let i = 0; i < a.length - 1; i++) {
    const position = a[i];
    swap(b, i, position);
}

```

Although I've tested it and it seems to produce correct results, I can't figure how to prove it works correctly. Can anyone please help with reasoning?

# Answer
You can't prove a false statement to be true :P

Consider this example:

```
a = [1, 2, 0]
b = ['a', 'b', 'c']

```

Output should be:

```
b = ['c', 'a', 'b' ]

```

But your algorithm will output:

```
b = ['c', 'b', 'a']

```

This because when you swap an element in its "final" position `a[i]` it's possibile that in one of the next loops that element will be swapped again.

To solve this problem think about swapping `a[ ]` elements too. :)
> 3 votes

# Answer
Let us run a test case on your algorithm.Let us have two arrays

```
a=[1,6,3,4,7,2,0,5];
b=[b,g,d,e,h,c,a,f];

```

As you can see that each element in array `a` is actually the index if there was an array `[a,b,c,d,e,f,g,h]`. So the output should produce them in the order a,b,c,d,e,f,g,h

But here's the output of your algorithm At `i=0` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[g,b,d,e,h,c,a,f];

```

At `i=1`

```
a=[1,6,3,4,7,2,0,5];
b=[g,c,d,e,h,b,a,f];

```

At `i=2` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[g,c,e,d,h,b,a,f];

```

At `i=3` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[g,c,e,h,d,b,a,f];

```

At `i=4` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[g,c,e,h,f,b,a,d];

```

At `i=5` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[g,c,b,h,f,e,a,d];

```

At `i=6` you get the output

```
a=[1,6,3,4,7,2,0,5];
b=[a,c,b,h,f,e,g,d];

```

At `i=7`

```
a=[1,6,3,4,7,2,0,5];
b=[a,c,b,h,f,d,g,e];

```

If your algorithm was correct then at `i=7` the output should be

```
a=[1,6,3,4,7,2,0,5];
b=[a,b,c,d,e,f,g,h];

```

So the algorithm doesn't work.
> 0 votes

---
Tags: algorithms, arrays
---


title: L* is in P but L is not?

text:
# Question
Title: L* is in P but L is not?
I am trying to show that $L^\* \in P $ does not necessarily mean that $L \in P$. My idea was to find a language $L \notin P$ , apply $\*$ operator and show that $L^\* \in P$ by showing that $L^\*$ can be decided with a polynomially bounded Turing machine, which will be a contradiction to $L^\* \in P \Rightarrow L \in P$. However, I am having trouble in finding such $L$. Is there a trivial $L$ that I'm not thinking of? Or should change my method? Any help will be appreciated.

# Answer
Yes, your method is fine and, yes, there's a fairly trivial way to complete your proof attempt: it's easy to arrange that $L^\*=\Sigma^\*$, which is in **P**.
> 2 votes

---
Tags: complexity-theory, turing-machines, time-complexity
---


# Question
Title: Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)
given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove correctness?

Any help appreciated.

Thanks!

# Answer
From the NFA $N$ construction an equivalent context-free grammar $G$ using the standard construction for this, and then construct a PDA $M$ such that $L(M) = L(G)$. The standard construction will (given a suitable definition of the notion of pushdown automaton) give us an automaton with three states only.

The automaton will simulate the leftmost derivations of $G$, and its stack symbols include the set $V$ of nonterminals and the set $\Sigma$ of terminals as well as a bottom marker $\\$$. Initially, $\\$$ is placed on the stack together with $S$. The main loop of the automaton is that involving the state $q\_2$: If a nonterminal $A$ appears as the topmost symbol on the stack and there is a production $A \rightarrow w$ in $G$, then $A$ is replaced by $w$ in reverse. If a terminal $a$ appears as the topmost symbol on the stack and the next input symbol to be read is also $a$, then the automaton proceeds. Finally, if all input characters have been read and the bottom marker is the only symbol on the stack, the computation succeeds.
> 1 votes

# Answer
The idea of the construction is to keep the current state as the symbol at the top of the stack. At each step, you pop the symbol at the top of the stack (the current state) and read a single character, and push the state to which the DFA transitions to the stack.

I leave the rest of the details to you.
> 0 votes

---
Tags: finite-automata, pushdown-automata
---


# Question
Title: How to enhance my skills as a programmer
I want to learn Cryptography and so I am interested to master C-programming.

I know the basic concepts of C-programming like how to use an array,pointers etc.

I want to develop myself so that I can find the different loopholes in the security of different cryptosystems.

Basically I want to work in Attacking of Cryptosystems apart from developing my skills in theory.

Will someone suggest me some goods or a list of books(say) which are just above the beginner's level and which will establish me as a good programmer?

I will be extremely thankful if someone could help.

# Answer
## Cryptopals challenges

I would really suggest going over the practical exercises on http://cryptopals.com/ which will (hopefully) illustrate practical known weaknesses of existing cryptosystems and ways to attack them.
> 2 votes

# Answer
You don't need books. You need to **write lots of programs**. Since you are interested in cryptography, you should practice writing programs that involve mathematics. A good way to do so is to join Project Euler and just go down the list. Good luck!
> 3 votes

# Answer
You may wish to investigate cyberdegrees

There is a wealth of information on this site including free online courses.
> 1 votes

---
Tags: programming-languages, books, c
---


# Question
Title: Random function "returns a uniformly distributed int". Does this mean the probability of every number is the same?
Most functions that generate random numbers are described as:

> Returns a pseudorandom, **uniformly distributed** int value between 0 (inclusive) and the specified value (exclusive)

If I use it to generate a number in the range `[0..9]`, does **uniformly distributed** mean that the probability for `3` and `8` is the same?

As I understand it, if I run the function a sufficient number of times, I'll have the same number of occurrences for each number, 0 through 9. Is this correct?

Alternatively, would we instead have a **normal distribution** where we would get more occurrences of the numbers 4, 5, and 6, as they are closer to the mean and hence have a higher probability of occurring?

# Answer
Uniform distribution is when all values have the same probability. A random uniformly distributed integer in the range $0,\ldots,9$ will attain each of the values with probability $1/10$. In practice, you function is not truly random but only pseudorandom, so the probabilities won't be exactly $1/10$ but only very close to $1/10$.

Normal distribution is a probability distribution on real numbers. If we "bin" them then we get a normal distribution on the integers. If we "cap" it (there are several ways of doing this) then we get a probability distribution on a finite set of integers.
> 3 votes

---
Tags: algorithms, randomness
---


# Question
Title: What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list
Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - `head` and `tail`. I've implemented the same functionality as a circular linked list using only one pointer `tail`. I'm wondering what's the advantage of two pointers versus one in a circular list. It takes more space as I understand so why did they choose this implementation?

# Answer
If you're not using a circular list, then you *must* have a pointer to `head` and `tail` to achieve $O(1)$ enqueue and dequeue. Furthermore, if it is not a circular list *and* not a doubly-linked list, then without a pointer to `head`, we can't enqueue!

Some picture might help a little too.

1. Single Linked List with only `tail` pointer:

There's no way to get back to the head to enqueue! We would have to remedy this with a pointer to the `head`.
2. Doubly Linked List with only `tail` pointer:

We can get back to the head, but at an $O(n)$ cost, we might as well just add another pointer to `head` for convenience.
3. Single Circular Linked List with only `tail` pointer:

We can get back to the head in $O(1)$! This is a good shortcut. In circular linked lists this node can sometimes implemented as a Sentinel Node which does not contain any information but works as a separator between the head and tail of the queue.

In terms of additional space, adding `tail` or `head` or both is almost negligible. The nodes will be taking up memory no matter what, it's just whether or not you use a variable to reference them. Using a circular linked list kind of acts like a `head` pointer if you think about it. `tail.next` would be a synonym for `head`, so it's not really saving space, nor is it really costing much space.
> 2 votes

# Answer
One possible advantage is that it is a little easier to understand how the push and pop operations work with a doubly-linked list. The use of a singly-linked circular list is not *that* much harder to understand, but it *is* a trick, and at this stage where it's the first time you're seeing anything of the sort, any extra complication can be extra confusing.
> 1 votes

---
Tags: data-structures, linked-lists, queues
---


# Question
Title: Can the mind be a finite automata and still invent the Turing machine?
The Turing machine was invented by a human mind. Presumably, nothing less powerful than a Turing machine can invent a Turing machine.

However, a Turing machine has infinite tape, whereas the mind is situated in a finite universe, and thus can only be a TM with finite tape. A TM with finite tape can be simulated by a finite automata, which is strictly less powerful than a Turing Machine. This seems to imply that a Turing machine was invented by an automata that is less powerful than a Turing machine, contradicting the initial premise.

Is this a problem? Or, is the initial premise false? Is it possible for a finite automata to somehow "invent" a machine that is more powerful, a kind of bootstrapping, if you will?

While it is difficult to formally define "invent," it does not seem a finite automata can even represent finite TMs effectively. For example, on the wikipedia page, it states a DFA will require quadrillions of states to represent a TM with a few hundred states. So, to even just represent the useful subset of halting TMs, my impression is that a DFA representation will probably exceed any computational capacity we have. There appears a big disconnect between DFAs and TMs, such that it is hard to imagine a plausible bootstrapping to go from one to the other.

There is also the related issue of how a finite automata can prove the halting problem for TMs.

# Answer
You do indeed have a premise problem. We are not FSMs *or* TMs. Don't forget that all of these computational theory devices are simple mathematical abstractions composed of a series of axioms and limited input. The computational theory systems (Godel's, Turing's, and Church's) are merely designed to allow us to make proofs about whether certain kinds of functions are computable or not.

By contrast, we:

1. filter through literally infinite information
2. possess consciousness (whatever that means)
3. exist in the physical world

(#1 above might be controversial, but I mean it quite broadly. As machines, we are not merely brains in vat. Plenty of information affects our body, and we are subject to this information in myriad ways, such as wind blowing on our bodies or rays from the sun burning our skin - these tiny inputs may not be directly noticed, but they are only finite if we live in a discrete universe, and they can absolutely change our behaviors - our "outputs" if you will)

One simple proof that we are not TMs is what you've just outlined: we can invent Turing Machines, but Turing Machines cannot invent us in turn. It is absolutely trivial for us to see the endpoint of an infinity of TM configurations before they run (though there also exist infinite TMs that we cannot see the endpoint for), but no TM can trivially determine the endpoint of a human before he or she lives.

There's a saying from cartography that can be very useful here: **The Map is Not the Territory**

These axiomatic systems are very cleverly designed to get at some tiny (albeit important) set of ideas, but trying to reduce a human to a Turing Machine's 7-tuple and short series of axioms makes about as much sense as reducing humans to any other abstract axiomatic system. While these systems are useful for seeing aspects of the real world, they are not complete pictures, and we are not Finite State Machines or Turing Machines any more than we are Number Theory or Set Theory.
> 3 votes

# Answer
**Some Turing Machine Details**

* A Turing Machine does not have infinite tape, it has *unbounded* tape. There is no limit to how many symbols can be stored on it, but at any given time, only a finite number of symbols are ever on the tape. So while we cannot conceive of all runs of a machine, we can always conceive at least some states of the machine.
* In a sense, Turing Machines carve out the "finite" portion of all languages, in the sense that it carves out the portion that can be finitely represented (by a Turing Machine). There are uncountably many languages, but countably many Turing Machines, so there's a bunch of stuff we will never understand because it is truly infinite, in too big of an infinity.
* Most problems that we can conceive of don't actually require the power of a Turing Machine. Many can be written using primitive recursion or other well-founded recursion schemes. So most algorithms don't actually require the infinite-ness of Turing Machines.
* For a Turing Machine that halts, there is always a function describing the max amount of memory used in relation to the input size. So we don't need to understand infinity, we simply need to understand the relationship.

**Can a weak system invent a stronger one?**

The answer here, I think, is yes, depending on your definition. For example, the language of all valid Turing Machines can be described using a context-free grammar, a computationally weaker formalization. You can even describe a regular language that describes what a valid Turing Machine looks like, and they're finite. (Spoiler alert, this doesn't say much, because you can map each integer onto a Turing Machine, so the regular language $\\{0,1\\}^\*$ can be the set of all valid Turing Machines).

And, it's important to distinguish recognizing a thing, or inventing a description of something, and inventing all the things. We can recognize what a Turing machine is, but we can't see all of them, and because of things like the Halting problem, we certainly can't even understand all of them.

**Other Infinite Things**

This question is ultimately no different than asking how a finite mind could understand the natural numbers, or the function $y=x$ in $\mathbb{R}^2$. Both are infinite, but can be described in finite ways.

But, there are functions and sets and real number and such that are truly infinite, that can never be described by any possible spoken or written formula (because there are uncountably many reals, but countably many finite sentences in any human language.) And there are more true theorems than there are proofs, a la Gödel.

So we can describe infinity, and speak of its properties, perhaps without truly understanding it, at least without understanding every facet of it.
> 7 votes

---
Tags: turing-machines
---


# Question
Title: Turing machine with a countably infinite alphabet
Suppose you have a Turing machine, but with a countably infinite alphabet.

How does such a Turing machine differ from an ordinary Turing machine, either in terms of computability or of complexity classes?

Do complexity classes for ordinary Turing machines hold up in such a model?

**Edit:** quick addendum - it seems obvious that the existence of a countably infinite alphabet leads to uncountably many state transition functions. I'm curious for the answer to both my original question, and to the restriction in which the only transitions allowed are recursive.

# Answer
Your model accepts all possible languages over the countably infinite alphabet.

The first step is to convert the input word to a single symbol, in some one-to-one fashion. We can do that since $\bigcup\_{n=0}^\infty \aleph\_0^n = \aleph\_0$. You can then encode your language in the transition function.

More generally, to get a non-trivial model you need to ensure that the description length of the machine is smaller in cardinality than the number of words over the alphabet.
> 2 votes

---
Tags: complexity-theory, computability, turing-machines
---


# Question
Title: What does it mean that a core supports 2 threads?
I understand that a process may have multiple threads, and that a processor may have multiple cores to run processes in parallel.

But I can't understand how a core may allow multiple threads, what does it change from a core with one thread support?

# Answer
See Wikipedia on Computer Multitasking and Time-sharing, which have an explanation of how operating systems allow this. Basically, they switch between multiple threads.

Read also about hardware multithreading. This allows a single core to execute multiple threads *concurrently*, without switching between them.
> 3 votes

# Answer
Any core "can" work on a multitude of processes or threads - you can have multithreading on single core machines (or more threads than cores in general).

The expensive part with threads is *context switching* \- saving and restoring the set of (nowadays rather large) registers when switching to a different thread. If a core is advertised as "supporting *two* threads" (in opposite to "*n* threads"), one might guess it has either capabilities for hardware threading, but, more likely, ist just has an extra register bank.
> 0 votes

---
Tags: computer-architecture, concurrency, threads
---


# Question
Title: How to teach abstraction needed for programming?
I experience that my students are fixed to compute with concrete values and are not keen to think in terms of general solution like creating a mathematical function $f(n)$ , needed to write programming functions `f(n)`.

What is a good method of teaching them this lesson, becoming able to think in abstractions like functions on natural numbers?

# Answer
To the extent that this question is on topic here (that is, without reference to literature on mathematical education), I would propose that experimenting with concrete instances is not antithetical to the development of abstract concepts.

In an educational setting in computer science, it should be clearly stated and agreed upon that formal reasoning is the goal, and aquiring an intuitive grasp on things is not enough. After this is established (not trivial, literally counterintuitive), abstractions and concrete examples can help each other, not get in the way of each other.

The thing is, formal reasoning is not something that we do, it is what we are as a field - which is why studying the history of computing is so important. It can be tedious though, unnerving sometimes. It must be gradually developed as a habit. Intuitions are naturally captivating, and that is why we tend to rely on them to motivate our students, but there is something captivating about formalization too. Our challenge is to bring it to the center of the stage.
> 1 votes

# Answer
It is very common that people start with a concrete problem, solve their concrete problem, and then examine how the solution to the concrete problem can be generalized to more general problems. That's a natural way to arrive at a general solution.

You don't want to interfere with that kind of thinking, except that you may strongly insist that the concrete solution to a concrete problem must be made more abstract. Otherwise, you risk that abstract solutions will never be found by many people. People's minds work in different ways. Trying to force everyone to think the same way is only going to end up in frustration for you and the student.
> 0 votes

---
Tags: education, didactics
---