title: Non-computability and Undecidability?

text:
# Question
Title: Non-computability and Undecidability?
Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?

# Answer
> 2 votes
Non computable problems are also undecidable. Basically undecidable is a subset of non computable.

This is because if you can't even say yes or no then you can't compute it. Take for example the Halting Problem of a Turing Machine, suppose someone asked you after how many steps the Turing Machine will halt on a given input. To answer the exact number you first have to answer whether the Turing Machine is going to halt or not. Then i may count the steps.

What we do is to convert our optimization problem to a decision problem. And if we are not able to give answer of that decision problem we cannot compute it. So, computing is harder than saying yes or no. So if the problem is undecidable then it will be also non computable.

---
Tags: terminology, computability, undecidability
---


title: rationale behind multi-layer networks

text:
# Question
Title: rationale behind multi-layer networks
I recently read that a feed forward neural network with a single hidden layer can represent any continuous function to great precision (ref.). Then how can we justify adding more that one hidden layer to our network ?

# Answer
> 5 votes
The rationale is that the number of neurones you need to use for approximating any given contiguous function decreases as you add subsequent layers. See Colah's Deep Learning, NLP, and Representations for a more in-depth explanation.

---
Tags: machine-learning, neural-networks
---


title: Understanding Master Method's Case 2

text:
# Question
Title: Understanding Master Method's Case 2
Whats the intuition behind multiplying the factor $\log n$

> Master Method Case 2 (CLRS Section 4.5)
>
> If $f(n) = \theta(n^{\log\_b a})$, then $T(n)= \theta(n^{\log\_b a} \log n)$

In generalized form sometime it can be written as

> If $f(n) = \theta(n^{\log\_b a} log^k n)$ with $k = 0$, then $T(n) = \theta(n^{\log\_b a} \log^{k+1} n)$

# Answer
> 1 votes
Suppose that $T(n) = aT(n/b) + n^{\log\_b a}$ and $T(1) = 1$. Now consider some $n$ which is a power of $b$, say $n = b^k$. The formula gives $$ \begin{align\*} T(n) &= aT(n/b) + n^{\log\_b a} \\ &= a^2T(n/b^2) + a(n/b)^{\log\_b a} + n^{\log\_b a} \\ &= a^3T(n/b^3) + a^2(n/b^2)^{\log\_b a} + a(n/b)^{\log\_b a} + n^{\log\_b a} \\ &= \cdots \\ &= a^kT(n/b^k) + a^{k-1}(n/b^{k-1})^{\log\_b a} + \cdots + n^{\log\_b a} \\ &= a^k + a^{k-1}(n/b^{k-1})^{\log\_b a} + \cdots + n^{\log\_b a} \\ &= a^k(n/b^k)^{\log\_b a} + a^{k-1}(n/b^{k-1})^{\log\_b a} + \cdots + n^{\log\_b a}. \end{align\*} $$ There are $k+1 = \log\_b n + 1$ terms in the final formula. Miraculously, all of them are equal to $n^{\log\_b a}$! (Work that out on your own.)

---
Tags: master-theorem
---


title: intractable problem example?

text:
# Question
Title: intractable problem example?
I have been doing some research into the limits of computation and I have come across the terms intractable and undecidable. Are these two terms the same thing?

What does intractable mean and what is an example of an intractable and undecidable problem?

# Answer
Tractable usually means decidable in polynomial time. Under that definition, **NP**-complete problems appear to be intractable, but they're still decidable.
> 4 votes

---
Tags: complexity-theory, computability
---


title: many one reduable

text:
# Question
Title: many one reduable
I A many one reducable to B and given A is decidable then is B decidable ?

preparing for an exam and please let me know if this holds

I understood how if B is decidable then A is decidable

and if A is not decidable then B is not decidable

# Answer
If $A$ is reducible to $B$ and $A$ is decidable, then $B$ is not necessarily decidable.

Suppose, for example that $A=\\{1\\}$ and $B$ is, say, $\\{\langle\\, B\\,\rangle\mid L(M)\text{ is infinite}\\}$. It's well-known that $B$ is undecidable and of course $A$ is decidable (any finite language is decidable).

Now let $X$ be a TM for which $L(X)=\Sigma^\*$. We could pick $X$ to be a one-state TM where the start state was also an accepting state and on every input symbol there was a transition from the start state to itself, for example. In a similar way, let $Y$ be a particular TM for which $L(Y)=\varnothing$.

We could then produce a many-one map from $A$ to $B$ by: $$ f(w)=\begin{cases} \langle\\, X\\,\rangle & \text{if $w=1$}\\ \langle\\, Y\\,\rangle & \text{if $w\ne 1$} \end{cases} $$ Clearly this is a computable function and $w\in A\Longleftrightarrow f(w)\in B$, establishing a reduction from $A$ to $B$ with $A$ decidable and $B$ undecidable.
> 1 votes

---
Tags: turing-machines, reductions
---


title: Infinite calculations in finite time

text:
# Question
Title: Infinite calculations in finite time
This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to complete. Then this computer can do an infinite number of calculations in a finite amount of time.

Why is this impossible? Is there a lower bound on how long it takes to carry out a non-trivial calculation?

# Answer
> 11 votes
This "kind" of computer is known as a Zeno Machine. Its computational model falls into a category called Hypercomputation. Hypercomputational models are mathematical abstractions, and because of the ways in which they are defined to work, they aren't physically possible.

Take your Zeno Machine for example. If we imagine the Zeno Machine to be a calculating machine of any kind, whether it uses an abacus or integrated circuit doesn't matter. Say the program data used by the machine is fed to it by an infinitely long tape of symbols (just like a Turing Machine).

Of course, we know from mathematics that:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum\_{n=1}^{\infty}(\frac{1}{2})^n $

which we say is equal to $1$. Thus the computation should complete in 1 second because the sum absolutely converges.

But this convergence is, of course, dependent on $n$ going to (and reaching) infinity. In the physical sense, this means that as the time required for each calculation gets smaller, the "read head" of the calculating machine will have to zip along the symbols in the tape faster and faster. At some point, this speed will exceed the speed of light.

So answering your second question, the absolute lowest-possible bound on a calculation would probably be on the order of the Planck time, given the speed of light as the primary limiting factor in theoretical, but physically-plausible models of computation.

# Answer
> 6 votes
The time taken for a primitive computation is limited by the speed of light and the size of atoms, as far as we understand physics on this very day, 15 September, 2015.

The computation unit needs to be built out of something of non-zero size (atoms) and for the computation to work, electricity or light will need to zip across it, which will be limited by how long it takes light to zip across the non-zero distance.

# Answer
> -1 votes
"Theory of Everything"'s answer is good, but I want to add some intuition as to why $\Sigma\_{n=1}^\infty (\frac{1}{2})^n$ converges to $1$, which we can translate into an answer to this question:

Imagine that you have a red and a blue bucket; the blue bucket contains one liter of water and the red bucket is empty. You pour half of the water from the blue into the red. Now both buckets have $\frac{1}{2}$ liter of water in them. You again pour half of what is in the blue bucket into the red, there is now $\frac{1}{4}$ liter of water in the blue bucket and $\frac{3}{4}$ liter in the red. Now you continue, always pouring half of what is in the blue bucket into the red bucket. Clearly you will never get more than one liter into the red bucket, and just as clearly you will always have more water in the blue bucket to pour over.

To complete the analogy; the blue bucket contains time, exactly twice as much time as the first computation $c\_1$ takes. For each step of the computation you use up half of the remaining computation-time and pour it into the red bucket of used time. Just as the red bucket of water can't contain more water than the blue contained, the red bucket of used time can not contain more than twice the computation time of $c\_1$. And just as there were always water left in the blue bucket we will always have a tiny bit of computation-time left for the next computation.

**Edit**: As noted by @aroth, this analogy assumes that we can keep dividing water forever; that there is no smallest indivisible atom. Which raises the interesting (I think) point that we must also assume time to be arbitrarily divisible for the computation to finish in finite time.

---
Tags: computability, computation-models
---


# Question
Title: Corner cases in the Interleave Lower Bound for BSTs
The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on Wilber's lower bound.
The Interleave lower bound is proved by defining a Transition Point for every node $y$ in a static tree $P$.
See Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251: Section 2 and Appendix A.

I see a problem with the definedness of the transition point for nodes in the tree that don't have a right subtree, such as leaves, for which there doesn't exist a path from the root that contains both elements from the left subtree + $y$ and from the right subtree of $y$.

Does it constitute a problem to the analysis of the bound?
It certainly seems to weaken `Lemma A.1. For any node y in P and any time i, there is a unique transition point for y at time i.`
If we consider the transition point of such nodes in $P$ to be themselves in $T\_i$ then there is a problem with `Lemma A.3. At any time i, no node in T_i is the transition point for multiple nodes in P.`

Can the analysis and the bound be kept by not counting the interleaving through the leaves (and possibly their parents), and thus avoiding the need to refer to their transition points?

# Answer
Leaves have no interleaving since they only have left sub-trees. Therefore you should apply the bound to all non-leaves, in which case the lemmas in the appendix go through. The resulting lower bound should be exactly the same.

The paper in question appeared first in a conference (FOCS) and then in a special issue dedicated to papers from the conference. Usually the conference reviewers are recruited to do the journal reviews as well, in the case of a special issue. This lowers the standard for reviews, since conference reviews are often not very exacting, and when reviewing the same paper for the journal, the reviewers won't bother to read the paper again. Exacerbating this phenomenon is the fact that the lower bound appears in an appendix.

The experts probably realized this inaccuracy right away, and knew that it wasn't a real problem, so didn't bother to comment about it if they noticed it at all.
> 3 votes

---
Tags: data-structures, search-trees, lower-bounds
---


# Question
Title: Distribution of the number of bits changed during generation of all binary tuples
Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings. I am interested in the total number of bits that change during this process.

During generation we store an $n$-bit string and can change some of the bits of the string in each round, with the string output at the end of each round. Call the sequence of integers represented by the output strings the *generating sequence*. Every $n$-bit string must be generated precisely once in a generating sequence. We are interested in the sum of the Hamming distances between successive elements in the sequence, with the initial value assigned to the string regarded as an $n$ bit change.

For the ascending generating sequence $0,1,\dots,2^n-1$ the number of bits changed during the enumeration is then $2^{n+1} - 2$. The generating sequence $0,2^n-1,1,2^n-2,2,2^n-3,\dots,2^{n-1}-1,2^{n-1}$ yields a larger number of bit changes, at least $(n+1)2^{n-1} = 2^{n-1+\log n}$, and $2^{n-1+\log n} \ge 2^{n+1} \> 2^{n+1} - 2$ as long as $n\ge 4$. A Gray code (which changes one bit at each step) yields $n+2^n-1$ bit changes. We can normalise these by dividing by $2^n$ to obtain the mean number of bits changed per step.

> What is the distribution of the mean number of bit changes per step, for a generating sequence chosen uniformly at random?

Even the expected value would be useful, or its behaviour as $n$ grows. The mean number of bit changes per step tends to 2 for the ascending sequence and tends to 1 for Gray codes (which achieve the minimum), as $n$ increases. However, I'm not even sure what the maximum is, other than being no larger than $n$ bits per step.

# Answer
It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely $2^n-1$. We can then rephrase your question as follows. Let $\pi$ be a random permutation of $\\{0,1\\}^n$. You are interested in the distribution of $$ X = \frac{1}{2^n-1} \sum\_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)), $$ where $d$ is Hamming distance. We can compute the moments of $X$ using linearity of expectation. The expected value of $X$ is $$ \mathbb{E}\[X\] = \mathbb{E} d(\pi(0),\pi(1)) = \mathbb{E}\_{x \neq 0} d(0^n,x) = \frac{\frac{n}{2} 2^n}{2^n-1} \approx \frac{n}{2}. $$ The second moment of $X$ is $$ \mathbb{E}\[X^2\] = \frac{1}{2^n-1} \mathbb{E} d(\pi(0),\pi(1))^2 + \frac{2(2^n-2)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(1),\pi(2)) + \frac{(2^n-2)(2^n-3)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \left(\frac{n}{2}\right)^2. $$ More generally, for every fixed $t$ we have $$ \mathbb{E}\[X^t\] \approx \left(\frac{n}{2}\right)^t. $$ This suggests that $X$ is tightly concentrated around $n/2$.

Going further, one is tempted to conjecture that the distribution is roughly normal, since the dependence between non-adjacent summands is very slight. This can be verified or refuted by repeating the calculation above with $d(\pi(i),\pi(i+1))$ replaced by $d'(\pi(i),\pi(i+1)) = d(\pi(i),\pi(i+1)) - n/2$. Since $d(\pi(i),\pi(i+1))$ is distributed almost like $\mathrm{Bin}(n,1/2)$, this suggests that $X$ is distributed almost like $N(n/2,n/4)$, a normal random variable with mean $n/2$ and variance $n/4$.
> 4 votes

---
Tags: combinatorics, enumeration
---


# Question
Title: Monetary computations theory (manual/textbook)
My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some fraction (percentage), and I have to round the results to cents. Then I have to match the sum of what I calculated to the total amount (the sum of all chunks) multiplied by the same fraction (to make sure that precision loss didn't cause a lot of damage to the "big picture"), and if I have an error, I put it into the last (or first?) calculated value. Then I have to "balance" all the amounts for every start date I have (and, probably, for an end date too).

Example: $A\_i$ is a monetary amount that is associated to a date $D\_i$, $i\in \[1, n\]\subset\mathbb{N}$. I need to calculate commissions for every amount. I know the commission rate $cr$. Every commission amount should be rounded. So, I have $n$ commission amounts $CA\_i$. The problem is that after rounding off the amounts, I get that ($\lceil x\rceil$ is the rounded value of $x$ in what follows): $$\sum\_{i=1}^n \lceil A\_i\*cr\rceil \neq \left\lceil\biggl(\sum\_{i=1}^n A\_i\biggr)\*cr\right\rceil$$

Let's assume that I correct this error by adding the difference to $AC\_n$. Now, I might have another problem: let $\\{d\_j\\}\_{1\leq j\leq m}$ be the set of all (distinct) dates $D\_i$. So, I have that $$\sum\_{k=1}^? \lceil B\_k cr\rceil \neq \left\lceil\biggl(\sum\_{k=1}^? B\_k\biggr)\*cr\right\rceil$$ where $B\_k = \\{A\_i \text{ such that } D\_i = d\\}$, for some date $d\in \\{d\_k\\}$. In other words, if I group the rounded results by date, there will still be an error compared to the total commission for this date. So, I should balance across every date (not forgetting about the total amount!)

This balancing is a very intuition-based approach, which might work or not. I've been looking for some formalization on the internet, but All I got was either the classic numerical analysis (after some brief introduction to floating point representation errors and rounding errors, it immediately goes to linear equations etc.) or just "Don't use floating point to represent money" articles. Are there any accessible sources on the specific topic of monetary calculations?

# Answer
Let me illustrate one problem which could happen, and one way to solve it. You want to distribute a given amount of cents $N$ into $k$ piles, in proportions $p\_1,\ldots,p\_k$, where $p\_1,\ldots,p\_k \geq 0$ and $p\_1 + \cdots + p\_k = 1$. The problem is that $Np\_i$ need not be an integer. As a simple example, you might want to divide $20$ cents into $1/3:2/3$ proportions. The fractional solution is $$ 6\frac{2}{3}:13\frac{1}{3}. $$ It seems fair to round this to $7:13$ since $2/3 \> 1/3$. More generally, compute $m\_i = \lfloor N p\_i \rfloor$ and $r\_i = Np\_i - m\_i$. Here $m\_i$ is the initial allocation and $r\_i$ is the fractional one that you want to round. You need to add up some amount $R = N - \sum\_i m\_i$ of cents to make the total exactly $N$. Sort the $r\_i$ in non-increasing order, and give one cent to the first $R$ parts according to this order (break ties arbitrarily). This is just a generalization of the example above.
> 5 votes

# Answer
Error analysis of floating point programs is a complex fields that far extends the scope of financial calculations. In general it is a quite complex field, which takes a bit of experience to get comfortable with.

Some starter papers:

The reason that textbooks and online sources recommend fixed-precision arithmetic for financial computation is because this is the textbook example of the utility of fixed-point numbers!

The main reason for floats is the case where it is unclear what the "correct" scale for the computation is (in meterology, for example, or other fields of physical calculation). In finance, you literally have a fixed smallest possible quantity: the cent. Coupled with the fact that the largest probable sum that you will ever have to manipulate (say, on the order of 100 trillion dollars), this means that every operation can be perfectly represented at maximum precision.

This is the ideal use case for representing everything as either a fixed point number, or simply a large enough integer representing the number of cents. It's not hard to implement the correct percentage operations that round to the nearest cent using integer division, and I suspect that there are many libraries that implement exactly this.

In conclusion: **floats are hard, and fixed-precision is the right tool to use for dealing with dollar amounts!**
> 1 votes

---
Tags: algorithms, numerical-algorithms, error-estimation
---


# Question
Title: How do I find an upper bound on this recurrence
$f(n)=f(n-\sqrt{n})$

I believe $f(n)\in O(\sqrt{n})$

However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks then does anything change?

# Answer
For definiteness, let's assume that the recurrence is $$ f(n) = \begin{cases} f(\lfloor n-\sqrt{n} \rfloor) + 1 & n \> 0 \\ 0 & n = 0. \end{cases} $$ (We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor \> n-\sqrt{n}-1$, we see that $$ f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}). $$ In the other direction, let us note that $f(n)$ is monotone and that $$ f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}. $$ This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that $$ f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1. $$ Iterating this $\log\_2 n+1$ times, we get $$ \begin{align\*} f(n) &\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &\leq f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &\leq \cdots \\ &\leq f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log\_2 n + 1}} + \log\_2n + 1 \\ &\leq \sqrt{n} \sum\_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &= O(\sqrt{n}). \end{align\*} $$ We conclude that $f(n) = \Theta(\sqrt{n})$.
> 4 votes

---
Tags: complexity-theory, asymptotics, recurrence-relation
---


# Question
Title: Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?
I am reading about red-black trees in *Introduction to Algorithms, Second Edition* by Cormen. Pages 316, 317.

I don't understand why we need to rotate the given tree. See (c) and (d) in the attached picture.

The author says that the following properties of a red-black tree can be violated after a new node has been inserted:

* the root is black;
* children of a red node are black.

The second property is restored in (b). The first property wasn't violated because we didn't insert the tree root. So why do we need to perform any other actions after recoloring?

# Answer
After recoloring in (b), the following rule is still violated:

* children of a red node are black.

Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which remains after step (c) and finally eliminated in step (d).
> 3 votes

---
Tags: algorithms, trees
---


title: Create a grammer for

text:
# Question
Title: Create a grammer for
create a grammer for {a^nb^m, n\>0, m=2^n+1}

itS unrestricted grammer. I tried to but couldnt understand. if you know the answer please breif it. coz i m new in this subject

# Answer
> 0 votes
Hint 1. try build some automaton (Turing machine, etc.) that accept strings of given pattern, then encode both states and transitions in the grammar.

Hint 2. try some scanning process to generate $\\{b^m|m=2^n+1\\}$, then generate $\\{a^n\\}$ **USING THE SAME TECHNIQUE**, and try to merge them.

Some examples:

1. Start from n=0, the sequence is bb,abbb,aabbbbb,aaabbbbbbbbb,... noticing the changes from adjacent items.
2. Using a state variable to scan from left to right and processing, then back. $$Acc \to aAcc \to abbAc \to abbbbA \to \underline{abbbB} \to Aaccc$$ $$Aaccc\to aaAccc \to aabbAcc \to aabbbbAc \to aabbbbbbA \to \underline{aabbbbbB} \to Aaaccccc$$
3. To make up for the direction change, and extra processing at both ends, using delimiters $\\#$. Now start symbol $S\to\\#Acc\\#$
4. Get rid of the state variable and delimiters at the end. But only get rid of them **on accepted state**.

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


title: Can the memory cache hold instructions?

text:
# Question
Title: Can the memory cache hold instructions?
My teacher told us that when the ram runs out of space it will push a program in the cache, i argued that the program should go to the swap space in the hard drive, plus the memory cache cannot hold instructions because instructions and data have different access patterns, it can only hold data frequently accessed. So i am asking the experts, can the memory cache hold instructions ?
Edit : what i mean by memory cache is the L1 memory cache

# Answer
Not perfectly sure whether i understood your question correctly. Basically, there are multiple questions:

A) 'when the system runs out of ram \[...\] push to cache' A cache is a dedicated storage to accelerate the access to often-used Resources. So no, neither ne CPU-cache nor any other cache is used to replace missing ram. I really think your professor wanted to explain SWAP

B) In fact, there are different architectures for computer systems. One of them is the Harvard Architecture where two different memories exist. One is reserved for instructions, while the other is used for data. This Architecture is used by the popular AVR Microcontrollers from Atmel and other MCUs.

The other architecture is the von-Neumann-architecture (sometimes also called Princeton-architecture). This one has exactly *one* memory, which is used for instructions and data. This architecture is used in all Computer systems we know as 'PC' today. This architecture is by the way the reason for most of the really bad security problems (e.G. buffer overflows). In a vulnerable software, an attacker can put instructions somewhere in the memory (the sections which originally should only hold 'data' like strings), and it'll be executed by the processor if its in the 'correct' location.

To return to your question: The CPU-cache doesn't care which memory gets cached. It's simply memory. The sections which are accessed more often will be cached. In a recursive function (many branches to the same location in the *one* memory), the CPU cache may hold instructions.
> 2 votes

# Answer
tillz is broadly correct, however there is one more detail of many modern systems which you should be aware of.

On some modern CPUs, when the power is first turned on and the CPU transfers control to firmware, almost all of the hardware needs to be initialised before it's used. This includes the hardware which arbitrates between cores in a multicore machine. One upshot of this is that main memory may not be available.

So some CPUs (notably Intel-esque machines) do support a mode where cache can be used as if it were RAM. Intel calls this "no-fill mode", and AMD calls it "cache-as-RAM mode". This is handled by the same mechanism that the CPU uses to implement non-cached memory (e.g. memory-mapped I/O).

On most modern CPUs, L1 cache split in two: an instruction cache, which is read-only, and the data cache, which is read-write. It does this so that the CPU pipeline can maintain the illusion of a Harvard architecture on top of a von Neumann architecture: the L1 instruction cache is "program memory" and the L1 data cache is "data memory", and they sit on top of a combined lower-level (probably L2) cache. "Combined" here means "both instructions and data", that is, it implements the von Neumann memory model.

Because the L1 instruction cache is read-only, the only way you can get anything in it is by filling from somewhere, and that somewhere is the next-level cache. So it's actually the lower-level cache which is acting as RAM, not the L1 cache.
> 3 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: How to deal with $n\sqrt n$ in master theorem?
In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$

$T(n) = 8T(n/4) + n\sqrt n$

How do I handle $n\sqrt n$ in this case to get $d$ ?

# Answer
> 4 votes
You have to remember that $\sqrt\[x\]{y} = y^{\frac{1}{x}}$.

Then the rest should follow easily.

Don't look at the following unless you're genuinely stuck.

> $n\sqrt{n} = n^{1}\cdot n^{\frac{1}{2}} = n ^{\frac{3}{2}}$, hence $d = \frac{3}{2}$. We also have $a = 8$ and $b = 4$, so $\log\_{b}(a) = \log\_{4}(8) = \frac{3}{2}$. Hence we have the second case of the Master Theorem where $f(n) \in \Theta(n^{d}\log^{0}n) = \Theta(n^{d})$ with $d = \log\_{b}(a)$. Therefore $T(n) \in \Theta(n^{d}\log n) = \Theta(n^{\frac{3}{2}}\log n)$.

---
Tags: recurrence-relation, master-theorem
---


title: Fixing a grammar

text:
# Question
Title: Fixing a grammar
I'm sorry I don't know the technical terminology for this. All I see in my notes is fixing a grammar. Can someone please help explain this? What exactly is this called?

# Answer
It is just Left Recursion Removal. The algorithms removing recursion for direct and indirect case are presented on the wiki page.

The case in your notes are direct recursion, in general form. $A\to A\alpha|\beta$. It can be roughly explained as below:

Following the rule $A\to A\alpha|\beta$ several times, one can get $$A\to A\alpha\to A\alpha\alpha\to\dotsb\to A\alpha\alpha\dotsm\alpha\to\beta\alpha\alpha\dotsm\alpha$$ ie. $A\to\beta\alpha^k, k\ge 0$. rewrite the rule as $A\to\beta A'$, then the rest $A'\to\alpha^k$ has a non-left recursive form: $A'\to\alpha A'|\epsilon$. In together, we get $$\begin{align}A\to&\beta A'\\A'\to&\alpha A'|\epsilon\end{align}$$ which is a rewrite of $A\to A\alpha|\beta$ while removing left recursion.

Your example $X\to XYaBb|XZ|ba|Bw$ is equivalent to $X\to X(YaBb|Z)|(ba|Bw)$, here $\alpha=YaBb|Z$ and $\beta=ba|Bw$.
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: Finding Second large element from a set of 4 element
Is there any special algorithm of lowest complexity for finding 2nd largest element from a set of 4 elements?

# Answer
It is known that the exact number of comparisons needed to find the second largest element out of $n$ elements is *exactly* $$ n-2+\lceil \log\_2 n \rceil. $$ See for example Jeff Erickson's notes. In our case, this gives $4-2 + \lceil 2 \rceil = 4$ comparisons.

Here is a matching algorithm for $4$ elements. Let the elements be $a,b,c,d$, which we assume to be distinct for simplicity.

1. Compare $a$ and $b$. Without loss of generality, $a \> b$.
2. Compare $c$ and $d$. Without loss of generality, $c \> d$.
3. Compare $a$ and $c$. Without loss of generality, $a \> c$.
4. Compare $b$ and $c$, and return the maximum.

More generally, if $n$ is a power of $2$, here is how to find the second largest element in $n-2+\log\_2 n$ comparisons. First you form a "tournament" by comparing the elements in pairs, then comparing the winners in pairs, and so on, until you find the maximum. This takes $n-1$ comparisons. Then you find the maximum among all $\log\_2 n$ elements which "lost" to the maximum, using $\log\_2 n - 1$ comparisons.

If $n$ is not a power of $2$ then you add dummy elements with value $-\infty$ to pad the list to the closest power of $2$, and proceed as before. The first phase will take only $n-1$ comparisons (since comparisons with dummy elements need not be performed), and the second will take $\lceil \log\_2^n \rceil - 1$ in the worst case (depending on the number of dummy elements which "lost" to the maximal element).
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Alternative Method for Computing Two's Complement Binary -> Decimal
I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a condescending stare. I'm willing to admit I'm wrong when I'm wrong but I can't find a case where it doesn't work.

**Example**

Take a two's complement binary representation of -38

```
1 0 1 1 0 1 0

```

The method I was taught is, starting at the right, keep the bits until you encounter a 1. Then flip all bits after that one. Which gives

```
0 1 0 0 1 1 0 = 38

```

The method I thought was easier since it doesn't involve any binary manipulations is treat the most significant bit as having a minus sign. So you would simply calculate the answer as

```
1*(-64) + 0*(32) + 1*(16) + 1*(8) + 0*(4) + 1*(2) + 0*1 = -38

```

What is wrong with my method?

# Answer
No error. in fact, if you add the binary representation of (-38) and 38 as unsigned 7-bit integer without overflowing, you'll get $10000000\_2$, then due to overflow the lowest 7 bits is preserved, resulting 0. This property holds for all $0\<x\<2^6$, ie. denoting $u(x)$ the unsigned value from 2's component representation of $x$, then $$u(-x) + x = 2^7, (x\>0)$$ thus $$\begin{align}-x =& u(-x)-2^7\\\=&(u(-x)-2^6)+(-2^6)\end{align}$$ ie. subtract the highest bit, and add back the minus bit. This can be extended from 7-bit to n-bit.
> 2 votes

---
Tags: arithmetic
---


# Question
Title: Proving that a language is not Recursive
I have the following language:

T = {M | there exists w such that M accepts w within |w| steps}

I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove that it is NOT recursive I considered the following steps:

1) Assume that it was recursive 2) Conside input w of infinite length 3) Meaning, we get infinite steps that M can perform before halting. So we get the halting problem when considering this infinite input, and we are saying that we can decide it 4) halting problem is not decidable. contradiction

What do you think about this proof? I'm not sure that I can consider an infinite length input, and I'm not sure wither turing machines in general should deal with infinite inputs lengths.

I tried to search for answers with no luck so far. Any help would be much appreciated. Thanks.

# Answer
Proving that the language is in RE is quite easy: simulate the machine on every input $w\in \Sigma^\*$, in minlex order, for $|w|$ steps. If an input is accepted - accept.

Proving that the language is undecidable can be done by reduction from $$A\_{TM}=\\{\<M,w\>: M\text{ accepts }w\\}.$$ A possible reduction:

Given input $\<M,w\>$, construct a new TM $M'$ that works as follows: given input $x$, simulate $M$ on $w$. If $M$ accepts, accept. If $M$ rejects, reject, and of course if $M$ does not halt then so will $M'$.

Now, if $\<M,w\>\in A\_{TM}$, then $M$ accepts $w$ within $t$ steps, for some $t\in \mathbb{N}$. Thus, for a word $x$ with $|x|\>\>t$ (the size of $|x|$ needed depends on the manner of simulation, but can be done with $O(t\log t)$), the simulation of $M$ on $w$ will terminate within $|x|$ steps, and $M$ will accept $w$, so $M'$ will accept $x$, and $\<M'\>\in L$.

Conversely, if $\<M,w\>\notin A\_{TM}$, then $M'$ will not accept any input, so $\<M'\>\notin L$, and you are done.
> 3 votes

---
Tags: computability, turing-machines, proof-techniques, undecidability
---


# Question
Title: Testing the property of being a union of three disjoint cliques
> Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.

I've been sitting for a few hours and I don't have any idea of how to solve this one ... anyone has any ideas / leads?

I have tried to pick the vertices randomly and then conclude from the graph they make $G'$ what it says about $G$. I've divided into cases by connectivity: if the connectivity is $4$ or more it is easy to conclude that the Graph do not has the property. I have struggled with the math in the other cases.

# Answer
I will explain how to solve a similar question:

> Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of *two* disjoint cliques.

I assume that a clique is also considered a union of two disjoint cliques (one of them empty).

The natural test to try is

> Sample three vertices $x,y,z$, and check that the graph $G\[x,y,z\]$ induced by $x,y,z$ is either a triangle or an edge.

If a graph is a union of two disjoint cliques, then this test always passes. Conversely, suppose that this test always passes. Fix some vertex $x$, and let $V\_1$ be the set of vertices connected to $x$, $V\_2$ be the set of vertices not connected to $x$. If $y,z \in V\_1$ then $G\[x,y,z\]$ includes the edges $(x,y),(x,z)$, and so must be a triangle, that is, $(y,z) \in E$. If $y,z \in V\_2$ then $G\[x,y,z\]$ doesn't contain the edges $(x,y),(x,z)$, and so must be the edge $(y,z) \in E$. Finally, if $y \in V\_1$ and $z \in V\_2$ then $G\[x,y,z\]$ contains $(x,y)$ but not $(x,z)$. It must be an edge, so that $(y,z) \notin E$. We conclude that $G$ is indeed a union of two disjoint cliques.

Now suppose that the test passes with probability $1-\epsilon$. In particular, there must be a vertex $x\_0$ such that conditioned on $x = x\_0$, the test passes with probability at least $1-\epsilon$ (why?). Define $V\_1,V\_2$ as before. The argument above shows that $H$, the union of the cliques on $V\_1$ and on $V\_2$, is $\epsilon$-close to $G$ (in fact, slightly closer). Indeed, for every pair of vertices $y,z \neq x\_0$, the test passes on $x\_0,y,z$ if and only if the edge $(y,z)$ exists on both or neither $G$ and $H$. Thus $G$ and $H$ agree on all edges involving $x$, and agree on a $1-\epsilon$ fraction of the rest of the edges.

---

What about the actual question? Again, the natural test to try is

> Sample four vertices $x,y,z,w$, and check that the graph $G\[x,y,z,w\]$ induced by $x,y,z,w$ is a union of three disjoint cliques.

This time the analysis is slightly more complicated. Suppose that the test passes with probability $1 - \epsilon$. We consider two cases.

**Case 1.** $G$ contains at least a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, $G$ is $\sqrt{\epsilon}$-close to a clique.

**Case 2.** $G$ contains at most a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, we can find two *unconnected* vertices $x\_0,y\_0$ such that conditioned on $x=x\_0,y=y\_0$, the test passes with probability at least $1-\sqrt{\epsilon}$. We can now define $V\_1,V\_2,V\_3$ analogously to how we defined $V\_1,V\_2$ in the preceding case, and show that $G$ is $\sqrt{\epsilon}$-close to the union of the cliques on $V\_1,V\_2,V\_3$. Details left to the reader.
> 2 votes

# Answer
I give a hint but not a complete solution. For property testing, it may help to consider what are the forbidden patterns. Then you may have an algorithm with one-side error. A graph $G$ is a union of several disjoint cliques (a.k.a. *cluster graph*) if and only if there is no induced $P\_3$ (a path of three vertices), i.e., any three vertices induce a triangle or one edge. Of course, for your problem, a graph without induced $P\_3$ is a cluster graph but not necessary consists of exactly three disjoint cliques. So, if you only randomly check $P\_3$, it will be two-sides error. You can think about four vertices. A three-disjoint-cliques graph must also be a cluster graph, and furthermore any four vertices do not induce an independent set.
> 1 votes

---
Tags: graphs, clique, disjoint-sets, property-testing
---


# Question
Title: Find the shortest OPEN path connecting a set of 2D points (special case)
I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.

The precondition is very simple: For each point there's always a set of nearby points within a narrow arc, and another (possibly empty) set of nearby points within a narrow arc at a nearly opposite direction. There are no other nearby points.

For each set of three contiguous points within the path, namely A, B and C, the angle ∠ABC always has a measure between 90° and 270° (most of the time it's close to 180°, though there are a couple cases of points forming a nearly right angle), and the angles ∠BAC and ∠BCA have a measure of less than 90° (or possibly a smaller threshold).

My naïve idea is: for each point, evaluate the vectors toward the nearest n points to find whether there are two nearest opposite pairs and make the path piecewise (if all the other points are at nearly the same direction, then we're at the beginning or end of the path).

However, I want to know about a better way to trace the shortest path between the set of points, given the constraints above.

**Edit**: I forgot to say. No, I don't want a cycle. Though minimum Hamiltonian paths are still NP-hard, I...

You know what? I'll build a sparse graph that only contains the set of edges whose weight (Euclidean distance) is less than a threshold, then run Dijkstra's algorithm through the resulting adjacency list. This will work well with my data.

# Answer
> 3 votes
Your paths are varieties of what are often called *angle-restricted paths* in the literature, and exploring the literature may help with your particular situation:

The general angle-restricted TSP (Traveling Salesman Path) problem is NP-hard, as established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."

---
Tags: algorithms, computational-geometry, shortest-path
---


# Question
Title: Sequence of total languages whose limit is turing complete
First let me clarify what I mean by a number of things. A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A language is said to be total if it only encodes total functions from naturals to naturals. A language is turing complete if it can encode all functions from natural numbers to natural numbers that a universal turing machine can. Because I can make a turing machine than infinitely loops on some inputs I can encode a non-total function with a turing machine. So being turing complete implies being non-total.

An interpreter of a language $L$ is a function $I\_L : \mathbb{N} \to \mathbb{N}$ such that $n \in \mathbb{N} \mapsto I\_L(pair(p, n))$ is the same function that $p$ encodes forall $p \in L$. A nice theorem says that if a language is total, it cannot encode such a function.

A while back I was wondering "is there a language that could only be interpreted by a turing complete language". Now the answer seems obvious to me (thanks to some help from stack exchange); no, no such things exists. You can always just add an interpreter for the language to get a total language that can't be interpreted by the previous one.

Clearly this gives raise to a sequence of total languages. Namely the first language you pick, then that language plus its interpreter, then that language plus its interpreter, etc...

But I have no reason to believe that this sequence is even particularly useful. I have some vague intuitive sense of a the limit of this sequence but I can't seem to pin down what a limit of a sequence of languages is. I do not think the limit of this sequence is turing complete. I do think the limit of this sequence is a partial language however. Namely, it seems the limit language should be able to interpret itself (perhaps this is not a good intuition?).

Does such a notion of a limit exist? If it does is there a sequence of total languages whose limit is turing complete? If such a limit exists is it computable? If it is computable, why does no one use such a language?

Bonus: Since we are talking limits anyhow. Is there a topology of languages to be considered here?

# Answer
> 3 votes
I'm not sure I full get your encoding and based on the comments there seem to be some problems with it, but I'll nevertheless provide my answer (or "answer", if you prefer).

A sequence of languages (your terminology) that satisfies your constraints is a sequence where the $i$th element in the sequence runs the Universal Turing machine for $i$ steps or until the machine halts, whichever comes first.

Clearly, each element in this sequence is total, but the limit is a Universal Turing Machine.

---
Tags: computability, reference-request
---


# Question
Title: Can one find the minima of a convex function efficiently?
Say I have a real valued convex function $f$ on the hypercube $\[-1,1\]^n$ and let $f'$ be its restriction on the discrete hypercube $\\{-1,1\\}^n$.

* Is there any $poly(n)$ algorithm that for any class of $f$ (and $f'$) can find the minima of it?
* Is there any relation known between the point where $f$ minimizes and the vertex where $f'$ minimizes? Like if knowing one of them helps find the other in $poly(n)$ time?

# Answer
Minimizing a submodular function can be done in polynomial time. This applies to functions on the discrete hypercube $\\{-1,1\\}^n$.
> 1 votes

---
Tags: algorithms, optimization, polynomial-time
---


# Question
Title: Regular Expression for even-odd language of string
I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \\{a,b\\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'s. I am also interested in constructing a DFA and NFA for the language.

I tried

> Even number of $b$'s = $(a^{\ast}ba^{\ast}ba^{\ast})^{\ast}$

**Edit:** I got `DFA` and `NFA` for odd number of $a$'s and even numbers of $b$'s and still unable to make regular expression which will allow only even number of $b$'s and odd nubmer of $a$'s . I also tried this Regular Expression

> $(a(bb)^{\ast}(aa)^{\ast})^{\ast} $

**Note:** From above RE only those strings are generated which start from a but i want that RE which generate string of even number of $b$'s and odd number of $a$'s regardles of starting from a or b

# Answer
> 8 votes
Constructing a DFA (and thus an NFA), is quite trivial, so let's focus on the regular expression. (well, you can always convert a DFA into a regular expression, but this will not be very insightful, is it?)

Let's start simple. How do we construct an expression that describes only even length strings (over $\\{a,b\\}$)? Or even more simple, how to construct an expression for a language of only even length strings over $\\{a\\}$?

If there's only $\\{a\\}$ in the alphabet, we either have none, or they come in groups of two, so a possible answer is $(aa)^\*$. When we have both $a$ and $b$, things become a bit more difficult. For instance, $(ab)^\*$ is incorrect, since it doesn't allow $aa$. On the other hand, any expression of the form $(a^\*b^\*)^\*$ not going to work, since we can't control the number of each letter. However, as before, we know that the letters must come in groups of 2, thus we should expect the form to be something like $(xy)^\*$ with $x,y$ describing only even length strings, but what should $x,y$ be in this case? Well, we can just write all possible options, getting:

$$ ( aa+ ab+ ba+ bb)^\*$$ (can you make it shorter?)

Now let's ask how do we get *odd*-length strings. Again, if the alphabet has only $a$, this would be quite easy - we can construct an even string, and add another $a$, getting: $$ (aa)^\*a$$

A similar approach works for the case where the alphabet is of size two: $$ ( aa+ ab+ ba+ bb)^\*(a+b)$$

Now a sanity check: we add the "a" or "b" only at the end. Maybe it comes in the middle, and not in the end?! Convince yourself that adding at the end is equivalent, and gives the right answer.

Finally, try to use the above ideas to solve your question. There is still some leap left, so don't give up too fast. Some hints:

> Hint1: the length of the final string must be odd (if it contains both letters)

.

> Hint2: get rid of one letter, so the length is even, and furthermore, both letters appear an even number of times!

.

> Hint3: don't forget to put back the one letter you got rid of. Convince yourself you placed it in the correct place...

# Answer
> 4 votes
Here is a pipeline of simple steps that leads you to the result:

1. Build an automaton $A\_a$ for $L\_a = \\{ w \in \\{a,b\\}^\* \mid |w|\_a \in 2\mathbb{N}+1 \\}$.
2. Build an automaton $A\_b$ for $L\_b = \\{ w \in \\{a,b\\}^\* \mid |w|\_b \in 2\mathbb{N} \\}$.
3. Construct the product automaton $A$ for $L\_a \cap L\_b$.
4. Convert $A$ into a regular expression.

The construction in 3. is a standard one I'd expect to be given in your lecture or textbook; usually, it's how we prove that the regular languages are closed against intersection.

Note how this approach generalizes to any regular language that can be characterized by elementary operations on other regular languages (which are simpled to express). Essentially, you work along the *closure properties* of the class of regular languages.

# Answer
> 2 votes
I will propose a way that requires almost no creativity but instead you will need a heavy algorithmic artillery.

You already found the RE $R\_1=(a^\*ba^\*ba^\*)^\*$ such that $R\_1$ denotes all the strings with a even number of b's(without restriction in the numbers of a's).

Now you can easily find the RE for the strings with a odd number of a's. $R\_2=(b^\*ab^\*ab^\*)^\*b^\*ab^\*$. Lets name this language $L\_2$.

We know that your language of interest $L=L\_1\cap L\_2$. I don't know if there is a way to directly intersect regular expressions. But I found a way to intersect DFA's. So the next step are:

1.- Transform the RE's into DFA's. You can do that directly following this algorithm: RE-\>DFA. One advantage of that algorithm is that you generate a minimum DFA so your drawing skills will not be challenged but you always can transform RE-\>NFA-\>DFA.

2.- Next you have to intersect the two DFA's using this algorithm: DFA intersection

3.- Finally you can transform your DFA into a RE following this algorithm: DFA-\>RE

I would do this only if it is my only option because creativity can save a lot of work.

# Answer
> 2 votes
# The hard way to do it

You might be able to deduce this system by pure insight, especially after seeing the answer that this method comes up with. But as Einstein once said in a lecture: "What follows has been done much more elegantly by Minkowski, but chalk is cheaper than gray \[brain\] matter, so we will take it as it comes."

The dumbest machine which builds strings in this language looks like:

```
                           [even, odd]
             (append "b") /           \ (append "a")
                         /             \
{start}  --> [even, even]               [odd, odd]
                         \             /
             (append "a") \           / (append "b")
                           [odd, even]
                                |
                                |
                              {end}

```

where `[]` are states of the system, `()` are actions taken while following an edge (either way), and `{}` are special pointers to enter and terminate the process. From now on the actions will all be "append a string matching this regex", so I will just include the regex in those parentheses and be done with it.

Now we remove states. When we remove a state X, we take every inbound arrow to that state from every other state Y, and create an arrow in its place from Y to every Z, where Z ranges over all of the destinations of outbound arrows of X. There are two subtleties: first, when X has an arrow pointing to itself (none of these do yet, but they will), in which case our regexes all need to include a repetition operator `*`; they all take the form `(Y-to-X)(X-to-X)*(X-to-Z)`. The other subtlety is that if an arrow of the same start and end already exists, we can (and should) concatenate their regular expressions with the alternation operator `|` that matches if either the regex on the right or left matches.

Now, it matters which states you remove, and in which order, for getting this regex to look simple. There are other forms which look less simple. We will remove the right node `[odd, odd]` first, then `[even, even]`, in order to preserve an aesthetic symmetry that will keep our regex simple.

So let's remove `[odd, odd]`. This means that you need to add four arrows: one arrow each from `[even, odd]` and `[odd, even]` back to themselves, and then one arrow from `[even, odd]` to `[odd, even]`, and one arrow back.

The arrow from `[even, odd]` to itself is labeled `(aa)` while the arrow from `[odd, even]` to itself is labeled `(bb)`. The path from `[even, odd]` to `[odd, even]` is `(ab)` and the reverse is `(ba)`.

Now we want to remove `[even, even]`. This is tricky because the `{start}` pointer is pointing at it, so we will instead point the `{start}` at some node `[start]` which is otherwise exactly like `[even, even]` but has no other inbound arrows. This removal symmetrizes the system nicely:

```
{start} ---> [  start  ]
            /           \
       (b) /             \ (a)
          V    (ab|ba)    V
    [even, odd]=======[odd, even] ---> {end}
       V   ^             V   ^
       |___|             |___|
      (aa|bb)           (aa|bb)

```

(Here the double line is again a symmetric transition.)

Eliminating `[even, odd]` is the tricky part; it induces a loop in `[odd, even]` which must now take the form of:

```
aa   |   bb   |   (ab | ba) (aa | bb)* (ab | ba)

```

where I've added spaces added for clarity, but it also has to add onto the `[start] -> [odd, even]` arrow:

```
a    |    b (aa | bb)* (ab | ba)

```

Thus we have simply

```
(a|b(aa|bb)*(ab|ba))(aa|bb|(ab|ba)(aa|bb)*(ab|ba))*

```

It has two parts: the first parses the minimal string that contains an odd number of `a` and an even number of `b`, by saying "either we start on an `a` and all is good or we start on a `b` and take further characters in pairs: if we see an `aa` or `bb` we keep going, if we see an `ab` or `ba` we have found the minimal string."

The second parses any string which has an even number of `a` and an even number of `b`, again by taking characters in pairs: if it sees an `aa` or a `bb` it continues, otherwise if it sees an `ab` or a `ba` it skips as many `aa` and `bb` tokens as it can until it finds a corresponding `ab` or `ba` (doesn't matter which).

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


title: Are Strings Scalar?

text:
# Question
Title: Are Strings Scalar?
I have always considered strings scalar and the main reason for that is that in programming we treat string values a lot like primitive values. But this and this Wikipedia definitions, as far as I understand them, speak against the scalar nature of strings.

In programming *scalar types* are often seen as the opposite of *object types* and strings are usually counted as scalar, because they, as well as primitive types, have natural ordering, and thus can be compared and tested for equality by means of the language itself, as opposed to *object types*, which would usually require custom logic for those operations.

By *scalar* here I mean firstly the opposite of *object types*, but I want to know whether being scalar is a real property of strings or are we just calling them scalar in programming because their behavior resembles primitive types

This leaves me with the question: are strings of text scalar values from the point of view of theoretical computer science?

# Answer
I'm used to hearing the word "scalar" used in physics and linear algebra and such, not theoretical computer science. In that context, we're interested in distinguish between a scalar vs a vector: e.g., an element of $\mathbb{R}$ vs an element of $\mathbb{R}^d$. The word was invented to help us talk about that distinction.

However, that distinction doesn't seem particularly relevant here.

I haven't heard the word "scalar" used much in theoretical computer science.

To the extent that we invented a meaning for "scalar" in theoretical computer science, I'd probably reserve it for values that can be stored in $O(1)$ space, and where basic operations on those values can be performed in $O(1)$ time. For instance, an `int` would qualify under this. If that's the definition you have in mind, a `string` doesn't qualify, as it is a constant-space item and operations on it can't be done in constant time.
> 4 votes

# Answer
So, I think scalar and object aren't particularly well defined here. What I think of it as is that scalar is a primitive type, that can't be broken down, and an object type is a composite type: it is built up from one or more other types.

A string is not inherently scalar, and how they are treated depends much on your choice of programming language.

On the one end, we have Haskell, where `String` is literally a synonym for `[Char]`: that is, a string is just a list of characters. In this sense, `Char` is a primitive type, and `String` is most definitely NOT scalar.

C is similar, where a string is just a pointer to an array of `char`, and C++ string objects are clearly not scalar since they are, well, objects.

However, some languages, like Java and JavaScript, distinguish strings and lists of characters. However, the main reason for doing this is efficiency. They make string its own primitive type, and do some weird stuff internally with interning, so that (in some cases), a string is only stored in one place in memory, and comparing them is as easy as checking pointer equality.

I would argue that this is more of an implementation detail more than anything. Usually, there is some sort of isomorphism between String and a sequence of Char, and there are non-scalar-style operations, like getting the nth character of a string. If you can do that, in some way your string is linked to a collection of characters, making it non-scalar.

Likewise, the fact that you can express string literals doesn't necessarily make them scalar. In Haskell, `"Foo"` is just syntactic sugar for `'F':'o':'o':[]` i.e. the linked list of characters.
> 5 votes

---
Tags: programming-languages, strings
---


# Question
Title: Party optimization: maximum weight independent set in a tree/graph
From Cornell

> Suppose we want to throw a party for a company whose organization chart is a binary tree. Each employee has an associated fun value, and we want the set of invited employees to have the maximum total fun, which is the sum of the fun values of the invited employees. However, no one has fun if some employee and that employee's direct superior are both invited, so we never invite two employees who are directly connected in the organization chart. (The less whimsical name for this problem is the maximum weight independent set in a tree.)

I was trying to think of an analogous statement if the problem were a graph rather than a tree. Might we say that now we want to throw the largest possible party with ex-girlfriends/ex-boyfriends such that no one's ex-partner is invited?

In this case an edge between two members denotes a ex-relationship. We want to find the largest set such that no two members share an edge.

Is this a correct interpretation of the graph problem and is there a known polynomial time algorithm?

# Answer
> 2 votes
You can interpret a graph problem in whatever way you wish. Note that your interpretation makes sense only for bipartite graphs.

Maximum independent set, even with all weights the same, is (almost) NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any fixed $\epsilon \> 0$ (here $n$ is the number of vertices); the actual hardness assumption is NP$\not\subseteq$BPP rather than P$\neq$NP (see for example Anupam Gupta's lecture notes). Under the exponential time hypothesis, any $r$-approximation algorithm must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ for any $\epsilon \> 0$ (see Chalermsook, Laekhanukit and Nanongkai).

---
Tags: graphs
---


title: Term rewriting; Compute critical pairs

text:
# Question
Title: Term rewriting; Compute critical pairs
I have tried to solve the following exercise but I got stuck while trying to find all the critical pairs.

I have the following questions:

1. How do I know which critical pair produced a new rule?
2. How do I know I found all the critical pairs?

> Let $\Sigma= \left \\{ \circ, i, e \right \\}$ where $\circ$ is binary, $i$ is unary, and $e$ is a constant. $$ E=\left \\{ \begin{gather} ( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\ x \circ e \approx x \\ x \circ i(x) \approx e \end{gather} \right\\} $$

My work so far:

> 1. $x\circ e \>\_{\textsf{lpo}} x$ (LPO 1) $x$ is a variable
> $x\circ i(x)\>\_{\textsf{lpo}} e$ (LPO 2b) there are no terms in the right hand side
> $(x\circ y)\circ z\approx x\circ(y\circ z)$
> $s=\circ(\underset{\large s\_1}{\circ(x,y)},\underset{\large s\_2}{\strut z})\qquad t=\circ (\underset{\large t\_1}{x\strut}, \underset{\large t\_2}{\circ(y,z)})$ (LPO 2c)
>
> * check that $s\>t\_j$, $j=\overline{1,m}$
>     $s\>\_{\textsf{lpo}}t\_1$ (LPO 1)
>     to prove that $s\>\_{\textsf{lpo}}t\_2$ (LPO 2c) we prove that $$s\>\_{\textsf{lpo}} y \\;\\;\text{(LPO 1)};\qquad s\>\_{\textsf{lpo}}z \\;\\;\text{(LPO 1)};\qquad \circ(x,y)\>y\\;\\;\text{(LPO 1)}$$
>     * find $i$ such that $s\_i\>\_{\textsf{lpo}}t\_i$ $i=1$ $$\circ(x,y)\>\_{\textsf{lpo}}x\\;\\;\text{(LPO 1)}$$
>
> $(x\circ y)\circ z\>\_{\textsf{lpo}} x\circ (y\circ z)$
> 2. **a.** $(x\circ y)\circ z\\;\rightarrow\\; x\circ (y\circ z)$
> $x\_1\circ e\\;\rightarrow\\; x\_1$
> $x\circ y \mathrel{\\,=?\\,} x\_1\circ e$
> $\theta\\{x \\;\leftarrow \\;x\_1;\\; y\\;\leftarrow \\;e\\}$ $$\require{AMScd} \require{cancel} \begin{CD} (x\_1\circ e)\circ z @\>\>\> \cancel{x\_1}\circ z\\ @VVV @VVV\\ \cancel{x\_1}\circ(e\circ z) @\>\>\> e\circ z\approx z \end{CD}\qquad\text{left identity?}$$
> **b.** $(x\circ y)\circ z\\;\rightarrow\\; x\circ (y\circ z)$
> $e\circ x\_1\\;\rightarrow\\; x\_1$
> $x\circ y \mathrel{\\,=?\\,} e\circ x\_1$
> $\theta\\{x \\;\leftarrow \\;e;\\; y\\;\leftarrow \\;x\_1\\}$ $$\begin{CD} (e\circ x\_1)\circ z @\>\>\> x\_1\circ z\\ @VVV @VVV\\ e\circ(x\_1\circ z) @\>\>\> ? \end{CD}$$
> **c.** $(x\circ y)\circ z\\;\rightarrow\\; x\circ (y\circ z)$
> $x\_1\circ i(x\_1)\\;\rightarrow\\; e$
> $x\circ y \mathrel{\\,=?\\,} x\_1\circ i(x\_1)$
> $\theta\\{x \\;\leftarrow \\;x\_1;\\; y\\;\leftarrow \\;i(x\_1)\\}$ $$\begin{CD} (x\_1\circ i(x\_1))\circ z @\>\>\> e\circ z\\ @VVV @VVV\\ x\_1\circ(i(x\_1)\circ z) @\>\>\> ? \end{CD}$$

As a support document I have *"Term Rewriting and All That"* by Franz Baader and Tobias Nipkow.

(original image here)

**EDIT1**

After searching for the critical pairs I have the following set of rules(assuming 2.a is corect):

$$ E=\left \\{ \begin{gather} ( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\ x \circ e \approx x \\ x \circ i(x) \approx e \\ x \circ (i(x) \circ y) \approx y \\ x \circ ( y \circ i(x \circ y) ) \approx e \\ e \circ x \approx x \\ e \circ (x \circ y) \approx x \circ y \end{gather} \right\\} $$

# Answer
> 6 votes
Before adressing the actual questions, one remark on your work so far: the left cancellation in 2.a. is not correct in general, the critical pair would just be $x\circ(e\circ z) \approx x\circ z$. Consequently, you don't get the critical pair 2.b. The problem with this cancellation is that the equation you get does in general not follow from the axioms you started from; for example, if you are working in the language of rings, you might at some point derive the critical pair $0\*x \approx 0\*y$, but it would be incorrect to deduce $x\approx y$ (which would mean that you only have a trivial model). No sound rewriting procedure, including Huet's, should allow this reduction.

On the other hand, you are missing the critical pairs you get by unifying (variable-renamed versions of) $x\circ e$ or $x\circ i(x)$ with all of $(x\circ y)\circ z$ (i.e. using the second $\circ$). The resulting critical pairs are

* $x\circ(y\circ e)\leftarrow (x\circ y)\circ e\to x\circ y$, which after reduction becomes the trivial equation $x\circ y\approx x\circ y$, and
* $x\circ(y\circ i(x\circ y))\leftarrow(x\circ y)\circ i(x\circ y)\to e$, which cannot be reduced further and gives the rule $x\circ(y\circ i(x\circ y))\to e$ (assuming that $\circ\triangleright e$ in the precedence $\triangleright$ used to define the LPO, just as you did when orienting $x\circ i(x)\approx e$).

For the basic completion procedure:

1. Whenever you create a critical pair, you reduce both sides as far as possible using the current set of rules. If the resulting normal forms are not equal, you create a new rule. For example, your 2.c. gives a new rule $x\circ(i(x)\circ z)\to e\circ z$. On the other hand, unifying $(x\circ y)\circ z$ with $x\_1\circ y\_1$ gives the critical pair $(x\circ y)\circ(z\circ z\_1)\leftarrow((x\circ y)\circ z)\circ z\_1\to(x\circ(y\circ z))\circ z\_1$, which can be reduced to the trivial $x\circ(y\circ(z\circ z\_1))\approx x\circ(y\circ(z\circ z\_1))$ and discarded.
2. Whenever you create a new rule $l\to r$, you must consider all critical pairs between it and the existing rules $l\_1\to r\_1,\dots,l\_n\to r\_n$, checking for unifiability of $l$ with each non-variable subterm of $l\_i$ and vice versa. Also remember to check for self-overlaps, i.e. unifiability of $l$ with its own subterms, as we did above for associativity. You only stop when all critical pairs of the existing rules have been examined and either produced new rules, or been discarded.

This procedure can be improved quite a bit. In particular, you can use new rules to simplify old ones (and possibly discarding them if they become trivial, meaning they are subsumed by the new rule), and a good heuristic for picking the next critical pair to examine can drastically cut down on the amount of rules.

---
Tags: logic, first-order-logic
---


# Question
Title: Every graph with $\delta(G) \ge 2$ has a cycle of length at least $\delta(G)+1$?
I'm reading up on graph theory using Diestel's book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads:

> **Proposition 1.3.1.** Every graph G contains a path of length $\delta(G)$ and a cycle of length at least $\delta(G)+1$ (provided that $\delta(G) \ge 2$).

Following the proof I can see why this would be true *if* G actually contains a cycle, but I keep thinking there are many graphs, like the path graph itself and connected trees, with $\delta(G) \ge 2$ but which don't have any cycles. I found this question on the same proposition, asking to prove it. The accepted answers there seem to quote Diestel's proof verbatim, assuming G just has a cycle.

I'm pretty sure I'm missing something, so I wonder why one would choose this formulation or whether I'm simply misunderstanding the proposition. Is it assumed that graphs are cyclic unless stated otherwise? Might this be specific to the context in a way I managed to overlook?

As a reminder, $\delta(G)$ is the minimum degree, taken over all vertices of $G$.

# Answer
If $\delta(G) \geq 2$ **every** vertex is connected to *at least* 2 others. This invariably leads to a cycle in any finite graph.

To see why, try to construct a path without a cycle from a graph with $\delta(G) \geq 2$. Every vertex you add is connected to either a previously added vertex (forming a cycle), or an other vertex. However, in turn, that vertex is connected... Since the graph is finite you will at some point run out of vertices to add which you haven't seen already, forcing you to form a cycle.
> 4 votes

# Answer
A path is a tree; trees have minimum degree $1$ so do not meet the hypothesis of the proposition. Conversely, if a graph has minimum degree at least $2$, then it is not a tree, so it *does* contain a cycle.
> 1 votes

---
Tags: graphs
---


# Question
Title: How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?
So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n \> 3$ as well. There are many polynomial time deduction rules that can make progress in finding a solution to a Sudoku puzzle. But then sometimes guessing values and following chains of conclusions might be required to eliminate a cell's value or a combination of cells' values. However, once a valid solution is found, this doesn't guarantee that the solution is UNIQUE. A valid Sudoku puzzle should have only one valid solution but when generating random puzzles, this may take extra computation to verify.

So, my question is, if we allow a certain set of polynomial time deduction rules (say, the most common set described in Sudoku strategy), along with guessing values and following the conclusions, then how much harder can it be to determine there is a unique solution to a given puzzle, versus finding just one solution, in terms of the number of non-unique solutions? Is there an asymptotic difference for certain classes of puzzles?

# Answer
> 14 votes
Yato and Seta show that for every constant $m$, given $m$ solutions to a Sudoku puzzle, it is NP-complete to determine whether there is another solution. They show that the same property is satisfied by other puzzles as well.

# Answer
> 1 votes
If I understand you correctly, you are trying to check Sudoku puzzles that your software have generated to see if they are valid.

**If only being “valid” is of interest then Yuval Filmus has already pointed you to a proof that it is NP complete.**

However if the aim to find new Sudoku puzzles that a person will enjoy solving, the problem is not as hard. (Having to guess lots of values, due to the puzzle not being solvable using “logic” is no fun!) Therefore personally I would limit the number of guesses to at most 4 and reject any puzzle that can’t be proved to have an unique solution within the limitation of what you consider is reasonable.

Doing the above, using standard back tracking to visit all possible guesses (within your limit), and showing that there is only one solution is much easier then NP complete.

Additionally you can score how hard a puzzle is based on the complexity of the deduction rules it needs and the number of guesses that were needed.

# Answer
> 0 votes
In order to prove that a puzzle is unique, any cell in which a guess had to be made must be branched over. When doing a search to simply find an answer, this is generally done with backtracking, where the solution is the first path in the decision tree which leads to a complete board. In order to prove uniqueness, you must show that only one path leads to a valid solution. This is where things get very difficult to define in terms of run time. The complexity is extremely tied to the actual problem at hand. If you are looking at pure worst case scenario, which is extremely unlikely to occur, then they can be considered the same complexity.

In the worst case scenario, when doing the solve, the solution is within the final possible branch of the tree which can be searched. The entire tree had to be searched to find it, while a search for uniqueness would also require the same search, going over the exact same paths.

Realistically however this is not the case, and with almost all cases involving searching for combinatorial designs, searching for one solution is always faster than searching for all solutions.

In general both of these problems are firmly entrenched in exponential run-times, if not worse.

---
Tags: complexity-theory, sudoku
---


# Question
Title: Is an irregular language concatenated with a language with which it has no common symbols irregular?
Here's an example of what I'm talking about. Suppose I have a languages
$$ L\_{1} = \\{a^ib^i \mid i\>0\\},\\ L\_{2} = \\{c^i \mid i\>0\\} $$

and $$ L\_{1}L\_{2} = \\{a^ib^ic^i \mid i\>0\\} $$

Is it true that if $L\_{1}$ is irregular and $L\_{1}$ has no common symbols with $L\_{2}$, then $L\_{1}L\_{2}$ is irregular? How would you prove this?

# Answer
First, your $L1L2$ is wrong. $$L1L2 = \\{a^ib^ic^j\ | \ i\>0, j\>0\\}$$ Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise $L1L2=\phi$ is clearly regular). This can be proved using Myhill–Nerode theorem.

Suppose $X$,$Y$ are any 2 different equivalence classes of $R\_{L1}$, $x\in X, y\in Y$, then there exists string $z$ such that $xz \in L1$ while $yz \notin L1$.

If $L2=\\{\epsilon\\}$, then $L1L2$=$L1$ is irregular. Otherwise, take any string $w\in L2, w \neq \epsilon$, then $xzw \in L1L2$, but $yzw\notin L1L2$ (consider that, due to no common symbol, no suffix of $yzw$ longer than $|w|$ in L2, and no prefix of $yzw$ shorter than $|yz|$ in $L1$).

This shows that $x$,$y$ belongs to different equivalence classes of $R\_{L1L2}$, too. ie. there must be at least the same number of equivalence classes in $R\_{L1L2}$ as in $R\_{L1}$

From Myhill–Nerode theorem, $L1$ has infinite number of equivalence classes. Thus $L1L2$ also has infinite number of equivalence classes, which means $L1L2$ is irregular also.
> 8 votes

# Answer
Yes: in general, if $L\_1$ is a non-regular language over alphabet $\Sigma\_1$, and $L\_2$ is a language over some other alphabet $\Sigma\_2$ with no symbols in common (i.e., $\Sigma\_1 \cap \Sigma\_2 = \emptyset$), and if $L\_2$ is not the empty language ($L\_2 \ne \emptyset$), then the language $L\_1 L\_2$ is also non-regular.

This follows from the closure properties of regular languages. In particular, if $L$ is a regular language and $f$ is a string homomorphism, then $f(L)$ (the homomorphic image of $L$ under $f$) is also regular. Now suppose $L\_1 L\_2$ was regular. Notice that

$$L\_1 = f(L\_1 L\_2)$$

where $f$ is defined so that $f(x)=x$ for all $x \in \Sigma\_1$ and $f(x)=\varepsilon$ for all $x \in \Sigma\_2$. (This is a string homomorphism.)

So, by the closure property, if $L\_1 L\_2$ was regular, it would follow that $L\_1$ was regular as well -- contradicting our assumption. The only possible conclusion is that if $L\_1$ is not regular, then $L\_1 L\_2$ is not regular, either.
> 8 votes

# Answer
The nit-picking answer is actually NO, the language $L\_1L\_2$ is not necessarily nonregular. In order for the given proofs to work we have to require that $L\_2\neq \varnothing$, since $L\_1\varnothing = \varnothing$ which is regular.

The machinery given in the other answers (Myhill-Nerode and closure properties) is really useful and in general is preferable over ad hoc methods. Here however there is a very elegant (albeit ad hoc) construction. If we have a finite automaton for $L\_1L\_2$ and letters in the languages are disjoint, then we simply can replace all letters from $L\_2$ by the empty string $\varepsilon$ and we get an automaton with $\varepsilon$-transitions for $L\_1$. Assuming of course that $L\_2\neq\varnothing$!

For this to work we only need to know that automata with $\varepsilon$-transitions are also defining regular languages.
> 5 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Show that the complements of NP-languages with one word per length are in NP as well
> Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the \> two conditions given below.
>
> 1. L is in NP and
> 2. for every n, there is exactly one string of length n that belongs to L. Let $L^c$ be the complement of L over $Σ^∗$.
>
> Show that $L^c$ is also in NP.

---

My attempt:

If L is a language in NP then L is Turing decidable. So, complement of L is also Turing decidable but not necessarily in NP. To prove it is NP we have to use (ii).

I don't know how to prove it is NP using (ii).

Can you explain it in a formal way, please?

---

This question is from competitive exam GATE. It's also been posted on Stackoverflow.

# Answer
Consider the complement of $L$, which satisfies the following property: for every $n$, there is exactly one string of length $n$ that is *not* in $L^c$.

In order to show that $L^c$ is NP, we show a polynomial time verifier for it. The verifier gets as input $x\in \Sigma^\*$, and a witness $y,z$ such that $|y|=|x|$, $y\notin L^c$, and $z$ is a witness to the membership of $y$ in $L$. Now, the verifier first checks that $y\in L$ using the witness $z$, and then verifies that $y\neq z$.

If the verification succeeded, then $y\in L$, so $x\notin L$, so $x\in L^c$. Conversely, if $x\in L^c$, there must exists such a $y$.
> 5 votes

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: What is the complexity of finding a regular expression equivalent to a given DFA?
I had taken a course long ago on complexity theory. I only remember basic things, so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter introduces DFA and NFA.

If we are given a DFA $D$ where $\sum=\\{0,1\\}$ ( the alphabets ), then how difficult is the problem of finding a regular expression of the language that $D$ recognises?

By difficulty I mean to which class does this problem belong like NP,PSPACE etc ( sorry for vague definition of difficulty, I only have a broad understanding of what classes NP,PSPACE etc are as of now ).

# Answer
"Find an equivalent regular expression" is not a *decision problem*, so it can not be in any of these classes. See also our reference questions on complexity theory.

There are polynomial-time algorithms that solve your computational problem, though, so it is in some flavor of P.
> 2 votes

---
Tags: complexity-theory, finite-automata, regular-expressions, search-problem
---


# Question
Title: Google Deep Dream has these understandings?
From both my own exploration of Google Deep Dream using Dreamify for IOS, and from Google Image results on the topic. I've come to 3 conclusions about the networks understanding of images that seem too common to be coincidences.

I would like to know if these are recognised as consequences of the approach, or otherwise to what degree thease properties are imagined while trying to understand the ambiguous high frequency images the Deep Dream algorithm often produces?

---

1. 3 dimensional understanding of real and dreamt objects, including rotation, occlusion (close things covering distant things), reflections etc...
2. Understanding of how objects group and are arranged allowing deep dream to create believable landscapes, settlements and narrative and physical interactions, including between people.
3. Objects (including people) being thematically/stylistically designed to fit a scene.

---

For example:

https://photos.google.com/share/AF1QipNgj7mRqnzW5G2D7ty3Sqb\_ZITjnBQZA23RH71691sSNVGBvUTVmdSCzb\_3b360xQ?key=SHpzeTVRbHk4SHFhUmMtRXVPRGxuMGRnd2xrM1dn

# Answer
> 3 votes
"Understanding" is a human concept ie a term used for human psychology. It may be used with machine learning systems informally. However, being flexible in interpretation of your question & not strictly literal, there is of course an open scientific question/ research program of how these systems actually "work". In ML, one "trains" systems and the systems exhibit the desired "behavior" but some of this relates to an old psychology theory of "behaviorism" where only the observed behavior is seen to be relevant and attributing particular mental states is seen to be something of a problematic/nonobjective ("anthropomorphic") projection by the experimenter.

With that *caveat,* the current scientific understanding of (deep) neural networks, with lots of related research and active/ongoing, is roughly that they build/ use feature detection. This overlaps with neurobiology theory and knowledge of the visual cortex in mammals. The exact features that are evolved (via "emergence") in the network are somewhat unique to each network, but general trends have been observed also, namely orientation columns (eg esp in "lower levels"). These types of features are also known to arise with sparse coding techniques/ mathematics.

There is a hierarchy of features. Higher level features are built out of lower level features inside the network hierarchy.

So the answer is roughly "yes", the network develops "spatial/ visual concepts" in the form of features. The networks recognize structural patterns in common across many images of real-world objects. These types of patterns include different/ various orientations, placements, relative spatial relationships, and sometimes more abstract "styles" of images found eg in paintings/even architecture etc.

---
Tags: terminology, machine-learning, neural-networks
---


# Question
Title: Are Elementary Cellular Automata structures considered to be fractals?
I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.

But, what about the other rules from Elementary CA? Are they also considered to be fractals?

Is there a definition relating Elementary Cellular Automata and fractals?

# Answer
> 5 votes
Cellular automata *can* generate fractal patterns (as in the case of Rule 90), but they don't always (e.g., Rule 0).

Willson was perhaps the first to demonstrate that CA can produce fractal patterns in the early 80's.

Shortly thereafter Wolfram characterized the fractal properties of a variety of 2-D CAs.

A few years later Culik and Dube went a bit further and proved that certain types of CA :

> ...will always produce a highly regular \[fractal\] behavior on an arbitrary finite configuration as the initial seed.

The take-home message is that some very simple CA rule sets generate complex behavior, but others don't do anything interesting at all.

# Answer
> 3 votes
There is not a precise/formal mathematical definition of "fractal" but there are rough informal specifications such as "infinitely self-similar objects".

A CA can output fractal-like configurations depending on the initial configuration. whether it does so is dependent on the initial configuration and CA rules. Some fractals are very regular and others are very irregular/"noisy". An example of a noisy fractal generated by a CA are patterns that contain many triangle-like regions with lots of surrounding noise. Even very simple CA rules can produce fractals. the same CA could produce either fractals or noise depending on the initial input. The interrelationship between CAs and fractals is a continuing area of study/research.

A bigger concept to note here is that CAs in general are "Turing complete" and can create any computation a Turing machine can, so yes, any "computable fractal" can also be generated by *some* CA. Also some *individual* CA rule sets are Turing complete.

This is a broad area with lots of refs. Two other refs on the subject:

---
Tags: computation-models, cellular-automata
---


# Question
Title: Product Matching problem in pattern matching
The **Product Matching** problem is defined as follows:
**Input**: Text T=t0,...,tn and pattern P=p0,...,pm over alphabet Σ=N .

**Output** : All of the i places in the text where exists ci which holds ti+j = ci * pj for every j=0,...,m

For example: **T**= 2,3,9,12,1,8 **P** = 1,3,4 so in index 1 there is a match for ci=3 because: 1\*3 = 3 , 3\*3=9, 4\*3=12

I've only managed to think about the naive way of multiplying the pattern for each number that gives us less or equal value to max{T} and then checking it with a regular O(N) pattern matching algorithm.

# Answer
> 0 votes
Hint: Starting with the original text, form a sequence $s\_1,\ldots,s\_n$ by the rule $s\_i = t\_i/t\_{t-1}$, and similarly from the original pattern form a sequence $q\_1,\ldots,q\_m$ by the rule $q\_j = p\_j/p\_{j-1}$. Look for the pattern $q$ inside the text $s$.

---
Tags: algorithms
---


# Question
Title: Given RSA, why do we not know if public-key cryptography is possible?
I was on wikipedia on list of unsolved computer science problems and found this: Is public-key cryptography possible?

I thought RSA encryption was a form of public-key cryptography? Why is this a problem?

# Answer
We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a *provably secure* public-key cryptosystem. We don't know for sure that such a cryptosystem exists at all; for all we know, *every* cryptosystem could be broken efficiently.

A different, unrelated problem with RSA is that it can be broken by quantum computers. This is an unrelated problem since the definition of a secure public-key cryptosystem only requires that the cryptosystem not be breakable by classical (non-quantum) computers.

Practically speaking, though, RSA seems secure, and it is used all the time. This is due to the gap between theory and practice. While theoretically we don't know for sure that RSA is secure, practically speaking we have to use some public-key cryptosystem, and RSA is a good choice since people have tried to break it and failed. Generally speaking, a *known* cryptosystem that people care about is more secure than an obscure one, since it has resisted the attempts of cryptographers. This doesn't constitute a proof that it is secure – it might well not be – but it's the best we can do.
> 31 votes

# Answer
Here are some other angles/details on this question, more specific & generally. As YF writes in a comment, despite appearances, RSA is not proven to be at least as hard as factoring. Breaking RSA involves the discrete log problem which of course is closely related to factoring in complexity, but not proven to be the same complexity. But (as pointed out) not even factoring has been proven hard.

YF also mentions quantum computation. As insiders are well aware, RSA is not secure against quantum computation which is proven to be able to factor in P time using Shors algorithm. Shors algorithm was considered a breakthrough at the time. And another breakthrough to mention in a "nearby" area is the AKS primality algorithm which proved that primality testing is in P. Theoretical breakthroughs in complexity theory are rare but not unheard of.

YF doesnt mention, but is always lurking in the background of these questions, the "big question" of P=?NP is still open. It is generally thought that "algorithmic cryptography could be impossible" (except for one-time pads) if P=NP, which is generally disbelieved by experts.

An excellent way to scientifically conceptualize this is Impagliazzos 5 worlds, overview by Kabanets. remarkably, complexity theorists do not know "which of the 5 worlds we live in" although there is circumstantial evidence leaning some ways. What world we live in depends on open complexity theory conjectures. They also relate to open problems on existences of trapdoor functions and one way functions. (RSA is *conjectured* to be both.) There was a 2009 research conference on Impagliazzos worlds with the latest thinking reported.
> 3 votes

# Answer
One thing that needs to be defined here is the definition of possible. There are two ways to answer this. The first is, can a public key cryptosystem be considered information-theoretically secure? In the broadest sense this requires that the algorithm be secure even when subjected to an attack involving infinite computing power. There is one known system that has achieved this, the one time pad, however this is only in theory as we can not create the truly random numbers required, and is private key. The second way the question can be viewed is, can a public key cryptosystem be considered unconditionally secure?. This second definition is looser. In the case of RSA, if someone were to prove that integer factorization was as difficult as we currently think it is, and prove there were no other assumptions or flaws in the system, then RSA would be unconditionally secure. Unconditional security removes the requirement of infinite computing power, and relaxes it to impossible in the physical universe. Since our public key algorithms all rely on massive assumptions on computability they do not meet the second definition.
> 2 votes

---
Tags: cryptography
---


# Question
Title: What's the real difference between throughput and capacity of a network cable?
I was preparing a presentation in work on GPON & other optical network technologies using documentation provided by a supplier, and the claim it made was "GPON networks have a capacity of up to 100Tbps".

Instantly that looked odd to me as I know the **throughput** of the most advanced version of InfiniBand only goes up to 280-290Gbps. I couldn't find any evidence that supported the supplier's claim, only turning up that the throughput of GPON was up to 2.5Gbps. The colleague who had been given the documentation I was working off said that the supplier had claimed that speed was independent of the devices on the network, and that it was limited only by the Optical Network Units (ONUs) and endpoint devices.

That seems a bit ridiculous considering the "data" in an optical cable is a pulse of light. Light travels (in a vacuum) at *c*, so surely the speed of any fibre-optic network is close to *c*, and in the same way the speed of electromagnetic wave propagation down a wire is 66 - 99% the speed of light, but I've never heard a CAT5 manufacturer claim their cables can support those speeds.

I brought it up with the supplier rep and he (derisively) let me know that "that's the capacity, not the throughput". I'm aware that to a lot of people the terms are interchangeable, but from a technical standpoint if throughput is the amount of data that can be sent over a network in a specified amount of time, what is capacity?

It would seem like the "capacity" of an optical fibre is "1 flash of light" as that's all it's likely to hold.

NB this question is about the science behind computer (or other data) networks, so I *think* it belongs here, despite references to particular hardware.

# Answer
> 1 votes
The easiest way to think about your situation is to just say that there is no such thing as "network capacity". To my ears, the term "capacity" makes most sense for data at rest (e.g., storage media); "throughput" is about data in motion; and networks are about data in motion.

I'm sure people have used the phrase "network capacity" to mean something specific, but it doesn't appear that your salesperson isn't using it that way, so I'd suggest you accept that this particular example of sales literature appears to be kinda meaningless and move on. (Not to mention that the clever use of "up to" makes their claim almost unfalsifiable.)

# Answer
> 2 votes
"Capacity", similar to many other terms, is a an overloaded word. In the example you bring, it seems that the meaning is equivalent to "throughput", i.e., the maximal "amount" of information a channel/network/etc. can transfer per time unit.

However, while these terms can be used interchangeably, to my ears "capacity" has the feel of a theoretical limit, while "throughput" has a feel of a practical limit. As in: "the capacity of a fiber channel is 1Gb/sec, which (due to coding, errors, and technical limitation) leads to a maximal throughput of 986KB/sec (=of YOUR data)".

A different explanation which may be used in other settings is a one in which the capacity of a link is measured in relative terms, that is, it will be a ratio between 0 and 1, to be multiplied with a predefined maximal rate of information transfer. This notation is useful when computing flows over the network.

---
Tags: terminology, computer-networks
---


# Question
Title: How can there be 10 steps in the binary search algorithm for the phone book search problem?
The following example was given in an online lecture I was watching.

A phone directory is 1000 pages long, and we have to find the name "Zurich Smith". The algorithm is as follows:

1. Split the phone directory into half. If the name is in the first half, get rid of the second half; and if the name is in the second half, get rid of the first half. Now we are left with 500 pages.
2. Repeat the above step another time, and we are left with 250 pages.
3. Repeat the above step another time, and we are left with 125 pages.
4. Repeat the above step another time, and we are left with 62 pages.
5. Repeat the above step another time, and we are left with 31 pages.
6. Repeat the above step another time, and we are left with 15 pages.
7. Repeat the above step another time, and we are left with 7 pages.
8. Repeat the above step another time, and we are left with 3 pages.
9. Repeat the above step another time, and we are left with 1 page.

\**As you can see, these are 9 steps, but they, in the lecture, are saying that this algorithm involves 10 steps. Why? \**

# Answer
> 5 votes
> but they, in the lecture, are saying that this algorithm involves 10 steps. Why?

He says:"10 **\- give or take**" in the lecture, which means that 10 is an estimate with a small uncertainty in either direction. He accepted it as estimate from the audience, which replies to his question, either because he couldn't be bothered to calculate the correct result or because he didn't want to correct the audience that it's one less, because the correct number is completely irrelevant for what he tries to teach.

# Answer
> 2 votes
To find the right page using binary search would take at most $\lceil log\_2 1000\rceil = 10$ steps, which I guess the lecture refers to. But that is not exactly what you do: note that there are a number of steps where you are left with an odd number $n$ of pages, and say that for the next step, you have $\lfloor n/2\rfloor$ pages; this means that you eliminate the page which is right in the middle (assuming that it doesn't contain the name, in which case you are done).

Doing it this way, nine steps are enough for $2^{10}-1 = 1023$ pages: After the $i$-th step, assuming you haven't found the name yet, the relevant half has $2^{10-i}-1$ pages left in it, which is $1$ for $i=9$.

# Answer
> 1 votes
The algorithm you describe in your question gets you to the *page* that Zurich Smith's name is on, but it doesn't get to his *name*. So, steps 1-9 of your algorithm is simply getting rid of the pages that we know are irrelevant to what we want. The final step would be to simply search the last page to find the name. You could do another binary search, but at this point a linear search would be simple to implement and you wouldn't notice a performance hit in most cases.

In fact, that's a bit like how you would search a phonebook IRL. The first part is finding the page; by comparing index words, you know if you are ahead of or behind the name in the book. When you find the right page, you run your finger down the names on it until you find the one you want (or ones because this is usually the point when you find out how many "Zurich Smiths" live in your city but differentiating those is a completely different algorithm).

So, I would imagine step 10 is "Search the 1 page for 'Zurich Smith'." It might have been left out of the lecture because it might have been seen as a trivial step.

# Answer
> 1 votes
Step nine could have stated that you are left with 2 pages. Imagine having 3 pages, and dividing it by 2. One "half" contains 1, the other "half" contains 2. So no matter how you divide, at most you would do 10 steps. It is always possible to be quicker than 10 steps (eg. if it's exactly in the middle, you will find it in 1 step), and the steps above seem to be from and actual run through of the algorithm. If you run the algorithm for every single name, you will find that

* 1 whole page of names can be found in 1 step
* 2 whole pages of names can be found in 2 steps
* 4 whole pages of names can be found in 3 steps
* ...
* 489 whole pages of names can be found in 10 steps

---

And 489=1000-1-2-4-8-16-32-64-128-256

which is kind of cool if you think about it, there's a higher chance of finding the name in LESS than 10 steps. Now you just have to scan the page for his number..

# Answer
> 1 votes
There are 2 simplifications involved in the example.

1. It will take 10 steps if the book is 1024 pages, not 1000 pages.
2. The binary search will take **at most** 10 steps, not exactly 10 steps.

This is because $\lceil log\_2 1024\rceil = 10$.

---
Tags: algorithms, search-algorithms, binary-search
---


# Question
Title: Notation: $L_R = \{w\#y\space|\space R(w,y)\}$?
What is the set $$L\_R = \\{w\\#y\space|\space R(w,y)\\}$$

Specifically what kind of conditional is $R(w,y)$?
Also what's the purpose of $\\#$?

This comes from page 2 of the Clay paper on **P vs NP:** http://www.claymath.org/sites/default/files/pvsnp.pdf

# Answer
> 6 votes
This set is a formal way of expressing a "checking set." What this is asking is, "Is $y$ a valid output for $w$, where the space of all valid input/output pairs is the binary relation $R$?"

Let $\Sigma\_i$ be the alphabet of the input and $\Sigma\_o$ be the alphabet of outputs. The checking relation, $R\subseteq\Sigma\_i^\* \times \Sigma\_o^\*$ is the binary relation $R(w,y)$ that returns ***true*** if $y$ is a valid solution to $x$, and ***false*** otherwise.

(Note here that a relation can be expressed as a subset of the parameter spaces, $R\subseteq\Sigma\_i^\* \times \Sigma\_o^\*$, or as a function $R(w,y)$ that returns ***true*** or ***false***. The functional form $R(w,y)$ can be viewed as the question, "Is $(w,y)\in R$?")

Finally, the symbol $\\#$ in this definition is just a specific symbol not in $\Sigma\_i$. Because a Turing machine only accepts a single string, you need some way of parameterizing your single input into two parameters, $w$ and $y$.

---
Tags: formal-languages, notation
---


# Question
Title: Converting regular language to regular expression by replacing commas with union
I know that regular languages are those that can be described by regular expressions. For the language `{0,1}*`, is the corresponding regular expression `(0∪1)*` ? If so, does replacing braces with parentheses and commas with union always work when converting from regular language to regular expression?

# Answer
Regular expression represent one way of describing regular languages, but there are other notations which you can use to depict such formal languages. E.g. you can use the standard grammar notation ( $S \to aB, B \to bC, \ldots $) or you can use a nondeterministic finite automaton and therefor a deterministic finite automaton to describe a regular language.

Both of your given examples are of the notation-type "regular expression", which can have multiple forms. An 'or' can be e.g. represented as union ($u$), by square brackets ($\[abc\]$) or maybe a comma like you used in your first example. This is just a matter of what convention you agree to.
> 0 votes

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


# Question
Title: What kind of Neural Network (if any) could fit two sets of data points?
I have two datasets, one of animal migration patterns (collected over the course of a couple years) that consists of many points on an x, y plane (latitude, longitude), and the other of ocean surface temperatures (also a set of lat, long points). What kind of neural network can be used, if any, to see some pattern, or correlate the two sets, so that I could alter the temperature data and have the network predict how the migration pattern changes? Is this a feasible use of an artificial neural network?

# Answer
> 3 votes
Try a common feed-forward neural network with one hidden layer and train it with error backpropagatin to find a coherence between your input (temperature values) and output (migration patterns). In order to train a neural network, you have to have pairs of input and output vecors, i.e. in your case, one temperature measurement position corresponds to one migration position. If you cannot assign single input-output pairs, you might do some preprocessing (for example, simply grouping your data into a grid on the x-/y- plane and taking the mean of each grid). The question to find a suitable number of neurons in the hidden layer is discussed here.

Note that there exist many machine learning techniques to learn relations between input and output data. Furthermore, there exists a notable variety of artificial neural networks in structure as well as in training algorithms. As your question explicitly demands a neural network, this answer tries to provide a rather straightforward standard method.

For pattern analysis (in order to *understand* and/or visualize the patterns/correlations) some statistical approaches might be more suitable, e.g. clustering the data with k-means/EM-algorithm.

---
Tags: artificial-intelligence, neural-networks, classification
---