# Question
Title: Strategy to designing grammar for a LR(1) parser
Is it better to think about tokens from right to left and perform right factoring on grammar for an LR(1) parser? As apposed to thinking about tokens left to right and doing left factoring on grammar for an LL(1) parser.

Example java import statement.

```
S1 -> S2 ;
S2 -> S5
S2 -> S3 id
S2 -> S4 *
S3 -> S5 as
S4 -> S5 .
S5 -> S4 id
S5 -> import id

```

Where `S1` is the starting rule.

Am I correct in thinking LR(1) grammar is no more difficult than LL(1) grammar, but you just need to think about tokens in reverse order. Kinda like LR(1) is the dual of LL(1)?

It also seems like you can simply reverse the order of the rules and construct a sort-of continuous passing style in the grammar in order to convert LR(1) grammar into LL(1) grammar like so:

```
S5 -> import id C1
C1 -> S2
C1 -> as S3
C1 -> . S4
S2 -> ; S1
S1 ->
S3 -> id S2
S4 -> * S2
S4 -> id C1

```

Further more. If you imagine Java is backwards token-wise and an import statement is written like `;s as swing.javax import` for example. Then you create an LL(1) grammar for that. And with your LL(1) grammar, you reverse the parts of each rule. Then you end up with the original LR(1) grammar at the top of this post. This leads me to believe LR(1) is the dual of LL(1).

A language running backwards should be just as expressive as a language running forwards token-wise, as all the information of the sentence is still there. Maybe LL(1) and LR(1) are in fact equal in expressive power as each other.

# Answer
It's not difficult to write grammars, and particularly not LR(k) grammars (despite all the claims to the contrary you'll find floating around). You should start by trying to write down a simple description of the language which reflects the actual structure of the language. In many cases, that's easier to do if you allow yourself to use repetition ("list of"), alternation, and optionality, as you might do in English.

(I've tried to address some of your specific questions after the rather long example.)

For example, some hypothetical language might be a *program*, consisting of a *list of declarations*, with a *declaration* being a *variable declaration* or a *function declaration*.

A *variable declaration* is a *type* followed by a *comma-separated list of variables with optional initializer* followed by a `;`. A *variable with optional initializer* is a *name*, optionally followed by an `=` and an `expression`.

Since this is just an example, I'll stop there and write it out, using a formalism which includes the above-mentioned operators; this is usually called an "extended" BNF (EBNF), which is more of a concept than a standard. (That is, there are a lot of different extensions, all more or less functionally equivalent, but with different textual manifestations). So here's my personal non-standard EBNF:

### Fonts:

* $\it{\<italics\>}$ are non-terminals (surrounded by angle brackets because I can't figure out how to make a good-looking hyphen in MathJax).
* $\it{CAPS}$ are terminals defined by a lexical grammar. (eg. $\it{IDENTIFIER})$
* $\tt{typewriter}$ are literal tokens. (eg. $\tt{begin}$ or $\tt{\\{}$)

### Operators (coloured red to distinguish them from literals):

* $\\;\color{red}{\large{\tt{\mid}}}$: separates alternatives.
* $\\;\color{red}{\large{\tt{\[}}}...\\;\color{red}{\large{\tt{\]}}}$: indicates that $...$ is optional.
* $\\;\color{red}{\large{\tt{\\{}}}...\\;\color{red}{\large{\tt{\\}}}}$: indicates that $...$ can be repeated (at least once).
* $\\;\color{red}{\large{\tt{\\{}}}...\\;\color{red}{\large{\tt{/}}}\\;\tt{,}\\;\color{red}{\large{\tt{\\}}}}$: indicates that $...$ can be repeated, separated with $\tt{,}$ (or some other punctuation token)

(That last one -- the interleave operator -- is particularly divergent; it is not even present in many EBNF variants, although it's incredibly useful. This particular version is mine and mine alone, so don't expect it to work in an EBNF tool.)

With that, the start of the grammar: $$\begin{align}\it{\<program\>}&\to\it\\;\color{red}{\large{\tt{\\{}}}\it{\<declaration\>}\\;\color{red}{\large{\tt{\\}}}}\\ \it{\<declaration\>}&\to\it{\<function\\;declaration\>}\\;\color{red}{\large{\tt{\mid}}}\\;\it{\<variable\\;declaration\>}\\ \it{\<variable\\;declaration\>}&\to\it{TYPE}\enspace\\;\color{red}{\large{\tt{\\{}}}\it{\<initialiser\>}\\;\color{red}{\large{\tt{/}}}\\;\tt{,}\\;\color{red}{\large{\tt{\\}}}}\enspace\tt{;}\\ \it{\<initialiser\>}&\to\it{IDENT}\enspace\color{red}{\large{\tt{\[}}}\tt{=}\enspace\it{\<expression\>}\color{red}{\large{\tt{\]}}}\\ \end{align}$$ Now, we can mechanically turn that into an LR(1) grammar, say for the popular Bison parser generator, using macro transformations for the EBNF operators:

| EBNF | Bison |
| --- | --- |
| $A\to\alpha\\;\color{red}{\large{\tt{|}}}\enspace\beta$ | `A: α | β` |
| $A\to\\;\alpha\\;\color{red}{\large{\tt{\[}}}\\;\beta\\;\color{red}{\large{\tt{\]}}}$ | `A: α | α β` |
| $A\to\\;\color{red}{\large{\tt{\\{}}}\\;\alpha\\;\color{red}{\large{\tt{\\}}}}$ | `A: α | A α` |
| $A\to\\;\color{red}{\large{\tt{\\{}}}\\;\alpha\\;\color{red}{\large{\tt{/}}}\\;\tt{,}\\;\color{red}{\large{\tt{\\}}}}$ | `A: α | A ',' α` |

(Some of the above require the introduction of intermediate non-terminals, if they are used other than at the top-level of a production.)

That produces the following Bison grammar snippet:

```
program
    : declaration
    | program declaration
declaration
    : variable-declaration
    | function-declaration
variable-declaration
    : TYPE initialiser-list ';'
initialiser-list
    : initialiser
    | initialiser-list ',' initialiser
initialiser
    : IDENT
    | IDENT '=' expression

```

OK, let's do your `import` statement, which I think is in some ways as fictional as my language above. Just a couple of notes first:

* I'm not really a Java programmer, but I don't see any reference to the `import type as alias` syntax in the JLS (version 18). Still, it's reasonable to build a grammar which includes it, so we'll do that.
* Your grammar seems to be for a sequence of `import` statements, rather than for a single `import` statement. That seems unrealistic; it's just one of many possible declarations, and it should fit into a syntax like the one above, for example by modifying *declaration* to be $$\it{\<declaration\>}\to\\;\it{\<variable\\;declaration\>}\\;\mid\\;\it{\<function\\;declaration\>}\\;\mid\\;\it{\<import\\;declaration\>}$$ and then making $\it{\<import\\;declaration\>}$ produce a single declaration. That's also a better match for the semantics (in which there's no category for a sequence of declarations of the same kind). So that's what we'll do.

That said, the JLS defines four types of `import` declarations, which is basically a product of two binary choices: *type* or *static*, and *single* or *on-demand*. Ignoring the minor detail about which of the identifiers is allowed to be one of the semi-reserved words (`permits`, `record`, `sealed`, `var`, and `yield`), these can all be summarised by one simple EBNF syntax:

$$\begin{align}\it{import\\;declaration}&\to\tt{import}\enspace\color{red}{\large{\tt{\[}}}\\;\tt{static}\\;\color{red}{\large{\tt{\]}}}\enspace\color{red}{\large{\tt{\\{}}}\it{IDENT}\\;\color{red}{\large{\tt{/}}}\tt{.}\color{red}{\large{\tt{\\}}}}\enspace\color{red}{\large{\tt{\[}}}\\;\tt{.}\enspace\tt{\*}\enspace\color{red}{\large{\tt{|}}}\enspace\tt{as}\enspace\it{IDENT}\\;\color{red}{\large{\tt{\]}}}\enspace\tt{;}\\ \end{align}$$ corresponding to the Bison grammar, where list needs its own non-terminal and the alternatives and optionalities translate into six productions:

```
import
    : "import" dotted-name ';'
    | "import" dotted-name '.' '*' ';'
    | "import" dotted-name '.' "as" IDENT ';'
    | "import" "static" dotted-name ';'
    | "import" "static" dotted-name '.' '*' ';'
    | "import" "static" dotted-name '.' "as" IDENT ';'
dotted-name
    : IDENT
    | dotted-name '.' IDENT

```

Even though that's a lot longer than the EBNF, I believe it's not that hard to follow (nor to write), unlike the LL version in your question.

For the cherry, I'll add (a very cut-down) *function declaration*, and change `TYPE` to a dot-separated list of identifiers, closer to the Java grammar. Then we can verify that it's an LALR(1) grammar by passing it through bison. Here's the full grammar (although for testing purposes, I'm treating `expression` and `statement` as terminals):

```
%token IDENT statement expression
%%
program
    : declaration
    | program declaration
declaration
    : variable-declaration
    | function-declaration
    | import-declaration

variable-declaration
    : type initialiser-list ';'
initialiser-list
    : initialiser
    | initialiser-list ',' initialiser
initialiser
    : IDENT
    | IDENT '=' expression

function-declaration
    : type IDENT parameter-list block
parameter-list
    : '(' ')'
    | typed-name-list
typed-name-list
    : type IDENT
    | typed-name-list ',' type IDENT
block
    : '{' statement-list '}'
statement-list
    : %empty
    | statement-list statement
    | statement-list declaration

import-declaration
    : "import" dotted-name ';'
    | "import" dotted-name '.' '*' ';'
    | "import" dotted-name '.' "as" IDENT ';'
    | "import" "static" dotted-name ';'
    | "import" "static" dotted-name '.' '*' ';'
    | "import" "static" dotted-name '.' "as" IDENT ';'
dotted-name
    : IDENT
    | dotted-name '.' IDENT

type: dotted-name

```

And that works, first time. No errors, no warnings, and no conflicts:

```
$ bison -Wall -v -o minijava.c minijava.y
$

```

(See note 1).

Now, that grammar is definitely not LL. There are various non-terminals which start with the same terminal, and there's lots of left recursion. LR doesn't care about any of that. (And it doesn't care about right recursion, either; I just avoid it because it uses more parser stack.) In this case, I could make it LL by left-factoring and eliminating left recursion, but:

* that's a lot of work;
* the result, like the example you provide, is very hard to read and therefore does not serve to document the syntax of the grammar;
* and it might not have worked, because LR is simply a more powerful parsing algorithm.

In short, it's not necessary to try to force a grammar to follow a particular model of how a parser might function. You can --and, in my opinion, should-- aim for grammars which capture the essence of the syntax in a natural and easily understood way (easily understood by programmers not well-versed in parsing theory, that is), and that's often easier to do if you don't have to apply the grammatical transformations necessary to make linear-time top-down parsing possible.

It's true that LR parsing can be considered a dual of LL, in a certain sense. But it's not that LR is LL applied to the reverse of the input, nor is it the case that some simple grammar transformation (like reversing the grammar) will turn a language into an LL grammar. LR parsing is strictly more powerful than LL parsing; proofs and examples can be found in any textbook on formal language theory. The duality shows up in a comparison of certain algorithms, in particular the algorithms for determining whether a given CFG is LL(k)/LR(k). These algorithms are not the same --they don't have the same asymptotic complexity, for example-- but there are aspects which show the parallels. These are explored in *Sippu & Soisalon-Soininen, On LL(k) Parsing* (1988), which is definitely worth reading if you're interested in the theory. (It won't help you write better grammars, though :-) ).

The dualism is also noted in the comparison between GLL and GLR parsing in various papers by Elizabeth Scott and Adrian Johnstone. Again, these are different algorithms; both can parse any context-free language in polynomial time (but not always linear time), but particular languages can have different asymptotic performance with the two frameworks. Scott & Johnstone argue that the GLL framework produces a simpler algorithm. The value of both GLR and GLL parsing is that it does not require any grammar transformation to make a grammar parsable. It might still require some work to make the language unambiguous, which is useful for practical formal processing. But even that is not a requirement. For example, C++ has a number of ambiguities which can only be resolved by implementing criteria described in the text of the C++ standard, some of which have no context-free description. Even so, it's demonstrably practical, although not necessarily parsable in linear time.

As a final note, I recognise that it is not always as easy to write grammars as my above example seems to indicate. Many languages occasionally require more than one token of lookahead; while it is true that you can always transform an LR(k) grammar into an LR(1) grammar from which the same parse tree can be extracted, that transformation is not of much practical assistance, since the resulting grammars are enormous. If you have a language whose "natural" grammar is LR(2) (or worse), you're generally better off using some lexical or semantic hack or switching to GLL/GLR parsing, rather than transforming the grammar into something parsable with an LR(1) parser. A similar comment applies to certain parsing ambiguities easily resolved with operator-precedence techniques but tedious to resolve using a context-free grammar, which is why most parser generators provide precedence relationships as a disambiguation technique. (One example of such an ambiguity is the infamous "dangling-else"; an LALR(1) grammar exists, but it's easy to get wrong and it is certainly not self-documenting, while the precedence comparison is almost trivial.)

### Notes

1. Because that grammar does not include statements or expressions, it's actually hiding one pain point which may show up in a grammar for the full language, related to the difficulty in deciding whether a given `IDENT` will turn out to be the name of a type or the name of a variable or function. This is particular painful in C, where it cannot be solved without context-sensitivity (that is, letting the lexer look the name up in a symbol table to decide whether it has previously been declared as a type). Extra-grammatical semantic checks like that can be easier in an LL grammar because there's no need to worry about the semantic action being executed speculatively for a production which later turns out to be inapplicable. Most LR parser generators don't allow semantic checks; ANTLR, on the other hand, uses them as a standard practice.
2. The two-volume textbook by the same authors on Parsing Theory (Volume 1 and Volume 2) is also a treasure. Sadly, unlike the above-mentioned article, you probably will only find a freely readable version in an academic library, and the outrageous costs of academic texts makes purchase only practical for the highly-motivated or independently-wealthy.
> 3 votes

---
Tags: parsers
---


# Question
Title: Is there a good rule of thumb for regularization constants?
I'm trying to train some linear logistic regression models and I need regularization. My models contain around 4000 features.

I know that without regularization, a good rule of thumb is to have 10x the number of data points as the number of features.

Unfortunately I have on the order of 1000 examples. With high regularization constants, I'm still able to achieve good results. I know that I could use cross validation for choosing these constants, but I will be training these models within the inner loop of a function, and I care less about accuracy than I do about just training the model once.

Right now, I've been trying constants on the order of num\_features/num\_instances, and this seems to work ok. But I have no reason to believe this is good. Is there some more principled way to determine regularization constants that is not cross-validation?

I'm using scikit learn, so in practice the constant is the inverse of what it is in the literature (for example, I'm using num\_instances/num\_features).

# Answer
> 1 votes
Cross-validation is simple and easy to implement. Rather than inventing something new, which might be dubious, I recommend you use cross-validation. It works.

There are no formulas for the regularization constant, because it depends on the specific task you are trying to solve (i.e., it depends on the data).

---
Tags: machine-learning
---


title: Bitvector for Memory Allocation

text:
# Question
Title: Bitvector for Memory Allocation
Lets say a system has 1TB of memory and 4kB blocks. How many MB of memory do we need if we want to store a bitvector to represent the current memory allocation situation with a bitvector?

**Bitvector**: a string of concatenated 0s and 1s, where 0 means a block is free, 1 means it is already allocated.

The solution is given as 256MB, but I get a completely different number:

1TB = 1000000000 kB 1000000000/4 = 250000000 Blocks Each block can be represented as 1 bit, thus we need 31.25 MB

Where am I wrong?

# Answer
Well, let's get the radix right. 1TB is $2^{40}$ bytes, and 4kB is $4\times 2^{10}$ bytes. So the number of blocks is:

$$\frac{2^{40}}{2^{12}} = 2^{28}$$

There are $2^3$ bits in a byte, so that's $2^{25}$ bytes to represent the bit vector, or 32MB.

The ratio between the two, of course, is exactly 8, which makes me think that they didn't take the number of bits in a byte into account.
> 1 votes

---
Tags: memory-management, memory-allocation
---


# Question
Title: Topological sort of minimum costs to finish interdependent tasks
The problem that I'm trying to solve goes like this:

A project is split into tasks. Each task takes a known number of days. Some tasks can be done at any time(lets call these simple tasks), others depend on other tasks that must first be done. Design an algorithm that can find the minimum number of days necessary to finish the project.

I modeled each task as a node in a graph, and an edge from $x$ to $y$ means that task $y$ depends on task $x$. I also added a $0$ node. Edges go from $0$ to all of the free nodes.

I proceeded to implement Kruskal, with some modifications to deal with the task dependency problem. After banging my head against the keyboard for a while, I realized Kruskal doesn't work on directed graphs.

I did some reading and stumbled upon the topological sort, which seemed to be just what I needed for my problem. While topological sort itself is nice and simple, and I can easily find a topological sort of my graph, I can't figure out how to find the one of minimum cost(cost being number of days, of course).

An idea that just came to me is introducing another new node, call it $-1$. All other nodes have edges going to this one, of $0$ cost. This would be the finish node, and now the problem becomes finding the minimum path from $0$ to $-1$, that is also a topological sort.

Any hints are very much appreciated!

# Answer
> 3 votes
I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the project will always be the same.

Let $t\_i$ represent a task and a vertex in your dependency graph. Let $d\[t\_i\]$ be the days needed to complete task $t\_i$ and $f\[t\_i\]$ be the actual time $t\_i$ is accomplished (finish time). Initially, $f\[t\_i\] = d\[t\_i\]$ for all tasks. Let $F$, initially 0, be the maximum finish time. The solution is as follows:

1. Perform the topological sort of the dependency graph to obtain the sequence $T$.
2. Visit each vertex according to their order in $T$:
    1. Let $t\_i$ be the current vertex. If $f\[t\_i\] \> F$, then $F= f\[t\_i\]$.
    2. If $(t\_i,t\_j)$ is an edge (meaning $t\_j$ is dependent to $t\_i$) and $f\[t\_j\] \lt f\[t\_i\] + d\[t\_j\]$ then update $f\[t\_j\] = f\[t\_i\] + d\[t\_j\]$.
3. Finally, return $F$.

The idea for step 2.2 is to compute the finishing time of a task with respect to the finishing time of its dependency. When a task has multiple dependencies, its finish time will be based on the time of the dependency that will finish late.

**Note**: I think that this solution is the iterative, bottom-up version of John L.'s solution.

# Answer
> 3 votes
This problem is basically to find the longest path in a directed acyclic graph (DAG).

---

Let $cost\[t\]$ be the number of days it takes to do task $t$.
Let $m\[t\]$ be the minimum number of days to finish task $t$ and all its prerequisite tasks.
Let $prerequisite\[t\]$ be the set of prerequisite tasks for task $t$.

We have the following recurrence relation. $$m\[t\] = cost\[t\] + \max\_{p\in prerequisite\[t\]}m\[p\]$$

The minimum number of days necessary to finish the project is $\max\_v m\[v\]$, where $v$ ranges over all tasks.

---

Here is an implementation in Python.

```
from functools import cache

def min_days_to_finish_project(cost, prerequisite):
    @cache
    def min_days_to_finish_task(t):
        return cost[t] + max((min_days_to_finish_task(p) for p in prerequisite[t]),
                             default=0)

    return max(min_days_to_finish_task(t) for t in cost)

# Example
c = {1: 5, 2: 8, 3: 13}  # tasks are [1, 2, 3]
pre = {1: [], 2: [], 3: [1, 2]}
print(min_days_to_finish_project(c, pre))  # 21

```

---

It is assumed above that the project can be completed, i.e., there is no circular dependencies. Otherwise, we should check that first.

---
Tags: algorithms, graphs, scheduling
---


title: Conditional entropies of sum relations

text:
# Question
Title: Conditional entropies of sum relations
Let $(X\_1,Y\_1)$ and $(X\_2,Y\_2)$ be identically and independently distributed. Also consider $Z=X\_1+X\_2$. I am trying to prove the following inequality:

$$ H(X\_2 \vert Y\_1 Y\_2 Z) \leq H (X\_1 \vert Y\_1)\leq H(Z \vert Y\_1 Y\_2).$$

I think I can show that middle term is the average of the other two. So now if I can show $$ H(X\_2 \vert Y\_1 Y\_2 Z) \leq H(Z \vert Y\_1 Y\_2),$$ I should be done. Can someone give a hint?

# Answer
Since $X\_1,X\_2$ are independent, $$ H(X\_1+X\_2) \geq H(X\_1+X\_2|X\_1) = H(X\_2), $$ and similarly $H(X\_1+X\_2) \geq H(X\_1)$. Therefore $$ H(X\_2|X\_1+X\_2) + H(X\_1+X\_2) = H(X\_2,X\_1+X\_2) = H(X\_1,X\_2) \leq \\ H(X\_1) + H(X\_2) \leq 2H(X\_1+X\_2), $$ which implies that $$ H(X\_2|X\_1+X\_2) \leq H(X\_1+X\_2). $$ Since we have only used the independence of $X\_1,X\_2$ in this argument, we also have $$ H(X\_2|X\_1+X\_2,Y\_1Y\_2=y\_1y\_2) \leq H(X\_1+X\_2,Y\_1Y\_2=y\_1y\_2), $$ since given $Y\_1Y\_2=y\_1y\_2$, the random variables $X\_1,X\_2$ just become arbitrary independent random variables. Taking expectation over $y\_1,y\_2$, we deduce $$ H(X\_2|X\_1+X\_2,Y\_1,Y\_2) \leq H(X\_1+X\_2|Y\_1,Y\_2). $$
> 2 votes

---
Tags: probability-theory, entropy
---


# Question
Title: How is the computational power of a human brain comparing to a turing machine?
This seems related to these questions at a glance:

What are some problems which are easily solved by human brain but which would take more time computers?

What would show a human mind is/is not reducible to a Turing machine?

But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:

* *Is there a language, which cannot be recognized by any turing machine, that can be recognized by a human?*
* *Is there a language, which cannot be decided by any turing machine, that can be decided by a human?*

And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:

$$L \subseteq \Sigma^\*$$

Since this is a question about computational power, I would make the following assumptions:

* Human do not make mistakes (here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
* There is no space limit (turing machine gets infinite tape, you get infinite medium to write)
* There are no time constraints
* However, the recognition/decision must be achieved within finite time.
* And of course, in finite space

Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.

**EDIT 1**

OK, as someone pointed out, I will add the following assumptions.

*Human* is probably not easy to define in precise mathematical words, so let's just assume "you".

About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...

**EDIT 2**

OK, to clarify, this *is* a question about model of computation, so yes, like André Souza Lemos mensioned, I am talking about "given a word $w$ and a language $L$, is sentence $w\in L$ decidable". I am not talking about a physical computer.

**EDIT 3**

OK, this is another idea I came up with. Does model of computation theory include inputs that are volatile by itself? That is, the input changes itself? That is probably not the "language recognition" problem though...

# Answer
Given that Alan Turing devised the Turing Machine model of computation by abstracting *what humans actually do when they compute by hand*, I think one would be very hard-pressed to prove that a Turing Machine is more powerful than a human.

*\[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course). Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states\]*
> 7 votes

# Answer
The *computational* problem of defining a language has led science to the concept of **model of computation**.

It is within the context of a model of computation that problems such as "given a word $w$ and a language $L$, is the sentence '$w \in L$' decidable?" can be tackled. The computer I am using now to write this answer is not a model of computation, per se. Which languages can be decided by my computer (or by any computer that has the same specifications), is a question that cannot be answered from a purely theoretical point of view. If my computer had unlimited memory, it would not be my computer, it would be something else, completely different.

Should you (or anybody else) formulate a model of computation that is *inspired* on how the human brain (or body) works $-$ and models like this exist $-$ it could possibly help answering some version of your question, but probably not in a way that could satisfy your fundamental curiosity.

Finally: a computational system can solve a problem by learning from its mistakes. Mistakes can be an essential part of the computational process, as defined by some models of computation.
> 5 votes

# Answer
**Theorem**:

Given the hypotheses of the question, and experimental evidence, the human brain is as powerful as a Turing Machine.

**Proof**

Experience shows that given enough paper, the human brain is capable of simulating on paper the computation of a Turing machine that is fully described on paper. By hypothesis, it does it without errors. Hence it can compute anything some TM will compute. It is actually a universal TM.

So we humans can show that we can do as much as a TM.

Now you should ask Turing Machines whether they can do as much as the human brain.

If they do not answer, it is either because you did not ask politely enough (Turing Machines are very picky on that), or because that is one thing we do that they do not do. But make sure you ask all Turing Machines, as some of them may not be knowledgeable on the topic (like humans about computability). Best is to ask on whatever they use for the TM equivalent of the human Stackexchange.com site.

Given that we can, theoretically of course, build Turing Machines with Lego pieces, this also shows that the above theorem also applies to Lego sets. Then since humans can build Lego sets, that should prove that the Human brain is at least as powerful as Lego sets, though Lego sets are serious contenders for Turing Power.
> 3 votes

# Answer
Here is a question on Turing completeness of neural networks. In my answer, I also discuss the human brain a bit, and I reference also this question here.

I think allowing for some type of infinite medium for infinite external memory is not so interesting. When you also consider a theoretical human brain without limitation in size, it is obvious that you could encode any possible Turing machine as a human brain, and thus the human brain + external memory is Turing complete.

The more interesting question is when you do not combine it with infinite external memory but just ask about the human brain itself.

You could say then a human brain has finite memory, so it is not Turing complete.

However, consider a standard PC. A *physical instance of a PC* also has finite memory and thus is not Turing complete. However, there is the concept of an *abstract machine*. And when you ask the question, is a PC Turing complete, then you don't really want to know about one specific physical instance, but you want to know about the *concept of a PC*, where you could just add as much memory as needed. It is relatively straightforward how to define such *concept of a PC*.

So, back to the human brain: I think this is analogue. You are not interested in one specific physical instance of a human brain. The question is about the *concept of a human brain*. But this is now less straightforward. How do you define such *concept of a human brain*?

Of course, such concept could just be as large as needed to encode any Turing machine. But then, the most relevant aspect is about the memory. Would such concept of a human brain have infinite memory? I'm not sure there is a clear answer. There many different kinds of memory in the human brain. Some kinds are clearly static (e.g. the current activations, like in a artificial RNN). But then it also has associative memory. The concept of such associative memory can easily be regarded as infinite memory.

Following this argumentation, the **concept of a human brain is Turing complete**.
> 1 votes

# Answer
In theory, a Turing machine has enough power to simulate all the molecules in a brain, so there is no doubt that it is as capable.

We can also argue that in some decades, AI will be able to reach human performance and pass the Turing tests successfully, without the need for a detailed physical simulation, just global behavior.
> 0 votes

# Answer
My take:

If by Turing Machine you mean "a plane" Deterministic Turing Machine (DTM), then, a human brain would be strictly more powerful as long as a brain can be

* a non-deterministic TM: in this case, the same set of problems can be solved by both, but for some of them, the running time of the brain is faster ¿P machine = NP brain?
* a non-deterministic TM using randomized algorithms. Here: the brain can solve, with high probability, problems that a DTM can't.
* a non-deterministic TM using randomized algorithms and quantum algorithms.
> -1 votes

---
Tags: turing-machines, computation-models, human-computing, computer-vs-human
---


# Question
Title: Is there a solution to the following thought experiment / problem involving trees?
I am trying to find an algorithmic solution to a thought experiment that occurred to me recently. Please excuse me if the question is a bit naïve as I am not a CS expert.

---

Basically I have a tree with $n$ nodes, each of which is assigned a numeric label $l\in\\{0,\ldots,k\\}$, $k\in\mathbb{Z}, k\geq0$. More than one node can have the same label. An example of such a tree is shown below.

Please excuse me for the poor quality of my drawing.

My aim is to find a mapping $m$ of the labels $\\{0,\ldots,k\\}$ to the set $s\in\\{A,\ldots,Z\\}$ (i.e., from *numbers* to *letters*) such that each path from a root node to a leaf node becomes a *human-readable English word*.

In the example above, a possible mapping could be $1\to S, 2\to E, 3\to L, 4\to A, 5\to N, 6\to W, 7\to D$, yielding the following resulting tree:

As you can see, each path from the root node to a leaf node produces an intelligible English word, which is from left to right $SEA, SELL, SAW$ and $SAND$.

Having a complete English dictionary at our disposal with all possible letter combinations that form intelligible English words, how could one find such a mapping $m:=l\to s$, assuming that any tree given as input is mappable?

---

EDIT: Any mapping needs to map different numbers to different letters, i.e., be injective.

# Answer
> 1 votes
What you're trying to build is kind of a crossword. This link shows an algorithm that generates crosswords. It's not quite your case, but it's close enough. Basically the algorithm does this (starting from the first word $w$ of the ordered dictonary):

1. If $w$ can be placed in a path and if it hasn't already been placed in every path possible: insert it. Else, we'll call $w$ the next avaible word and start again.
2. Search for a word $w\_1$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 1. and insert $w$ in another path
3. Search for a word $w\_2$ that matches the conditions, hasn't already been placed in every path possible and insert it. If every path is full, then you have a solution. If you can't find it, go back to 2. and insert $w\_1$ in another path
4. \[...\]

This is a backtracking algorithm.

I would suggest to sort all the words alphabetically and then by length (you'll have something like $a, aa, ab, b, ba, bb, c, ccc,\ \[...\]$). I think an example will clarify why.

Let's say you just inserted $SEA$ in your example. To fill the path $1-4-6$ you'll have to search words that start with $SA$. This can be done easly with the sort. Starting from words with length $3$ wich start with $S$: if you encounter $S\\\_\ $, where $\\\_\ $ can be every letter other then $A$, or a word with length $\>3$ then $SEA$ can't be placed in that specific path.

To be more specific, let's say this is a portion of the ordered list of words: $\[...\], RAW, SAA, SAW, SEA, \[...\]$. Then we can be sure that if the path $1-4-6$ can be fulfilled by a word, it needs to be after $RAW$ and before $SEA$.

For an implementation you could perhaps use a list of lists like this one: $\[\[1, 2, 4\], \[1, 2, 3, 3\], \[1, 4, 6\],\ ...\]$. Whenever you place a word in a path you replace every number of the list with the corrisponding letter: $\[\[S, E, A\], \[S, E, 3, 3\], \[S, A, 6\],\ ...\]$

---
Tags: algorithms, trees
---


title: Comparing the efficiecy of 2 run times

text:
# Question
Title: Comparing the efficiecy of 2 run times
I have a heap with $n$ elements. $k$ represent a number that is the height of one of the elements in the tree.

I need to compare two run times and prove what i claim.

The 2 run times are: $$ (1)O(\lg n \cdot (\lg n - k)) $$

And: $$ (2)O(2^k \cdot \lg n) $$

Where: $$ \lg n - k $$ Is a constant value.

---

For the first run time formula, its seems that we get: $O(\lg n)$

But how do i find the run time (and prove) for the second run time?

Thanks.

# Answer
$\log(n)-k$ is const $\implies$ $2^{\log(n)-k}$ is const $\implies O(2^{k} \cdot \log(n)) = O(2^{\log(n)-k} \cdot 2^{k} \cdot \log(n)) = O(2^{\log(n)} \cdot \log(n)) = O(n \cdot \log(n))$
> 1 votes

# Answer
In case of heap the worst case height could be $O(\log n)$.

$O(2^k\cdot\log n) = O(2^{\log n} \cdot \log n) = O(n\log n)$
> 0 votes

# Answer
Let $k=\lg(n)+c$.

$(1) = O(\lg(n)),$

$(2) = O(2^{\lg(n)+c}\lg(n))=O(n\log(n)).$
> 0 votes

---
Tags: algorithms, efficiency
---


# Question
Title: Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$
I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. and I have this language here: $$L=\\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\\}$$ So my main purpose is not actually to know the type of this language but I've faced a lot of questions that asked in the same manner, meaning it asks if the given language has a substring with some characteristics in the first half of a string $w$ in the language or such a thing as appears above.

So I'm searching for an approach that I can adopt to solve such questions.

Also, I would like an answer for the type of the above language.

I assume the language to be CFL but don't really know how to build finite automaton or CFG to decide it, it's clear that it's in P but I'm willing to know if it's CFL or regular.

# Answer
> 1 votes
The $|w|$ is even requirement can be checked by a finite state automaton, so that is not a real restriction. Comparing two numbers (the total length $|w|$ and the length of a consecutive sequence of $0$'s) is usually impossible for FSA.

Now to determine the type, following this intuition, you will have to show the language is CFL by building a suitable grammar, and showing it is not in REG, probably by applying the pumping lemma for regular languages.

To build a CFG first try to build one for $\\{ 1^i 0^j 1^k \mid j=i+k\\}$, and then change it in such a way that any number of $1$ can be changed into additional $0$.

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


# Question
Title: Θ, O and Ω, and how they relate to each other as subsets
I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track.

I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger and all of its elements are also in $O(n)$.

Then $Θ(n) ⊆ Ω(n)$ is true too, yes?

But $O(n) \subseteq Ω(n)$ isn't true?

If I were to make statements that involve the union of two sets I could say:

$Θ(n) ∪ Ω(n) ⊆ O(n)$ is **not** true.

and

$Θ(n) ∪ Ω(n) ⊆ Θ(n)$ is true. For this one, if I am correct, is it still true for a proper subset $(⊂)$?

# Answer
Holds $$\Theta=O \cap \Omega$$
> 1 votes

# Answer
For two real numbers $a$ and $b$, either $a \< b$, $a=b$, or $a\>b$. This notation works analogously but orders functions by growth rates. For two functions of $n$, $f(n)$ and $g(n)$, either $f(n)$ grows slower than $g(n)$, $f(n)$ grows as fast as $g(n)$ or $f(n)$ grows faster than $g(n)$. So if $f$ and $g$ are their grow rates, either $f \< g$, $f=g$, or $f \> g$.

If $f \< g$ or $f = g$ (i.e $f \leq g$) we say $f(n) \in O(g(n))$, if $f \> g$ or $f = g$ (i.e $f \geq g$) we say $f(n) \in \Omega(g(n))$, and if $f = g$ we say $f(n) \in \Theta(g(n))$. With real numbers, if $ a \leq b$ and $a \geq b$ then $a=b$ and for the same reason $O(f(n)) \cap \Omega(f(n)) = \Theta(f(n))$.

Here is a Venn diagram of the three sets:

$\omega(g(n))$ and $o(g(n))$ are subsets of $\Omega(g(n))$ and $O(g(n))$ respectively and contains all functions growing strictly faster or slower ($f \> g$ or $f \< g$) than $g(n)$.
> 1 votes

# Answer
## Asymptotic Notations

We can define **Asymptotic Notations** in terms of **Set**

For Example,

> $O(g(n))$ = $\\{f(n) : \exists$ constants $b\>0$ and $n\_o\>0$ such that $0\leqslant f(n) \leqslant b.g(n) \\; \forall \\; n\geqslant n\_o \\}$

It means that $O(g(n))$ is set of all functions $f(n)$ such that there exists positive constants $b$ and $n\_o$ such that $0\leqslant f(n) \leqslant b.g(n)$ for all $n\geqslant n\_o$

**Similarly**

> $\Omega(g(n))$ = $\\{f(n) : \exists$ constants $a\>0$ and $n\_o\>0$ such that $0\leqslant a.g(n) \leqslant f(n) \\; \forall \\; n\geqslant n\_o \\}$

**Now,**

> $\Theta(g(n))$ = $\\{f(n) : \exists$ constants $a\>0$, $b\>0$, and $n\_o\>0$ such that $0\leqslant a.g(n) \leqslant f(n) \leqslant b.g(n) \\; \forall \\; n\geqslant n\_o \\}$

Let's *break* this definition

> $\Theta(g(n))$ = $\\{f(n) : \exists$ constants $a\>0$, $b\>0$, and $n\_o\>0$ such that $0\leqslant a.g(n) \leqslant f(n)$ **AND** $0\leqslant f(n) \leqslant b.g(n) \\; \forall \\;n\geqslant n\_o \\}$

*Breaking Further*

> $\Theta(g(n))$ = $\\{f(n) : \exists$ constants $a\>0$ and $n\_o\>0$ such that $0\leqslant a.g(n) \leqslant f(n)$ **AND** $\exists$ constant $b\>0$ such that $0\leqslant f(n) \leqslant b.g(n) \\; \forall \\;n\geqslant n\_o \\}$

Now, **AND** is necessarily **INTERSECTION of SETS**. Using, this fact and further modification of definition. We can write.

> $\Theta(g(n))$ = $\\{f(n) : \exists$ constants $a\>0$ and $n\_o\>0$ such that $0\leqslant a.g(n) \leqslant f(n) \\; \forall \\; n\geqslant n\_o \\}$
> $$\cap$$ $\\;\qquad\qquad\\{f(n) : \exists$ constants $b\>0$ and $n\_o\>0$ such that $0\leqslant f(n) \leqslant b.g(n) \\; \forall \\; n\geqslant n\_o \\}$

**Thus,**

> $\Theta(g(n)) = \Omega(g(n)) \\; \cap \\; O(g(n))$

## Now, Question

The notation $\Theta(n), \Omega(n) \text{ and } O(n)$ is specific for one class of functions only namely $g(n)=n$, while the notation used in entire solution till text is general for any function $g(n).$ **Now**,
$$\Theta(n) = \Omega(n) \\; \cap \\; O(n)$$ **Thus,** using this property, we can conclude that $$\Theta(n) \subseteq O(n)$$ $$\Theta(n) \subseteq \Omega(n)$$***Undoubtedly,*** $O(n) \subseteq \Omega(n)$ **isn't true**. Informally, $O(n)$ contains all *functions $(f(n))$ asymptotically less than or **equal** to $b.n$ (where b is a positive constant)*, **whereas** $\Omega(n)$ contains all *functions $(f(n))$ asymptotically greater than or **equal** to $a.n$ (where a is a positive constant)*. Both are not mutually disjoint, courtesy to ***equal*** in definition. But, definitely one is not subset of other.

**Moreover**. $\Theta(n) \cup \Omega(n) \subseteq O(n)$ **isn't true**. Since $O(n)$ **doesn't** contain functions greater than $n$, while $\Omega(n)$ consists such functions.

**Now,** $\Theta(n) \cup \Omega(n) \subseteq \Theta(n)$ is **definitely NOT true** since, $\Theta(n) \subseteq \Omega(n)$

The following example may **clarify** things

* $\Omega(n)=\\{n, n\log n, n^2, n^2\log n, n^3, 2^n, 3^n, n! \\;, n^n......\\}$
* $O(n)=\\{1, \log n, n^{\frac{1}{3}} ,\sqrt n, n, ......\\}$

Thus,

* $\Theta(n)=\\{n,......\\}$

**EDIT**
Fundamental Mistake was corrected in later part of solution, thanks to Nathaniel
> 0 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, discrete-mathematics, big-o-notation
---


# Question
Title: Why dont I need to memoize maxHeight in the problem below
I see this occasionally when solving Dynamic programming questions. I like to solve dp questions using recursion, then Memoize it based on the number of parameters I pass to the recursive function. The question is, in my code below, even though I passed three parameters to my recursive function, the solution still worked when I Memoized only two parameters.
I want to understand why this works (memoizing only two parameters instead of three still produces the correct answer). Thanks

Below is the link to the question.
https://leetcode.com/problems/filling-bookcase-shelves/

> You are given an array books where books\[i\] = \[thicknessi, heighti\] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.
> We want to place these books in order onto bookcase shelves that have a total width shelfWidth. We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.
> Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.
> For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf. Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Below is my code. the logic behind my code is:

> For each book we have two choices:
> Either 1) place it in the current shelf or 2) place it in a new shelf.
> Find the minimum from those two options. If we place it in a new shelf, we have to add the height of the previous shelf to the return value.

i.e minH(int curBook, int maxHeight, int curWidth) returns the minimum shelve height attainable using Book\[curBook\] to Book\[N\] where N is the number of books. curBook is the current Book we are on, maxHieght is the maximum height we have seen on the current Shelve excluding the height of curBook, and curWidth is the current width of books placed on the current shelve excluding the width of curBook.

```
class Solution {
public:
    int dp[1001][1001];
    vector<vector<int>> books;
    int shelfWidth;
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        this->books      = books;
        this->shelfWidth = shelfWidth;
        return minH(0, 0, 0);
    }

    int minH(int curBook, int maxHeight, int curWidth){
        if(curBook >= books.size())
            return maxHeight;
        else if(dp[curBook][curWidth])
            return dp[curBook][curWidth];
        else{
            int ans = maxHeight + minH(curBook+1, books[curBook][1], books[curBook][0]);
            if(curWidth+books[curBook][0] <= shelfWidth){
                int Height = max(maxHeight, books[curBook][1]);
                ans = min(ans, minH(curBook+1, Height, curWidth+books[curBook][0]));
            }
            dp[curBook][curWidth] = ans;
            return ans;
        }
    }
};

```

# Answer
> 1 votes
Memoization does not affect correctness. It only affects the running time. An algorithm that is correct with memoization will also be correct without memoization, and vice versa. Memoization doesn't change what result the algorithm returns, it only changes how long it takes to get to that result.

---
Tags: dynamic-programming, c++
---


title: can UTC replace Lamport logical clocks?

text:
# Question
Title: can UTC replace Lamport logical clocks?
if UTC is universal, what drawbacks does it have in using it in a distributed system to coordinate events or use it as a global objective reference clock?

isn't it right to just use UTC to timestamp every message to order messages without using lamport logical clocks!

# Answer
> 1 votes
In a distributed system, achieving perfect time synchronization among all nodes is often impossible. Lamport logical clocks are one way to deal with this problem.

I presume that by "use UTC to timestamp" you are assuming that you will use a timestamp. The problem is that machines' clocks usually aren't perfectly synchronized, so machine A might give a timestamp of 5:00:00.00 and machine B might give a timestamp of 5:00:00.13, but the event on B might actually have happened first even though the timestamp appears to be later, because B's clock isn't synchronized to A's clock.

See also https://en.wikipedia.org/wiki/Logical\_clock.

---
Tags: distributed-systems, clocks
---


# Question
Title: Finding minimal amount of coins to reach n
According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.

The problem is such:

You are required to give change equal to `n` (n is a positive nonzero integer, not necessarily bigger than biggest coin) with a given set of `k` different coins such that each coin has a positive nonzero “value”.

The problem is to find the combination with least amount of coins that is equal to `n`.

The only method of solution I can come up with is the 'brute' approach, so if I have the set `{k1,k2,k3}` of coins, I'll need to calculate `f(n-k1), f(n-k2), f(n-k3)` and for each of `f(n-k_i)` I'll have to calculate another 3 possibilities, which lead to exponential complexity.

However, I've read that this is possible to solve in `O(n)` time, yet all explanations I've seen were really math-based and non-intuitive.

I’m really eager to understand this solution, so any source of information regarding this problem could assist in many ways.

Thanks!

# Answer
This problem is similar to the Knapsack problem. The only difference is that in your case you need to minimize (the amount of coins) instead of maximize (the amount of items in the bag).

The problems are very similar, I think you can get the solution alone :)
> 2 votes

# Answer
You are on the right track that, given a change amount $n$ and denominations $k\_1, k\_2, k\_3$, to compute the minimum number of coins $f(n)$ for change amount $n$ you need to compute $f(n-k\_1)$, $f(n-k\_2)$ and $f(n-k\_3)$.

The main objective is to derive a recursive equation for $f(n)$. Imagine you are given the minimum number of coins for change amount $n$, one coin at a time. In the last step, there are three cases for the value of the last coin: the coin had value $k\_1$, and that before that step the change amount $n-k\_1$ was given to you optimally, i.e. using $f(n-k\_1)$ coins, for a total of $f(n-k\_1)+1$ coins. Similarly for the other two cases. This gives the recursive equation $f(n) = min\\{f(n-k\_1), f(n-k\_2), f(n-k\_3)\\}+1$.

Now that we have a recursive equation for $f(n)$, we can implement it using top-down recursion. To compute $f(n)$ in linear time, you can store the values of smaller subproblems $f(n-k)$ for various $k$ in a table $T$ (stored as a dictionary in the pseudocode below) before returning its value, so that each subproblem is solved only once. This method is called top-down recursion with memoization. Here's the pseudocode:

```
function f(n):
    if n = 0 then return 0
    if n in {k_1, k_2, k_3} then return 1
    if n in T then return T[n] #since subproblem was solved previously, just do a lookup
    else #need to compute and store T[n] before returning a value
        temp = min{f(n-k_1), f(n-k_2), f(n-k_3)} + 1
        T[n] = temp  #memoization: store solution to subproblem before returning solution
        return T[n]

```
> 0 votes

---
Tags: dynamic-programming, linear-complexity
---


# Question
Title: Bitwise X-OR properties for competitive programming
What are some equations/ inequalities and properties of bitwise X-OR that can be used in competitive programming.

# Answer
> 1 votes
*Exclusive or* is non-monotone, linear, symmetric, balanced, evasive.

---
Tags: xor
---


title: Printing an array using recursion

text:
# Question
Title: Printing an array using recursion
Printing an array using recursion is much slower as compared to printing an array using iteration. Why? Is iteration always faster than recursion?

# Answer
It takes most (when not all) compilers more time to call a function, then to jump back with the programmcounter. (The number that indicates which line gets executed.)

When a function gets executed, its parameters and return-adress have to be registered on the stack.
> 1 votes

---
Tags: optimization
---


# Question
Title: Question about Complete partially Directed Acyclic Graph
I am reading CPDAG, can anyone please explain why G1 and G3 are not equivalence classes as in the picture below? Thank you very much!

according to https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html .

> "Theorem 1 \[59\] Two DAGs are equivalent if and only if they have the same skeleton and the same v-structures.
>
> The skeleton of a DAG is the undirected graph that results from ignoring the directionality of every edge.
>
> A v-structure in a DAG $H$ is an ordered triplet of nodes, $(x,y,z)$, such that (1) $H$ contains the arcs $x\rightarrow y$ and $y \leftarrow z$, and (2) the nodes $x$ and $z$ are not adjacent in $H$. A head-to-head pattern (shortened h-h) in a DAG $H$ is an ordered triplet of nodes, $(x,y,z)$, such that $H$ contains the arcs $x\rightarrow y$ and $y \leftarrow z$. Note that in an h-h pattern $(x,y,z)$ the nodes $x$ and $z$ can be adjacent."
>
> The concept of equivalence of DAGs partitions the space of DAGs into a set of equivalence classes.

# Answer
They have different v-structures: $G\_1$ has the v-structures $(x\_3,y,x\_4),(x\_4,y,x\_3)$, whereas $G\_3$ has the v-structures $(x\_1,x\_4,y),(y,x\_4,x\_1)$.
> 3 votes

# Answer
This answer includes some clarification and an answer. The figure in the question is from here. Some clarifications regarding the terms:

1. Two DAGs are equivalent iff they have the same skeletons and the same v-structures. Each equivalent class can be uniquely represented by a partial DAG (PDAG).
2. An equivalence class is denoted using a completed partially directed acyclic graph (CPDAG). Given a DAG, to find its equivalence class, keep the v-structures and convert every other directed edge to undirected, except those that may lead to new v-structures when reversed.

Coming back to the question, in the paper where the image comes from, it seems to be a typo. Also, I don't think that G is a CPDAG since it has directed edges not participating in any v-structure.

---

References

\[1\] David Maxwell Chickering, "Learning Equivalence Classes of Bayesian-Network Structures", JMLR (2002)

\[2\] Guido Consonni, "Learning Markov Equivalence Classes of Directed Acyclic Graphs: an Objective Bayesian Approach", https://www.hiit.fi/wp-content/uploads/2018/04/Learning-Markov-Equivalence-S29.pdf
> 1 votes

---
Tags: graphs
---


# Question
Title: Why can't you randomize an advice string to show that $P/poly \subseteq NP$
**Definitions:**

1. $$\mathsf{NP} = \\{S \\: \mid \\: \text{Exists a polynomial, non-deterministic algorithm $A$ s.t. $A$ decides $S$} \\}$$ Where a polynomial non-deterministic algorithm, is an algorithm that it's runtime is bounded by $p$ some polynomial, and may behave differently from run to run.

2. $$\mathsf{P/poly} = \bigcup\_{c=0}^\infty \mathsf{P/} n^c$$ We say a problem $S \in \mathsf{P}/l$ for some function $l\colon \mathbb{N} \rightarrow \mathbb{N}$, if there exists a polynomial algorithm A and an infinite set of strings $\\{a\_n\\}\_{n = 1}^\infty$ s.t.:

a. $\forall n\colon \left | a\_n \right | = l(n)$

b. $\forall x\colon x \in S \Leftrightarrow A(a\_{\left | x \right |},x) = 1$

**Question:**

Given $S \in \mathsf{P/poly}$, why is it not possible to show an algorithm $M$ that randomizes an advice string $a\_{\left | x\right |}$ such that $\left | a\_{\left | x\right |} \right | \leq p(\left | x \right |)$, and returns the output of $A(a\_{\left | x\right |},x)$? Formally it should perform as follows:

1. Set $a\_{\left | x\right |}$ = ""
2. While $\left | a\_{\left | x\right |} \right | \leq p(\left | x \right |)$ choose non-deterministically:

a. $a \leftarrow a0$

b. $a \leftarrow a1$

c. Continue to step 3
3. Return $A(a\_{\left | x\right |},x)$

I understand that $\mathsf{P/poly} \not \subseteq \mathsf{NP}$ because it contains non-decidable problems, but can't understand why this proof fails.

# Answer
> 2 votes
Consider the following functions with advice: $$ f(a,x) = a. $$ (The advice $a$ is one bit.)

The function $f$ is computable in polynomial time, and this shows that any language of the form $\\{ x : |x| \in S \\}$ belongs to $\mathsf{P/poly}$. If we choose $S$ to be some uncomputable set, then the corresponding language is not in $\mathsf{NP}$.

If you run your proposed algorithm on $f$, then you obtain a nondeterministic algorithm which accepts *all* strings. The problem is that $f$ is guaranteed to compute the language given the correct advice, but there is no guarantee as to what happens when it is fed the wrong advice.

---
Tags: complexity-theory
---


# Question
Title: Generating the n-th number with k bits set, is it possible?
# Generating numbers with $k$ bits set for a poker simulation

## Context

I'm trying to generate all possible Texas Hold'em games for $p$ players, which means there will be at most $2 \cdot p + 5$ cards at play.

To make things a little bit easier, I figured that I could use a 64-bit number to represent each of the cards in a standard 52-card deck (from $2^0$ through $2^{51}$) and represent a full game as the sum of any $2 \cdot p + 5$ distinct 64-bit numbers.

For example, if in my ordering, the suit order is *clubs, diamonds, hearts, spades*, then $1$ would be the ace of clubs ($1♣$), $2$ would be the ace of diamonds ($1♦$), and so on. At the end of the deck will be the king of spades ($K♠$) with a numerical value of $2^{51} = 2\\,251\\,799\\,813\\,685\\,248$ (quite big). This way, the number $2^{51} + 2^1 + 2^0$ uniquely represents a player's hand of $K♠1♦1♣$.

## Example with two players

Plugging in $p=2$ yields a total of $9$ cards at play for a two-player Texas Hold'em game.

This means that any sum of nine distinct numbers from the set described above would represent a valid game of Texas Hold'em poker with two players. For example, the decimal number $511\_d$ in binary is $1\\,1111\\,1111\_b$ and the number $991\_d$ in binary is $11\\,1101\\,1111\_b$.

## What I've tried

My initial strategy was to iterate over all 64-bit numbers, checking each number to see if it has $9$ bits set with an algorithm I found online, but I realized I probably wouldn't be alive anymore by the time it finished.

I then thought that maybe I could generate a few terms of each $k$ algorithmically and then fit a polynomial through them to "predict" the next terms, but that was a dead end as well.

So I was wondering if there exists a closed-form expression to yield the $n$-th number that has $k$-bits set to $1$ in its binary representation ($k=9$ in the two-player example).

# Answer
This is called *Enumerative Coding* and was introduced by Tom Cover. Consider a word $W$ that is $n$ bits long, where the one bits are in locations $x\_k, \ldots, x\_1$ with $x\_k\>x\_{k-1}\>\cdots\>x\_1$ and the locations are labelled from $0$ to $n-1.$

The position of this word in the lexicographic ordering of all words with exactly $k$ $1$ bits set is an integer which we conveniently start at $0$ (due to the formula used):

$$\textrm{Position}(W)=\sum\_{1 \le i \le k} { x\_i \choose i}.$$

So, for example, for a 6-bit word with $3$ bits set:

$$\textrm{Position}(000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$ $$\textrm{Position}(001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$ $$\textrm{Position}(111000) = { 5 \choose 3 } + {4 \choose 2 } + {3 \choose 1} = 19$$

Note that the binomial coefficient $\binom{n}{k}=0$ if $n\<k.$ The first word $000111$ has index zero and the last word $111000$ has index $19.$ There are $\binom{6}{3}=20$ such words so this checks out.

You would apply this with $n=64,$ and $k=9,$ etc.

**Edit:** *Inverse mapping*

For the inverse, note that the sequence $$ {x\_i \choose i },\quad 1\leq i\leq k $$ is increasing in $i$ (being a subsequence of the diagonal of the pascal's triangle).

So given the position, since you know $k$ just find the *largest* quantity of the form $x \choose k$ which obeys $${x \choose k} \leq \textrm{Position}(W).$$ The value of $x$ which is the largest is your $x\_k.$ Then find the largest $x$ which obeys $$ {x \choose k} + {x\_k \choose k} \leq \textrm{Position}(W) $$ which is your $x\_{k-1},$ and so on recursively, for $k$ steps.
> 3 votes

---
Tags: algorithms, reductions, dynamic-programming, combinatorics
---


# Question
Title: Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive
I have to show that given $f:\mathbb{N}\rightarrow\mathbb{N}$ the function that returns the number of times $6$ appears in the input (for example $f(436546)=2$) is primitive recursive. The exercise says to assume that the functions $rem(m,n)$ and $div(m,n)$, which returns the remainder and the quotient, are recursive primitive (rp from now on).

What I tried so far:

1. Trying to build a recursive primitive schema: $$f(0)=0$$ $$f(n+1)=\phi(n,f(n))$$ where $\phi$ returns how many 6 are there in the input. The problem is that if $n=23599$ then to find the number of $6$ you have to divide and get the remainder $3$ times. In general you will have to do this remainder and division algorithm $l$-times where $l$ is the length of the input. So the recursive primitive schema won't work, I guess, because $f(n)$ does not tell you anything.
2. Trying to prove that $proj\_i:\mathbb{N}\rightarrow\mathbb{N}$ is recursive primitive. Where for example $proj\_3(2345)=3$. Now if this is proved to be true $f$ whould be recursive primitive because it's composition of rp functions:$$f(n)=\sum\_{i=1}^{n} (10^i\<n) \times eq(proj\_i(n),6)$$ If this is correct, the only thing left to prove is that $proj$ is a pr function. Maybe like this $proj\_i(n)=rem(div(n,10^{(i-1)}),10)$.
3. I know from other answers in this topic that if we can derive a simple enough algorithm then the function would be pr. In this i guess we can use this strategy, the problem is that we didn't cover it in the lectures, so i guess i can't use it. The algorithm would be very simple though, an iteration, using division and reminder.

# Answer
Here is a recursive function for your problem: \begin{align\*} & \mathrm{count6}(n) = \mathrm{cond}(\mathrm{eq}(n, 0), 0,\\ & \quad \mathrm{add}(\\ & \quad \quad \mathrm{cond}(\mathrm{eq}(\mathrm{rem}(n, 10), 6), 1, 0), \mathrm{count6}(\mathrm{div}(n, 10))) \end{align\*}

$\mathrm{eq}$ is defined as: $$ \mathrm{eq}(x, y) = \begin{cases}1\\,\mathrm{iff}\\,x = y\\ 0\\,\mathrm{otherwise}\end{cases} $$ and $\mathrm{cond}$ as: $$ \mathrm{cond}(x, y, z) = \begin{cases}y\\,\mathrm{iff}\\,x=1\\ z\\,\mathrm{otherwise}\end{cases} $$ Now you just need to show that $\mathrm{eq}$ and $\mathrm{cond}$ are recursive primitive which is tedious but not difficult.
> 1 votes

---
Tags: recursion
---


# Question
Title: LR(1) grammar that can not be transformed an LL(1) grammar
Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.

# Answer
> 1 votes
$\def\NT#1{{\langle\it #1\rangle}}\def\T#1{{\tt#1}}$

The canonical example of an $LR(1)$ language which is not $LL(k)$ for any $k$ is $L\_{\ge} = \\{a^i b^j\mid i\ge j\\}$. It's easy to show that the language is $LR(1)$ since it has an $LR(1)$ grammar (in fact, an $SLR(1)$ grammar): $$\begin{align}L\_{\ge}&\to M\\L\_{\ge}&\to a M\\M&\to\epsilon\\M&\to aMb\\ \end{align}$$ Intuitively, that works for bottom-up parsing because the parser doesn't have to chose between $L\_{\ge}\to aM$ and $M\to a M b$ until it actually sees the $b$, or reaches the end of input. $LL$ parsers don't have that luxury; they must decide which production to predict based on the lookahead from the start of the production, which can't be done. (A more formal proof can be found in the Rosencrantz & Stearn paper cited at the top of this extremely useful summary.)

The dual to this problem, if you like, is the fact that no $LR$ parser exists for the language of palindromes, $P=\\{\omega \omega^R\mid \omega\in\Sigma^\*\\}$. That language is context-free and unambiguous, but it cannot be made deterministic because the parser needs to decide to stop shifting and start reducing precisely at the middle of the input, but it can't know where the middle is until it reaches the end, which is far too late to make a decision.

Of course $P$ is not $LL(k)$ either because $\forall k: LL(k)\subset LR(1)$. But it's a dual in the sense that the problem lies in the impossibility of making a prediction based on the input up to the point of prediction. In $LL$, that point is the beginning of a production and in $LR$, it's at the end. But duality is not identity, and *beginning* and *end*, while duals, are still quite different. Simply put, more information is available at the end than the beginning (where beginning and end are relative to the direction of the parse.)

That might be evident from the observation that the language $L\_\le = \\{a^i b^j\mid i\ge j\\}$, which is very similar to $L\_\ge$, *is* $LL(1)$: $$\begin{align}L\_\le&\to M B\\ M&\to\epsilon\\ M&\to a M b\\ B&\to\epsilon\\ B&\to b B\\ \end{align}$$ Another way to look at that is that $L\_\ge$ is $LL$ if parsed *right-to-left*, while $L\_\le$ is $LL$ if parsed *left-to-right*. Both languages are $LR$ regardless of the direction of the parse.

All of this is of practical importance because of the common need to write parsers for undelimited $\T{if}$ statements with optional $\T{else}$ clauses. (By "undelimited" we mean that there is no explicit punctuation at the end of the $\T{if}$ statement.) The obvious grammar for this construct would be: \[Note 1\]

$$\begin{align} \NT{statement}&\to\NT{if\\;statement}\mid\\; ...\\ \NT{if\\;statement}&\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{statement}\\ \NT{if\\;statement}&\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{statement}\\;\T{else}\NT{statement}\\ \end{align}$$ But that grammar is ambiguous because it doesn't specify which $\T{if}$ should be matched by an $\T{else}$, if there's more than one open $\T{if}$. In other words, when the programmer writes:

```
    if x > 0 then if y > 0 then do_xy_positive else do_something_else

```

the above grammar would allow two interpretations: `do_something_else` executes if $x\>0$ and $y\<=0$, or `do_something_else` executes if $x\<=0$. For this reason, the syntax is often described as the "dangling-else ambiguity", although it's not really ambiguous at all. The simplistic grammar is ambiguous, but almost every programming language uses the same rule: the $\T{else}$ matches the innermost (or first preceding) unmatched $\T{if}$, so the statement would always be interpreted in such a way that `do_something_else` executes if $x\>0$ and $y\<=0$ (and nothing at all happens if $x\<=0$).

It's easy enough to write a grammar which unambiguously implements that syntax: $$\begin{align} \NT{statement}&\to\NT{open\\;statement}\\;\mid\\;\NT{closed\\;statement}\\ \NT{closed\\;statement}&\to\NT{other\\;statements}\\ \NT{closed\\;statement}&\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{closed\\;statement}\\;\T{else}\\;\NT{closed\\;statement}\\ \NT{open\\;statement}&\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{closed\\;statement}\\;\T{else}\\;\NT{open\\;statement}\\ \NT{open\\;statement}&\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{statement}\\ \end{align}$$ That grammar is unambiguous, and moreover $LR(1)$. But it's not $LL(k)$ for any $k$, for a reason very similar to the language $L\_\ge$. Ignoring the $\NT{statement}$ in the $\T{else}$ clause, it's essentially the same language: the number of $\T{if}\\;\T{then}$ clauses must be greater than or equal to the number of $\T{else}$ clauses. Unsurprisingly, this means that there is no $LL(k)$ grammar for C-like $\T{if}$ statements. \[Note 2\]

In practice, it's not that common to see the $LR$ grammar snippet, either, because it's actually much easier for a software engineer to use a feature found in almost all parser generators: precedence declarations. Precedence declarations were designed to simplify the parsing of arithmetic expressions, allowing the use of an ambiguous grammar which doesn't specify how different operators are to be grouped, and then augment the grammar with a list of precedence levels, where each level groups more tightly than the previous ones. In this model, precedence levels are used to resolve shift/reduce conflicts: *shift* is chosen if the token to be shifted has higher precedence than the production to be reduced, and otherwise *reduce* is chosen. Although it's slightly perverse, that mechanism can be used to make $\T{else}$ "greedy". If $\T{else}$ has higher precedence than $\NT{if}\to\T{if}\\;\NT{expression}\\;\T{then}\\;\NT{statement}$, then the $\T{else}$ will always be shifted, causing it to be included in the innermost open $\NT{if\\;statement}$.

---

### Notes

1. C, of course, doesn't use $\T{then}$ to separate the condition expression from the target statement. It prefers to use punctuation; the condition is enclosed in parentheses. But that has no bearing on the dangling-else issue.
2. This doesn't have much impact on recursive descent parsers, but it might affect a table-driven top-down parser. The recursive descent parser only needs to ignore the possible conflict; when $\T{else}$ is encountered by the `if_statement` parse function, it greedily accepts. Parser generators like Antlr or PEG parsers, which use ordered choice, also have no problem with the greedy $\T{else}$. But it remains the case that the language is not $LL(k)$ for any $k$.

# Answer
> 0 votes
Thanks to rici and D.W. for pointing out a very practical example of a LR(1) grammar that can not be expressed as an LL(1) grammar.

They've provided the example language $\\{a^ib^j\mid i\ge j\\}$, which shows why "if then optional-else" is not in $LL(k)$ for any $k$. The example language has at the same or more number of $a$s than $b$s, just as you have the same or more number of **if**s than **else**s, when **else** is optional in a if-then-else statement.

"if then-optional else" has a unambiguous solution in LR(1) where you simply create a separate statement non-terminal which does not contain the if-statement.

E.g.

```
program
    : statements
statements
    : statement
    | statements statement
statement
    : if_statement
    | statement_no_if
statement_no_if // <-- contains all the statements except for if_statement
    : ...
if_statement
    : "if" expression "then" statement
    | "if" expression "then" statement_no_if "else" statement
expresion
    : ...

```

Since `statement_no_if` contains any statement except the `if_statement`, the `else` ends up getting associated to the closest if-statement, make it unambiguous.

So $\\{a^ib^j\mid i\ge j\\}$ can be expressed in $LR(1)$, because of that well known pattern above for handling the dangling else problem in $LR(1)$ grammars.

There is also a simple $LR(1)$ grammar provided by rici for $\\{a^ib^j\mid i\ge j\\}$ of:

$S\to M \mid a S; M\to\epsilon\mid a M b$

which is $LR(1)$ and definitely can not be written as $LL(1)$

---
Tags: formal-grammars, parsers
---


# Question
Title: simple but (seemingly?) tricky recurrence
I'm cross-posting from math stack exchange after receiving no answers there.

I came across the following very simple recurrence-style expression but am having trouble solving it: $$T(2n) \in \theta(T(n) \log(T(n)))$$ for sufficiently large $n \in \mathbb{N}$.

My first thought was to take the logarithm of both sides and apply the Master Theorem but the "$f(n)$" term unfortunately is not in the right form. Repeated expanding quickly yields a mess. Wolfram Alpha was no use.

Plugging in $T(n) = n^a$ makes the left side grow too slowly so $T$ must grow faster than any polynomial. But plugging in $T(n) = \exp(\log(n)^b)$, $b\>1$, causes the left side to grow too fast so $T$ must grow more slowly. So it seems $T$ is super-polynomial but *barely*.

What approaches are viable for such an equation?

# Answer
We shall asymptotically solve $\color{blue}{ f(2n) = f(n)·\log(f(n))·2^c }$ for any $c∈ℝ$ as $n → ∞$ (where $\log = \log\_2$). $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

~ ~ ~

Note that $\log\log(2n) = \log(\log(n)+1)$ $= \log\log(n)+\lfrac{r}{\log(n)}+\cdots$ where $r = \lfrac1{\ln(2)}$. (Omitted terms are asymptotically smaller.)

And $\log\log\log(2n) = \log\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)$ $= \log\log\log(n)+\lfrac{r^2}{\log(n)·\log\log(n)}+\cdots$.

Let $g$ be a function such that $f(n) = 2^{\log(n)·\log\log(n)+g(n)}$. We shall take for granted (I believe it can be proven with some effort) that $g(n) ≪ \log(n)·\log\log(n)$.

Then $f(2n) = 2^{\log(2n)·\log\log(2n)+g(2n)}$

$= 2^{\log(2n)·\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)+g(2n)}$

$= 2^{\log(2n)·\log\log(n)+g(2n)+r·\big(1+\lfrac1{\log(n)}\big)+\cdots}$.

And $f(n)·\log(f(n))·2^c$

$= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n)+g(n))+c}$

$= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n))+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+c}$

$= 2^{\log(2n)·\log\log(n)+g(n)+\log\log\log(n)+c+\lfrac{r·g(n)}{\log(n)·\log\log(n)}}$.

Thus $g(2n)-g(n) = \log\log\log(n)+(c-r)−\lfrac{r}{\log(n)}+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+\cdots$.

So $g(2^{k+1})-g(2^k) = \log\log(k)+(c-r)+\cdots$ as $k → ∞$.

Thus $g(2^k) = \sum\_{i=2}^{k-1} \log\log(i) + k·(c-r) + \cdots$.

$ = k·\log\log(k) + k·(c-r) + \cdots$.

Thus $g(n) = \log(n)·\log\log\log(n)+\log(n)·(c-r)+\cdots$.

Therefore $\color{blue}{ f(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r)+\cdots)} }$.

~ ~ ~

To check, letting $f\_1(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r))}$ we get:

$\log(f\_1(2n))$

$= \log(2n)·(\log\log(2n)+\log\log\log(2n)+(c-r))$

$= (\log(n)+1)·\big(\log\log(n)+\log\log\log(n)+(c-r)+\frac{r}{\log(n)}+\cdots\big)$

$\log(f\_1(n)·\log(f\_1(n))·2^c)$

$= \log(n)·(\log\log(n)+\log\log\log(n)+(c-r))+\log\log(n)+\log\log\log(n)+c+\cdots$.

So $\log(f\_1(2n)) - \log(f\_1(n)·\log(f\_1(n))·2^c) = \frac{r}{\log(n)} + \cdots$, as expected.

~ ~ ~

It may be possible to get an exact asymptotic solution, since we just have to find some $h$ such that $f(n) ∈ 2^{\log(n)·\big(\log\log(n)+\log\log\log(n)+(c-r)+h(n)+O(\lfrac1{\log(n)})\big)}$, but I'm not sure it's worth the trouble.
> 3 votes

# Answer
Let us attempt to solve the easier recurrence $T(2n) = T(n) \log T(n)$. Define $S(m) = \log T(2^m)$. Then $S(m+1) = S(m) + \log S(m)$. Let us heuristically convert this into a differential equation: $S' = \log S$. The solution to this equation is $S = \mathrm{li}^{-1} + C$, where $\mathrm{li}$ is the logarithmic integral. Roughly speaking, $\mathrm{li}(x) \approx x/\log x$, and so $\mathrm{li}^{-1}(x) \approx x\log x$. This heuristic implies that $S(m) \approx m \log m$, and so $T(n) \approx \exp \Theta(\log n \log \log n)$. Of course, at this point this is just an educated guess.

As a sanity check, suppose that $T(n) = \exp (\log n \log \log n)$, where all logarithms are base 2. Then $$ \begin{align\*} T(n) \log T(n) &= \exp (\log n \log \log n) \log n \log \log n \\ &= \exp (\log n \log \log n + \log \log n + \log \log \log n) \\ &= \exp (\log (2n) \log \log n + \log \log \log n). \end{align\*} $$ This is quite similar to $T(2n) = \exp (\log (2n) \log \log (2n))$ (though not the same).
> 3 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: On load estimation of memory consumption of program, is it possible?
In the book "Fundamentos de sistemas operativos" (Gunnar Wolf, Esteban Ruiz, Federico Bergero, Erwin Meza p.254) it says:

> Al cargar un programa el sistema operativo calcula cuánta memoria va a requerir a lo largo de su vida prevista. Esto incluye el espacio requerido para la asignación dinámica de memoria con la familia de funciones malloc y free.

It translates to:

> When loading a program, the OS calculates how much memory it will consume along its expected life. This includes the space required for dynamic memory allocation with the `malloc` and `free` function family.

Is this even possible? Can the OS calculate a sensible bound on memory usage? If so does Linux do that on program load?

I cannot find any other reference that explains this.

# Answer
That statement is incorrect. With most OS's we use today, the OS does not try to calculate in advance how much memory the process will use. Indeed, when we use dynamic memory allocation (such as malloc) it is typically impossible to predict how much memory the process might use.
> 1 votes

# Answer
Here's what the operating system could do at best: It could examine your computer, and find out what is the maximum amount of memory that can be successfully allocated. For example, if you have so much RAM, so much space for swap space on your hard drive etc. the OS could figure out something like "if you try to allocate more than 197GB in total, some allocations will fail".

It *may* be possible for a C or C++ program to figure out how much memory will be needed so the program can proceed to the beginning of the main() function.
> 1 votes

# Answer
Consider the code

```
scanf("%d", &size); malloc(size);

```

How will the compiler calculate the amount of memory ?

---

The fact is that a default size is allocated for the heap and the stack, and these might be increased on demand at run-time, depending on the memory manager.
> 0 votes

---
Tags: operating-systems, memory-management
---


title: How could NP-complete problems be in P?

text:
# Question
Title: How could NP-complete problems be in P?
I've learned some basics about P and NP. Please excuse if the following is not very precise.

I've read that NP-complete problems are the hardest problems in NP. (Is that correct?)

But now I'm wondering if P problems have polynomial runtime, and assuming P=NP for a moment, how can polynomial runtime problems ever have something like a "hardest problem"? How could polynomial runtime problems have a thing like the largest element?

EDIT: I just remembered that the notion of NP-complete being the "hardest" is defined up to polynomial transformations? And the comparability of P problems is a different thing. Is that the answer? Or can the notion of comparing P problems and NP-complete problems being the hardest be made similar?

# Answer
If a problem X is NP-complete, that means "I can solve any problem in NP by converting it into an instance of X that has the same YES or NO answer in polynomial time, and solving that instance.". We are very, very generous with "polynomial" factors here. n^2 and n^1000 are considered equal *in this context*, because it's just polynomial.

So with this background, if P = NP were true, then all problems in P would indeed be considered to be equally hard because we don't care about polynomial factors in this context.
> 1 votes

# Answer
$NP$-complete problems are the hardest problems in $NP$ with regard to the time required to solve them. Despite more than 50 years of research, nobody was able to design a polynomial time algorithm to solve one of them (nor to prove a supra-polynomial lower bound either). Actually, solving one of them in polynomial time also implies solving them all and all of the problems in $NP$ through the concept of reduction. In practice, that will imply $P = NP$.

Now, if $P = NP$, then $NP$-complete problems are obviously easy (by definition of $P$) with regard to the time required to solve them.
> 0 votes

---
Tags: np-complete, p-vs-np
---


# Question
Title: show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages
prove this language verifies the conclusion of the pumping lemma

> show that $L=\\{a^\*\\}\cup\\{b^ja^{n^2}|0\<j,1\leq n \\}$

> Holds the pumping lemma for context-free languages

the problem is that I know how to refute with pumping lemma that a language is **not context-free**. but I don't know how to prove Language holds the pumping lemma -\> **is a context-free** lang.

# Answer
One can never prove a language to be context-free with the use of pumping lemma alone. The pumping lemma for context-free languages states a property that is necessary but not sufficient for context-free languages. There are no context-free languages that lack a context-free pumping property, but there are languages that have this property despite not being context-free.

Let $s \in L$ with $|s| \geq p$ for some pumping length $p$ of $L$. I am going to show that for any such $s$, the $uvwxy$ division required by the pumping lemma is possible. Due to the definition of $L$, we know that one of the following is true:

1. $s = a^n$ for some $n \geq p$
2. $s = b^ma^n$ for some $m \geq 1$ and $n$ is a natural square

For each of these cases, there exists a trivial decomposition that satisfies the conditions of the pumping lemma. Can you find them?

Note that in the end, $L$ is not context-free, so this will serve as a proof of non-invertibility of the pumping lemma – you cannot use it to prove a language context-free.
> 0 votes

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


title: CFG to RG Conversion

text:
# Question
Title: CFG to RG Conversion
I'm struggling with this question. I would appreciate a detailed solution as it would help me better understand the subject.

Convert the following Context Free grammar into a Regular Grammar:
S -\> aSb | A
A -\> bA | a

# Answer
> 0 votes
No, you can't convert context free grammar into regular grammar **in general**. Because CFG is $Type{-}2$ grammar which has less restriction than $Type{-}3$ RG grammar. CFG generate more complex languages that RG can ever do.

When CFG generates a language which is regular then you must write equivalent RG for that regular language. But your grammar generates the language $a^nb^\*ab^n$, which is clearly not regular. That's why we are not able to write equivalent regular grammar for that language.

Every $Type{-}3$ RG grammar also satisfies conditions of $Type{-}2$, $Type{-}1$, $Type{-}0$ grammar. So we can say every $Type{-}3$ grammar is also $Type{-}2$ grammar but the converse isn't true.

**N. B.** \- Small suggestions you need to understand Chomsky Hierarchy very carefully.

---
Tags: regular-languages, context-free
---


# Question
Title: If A is Turing-reducible to B and B is Turing recognizable then A is Turing recognizable
I believe this is true and I have given a simple proof of this: If A is Turing-reducible to B then there exists a Turing machine with oracle for B that decides A, because B is Turing-recognizable then by using the oracle for B we can decide A and therefore A is Turing recognizable.

# Answer
The statement is false. Consider the language $H$ of the halting problem and let $H'$ be its complement.

$H'$ is Turing reducible to $H$ and $H$ is recognizable, however $H'$ is not recognizable (if $H'$ were recognizable then $H$ would be decidable).
> 1 votes

---
Tags: turing-machines, turing-recognizable
---


# Question
Title: Is it provably true/false that for a program, there exists a proof whether it halts or not?
##### A standalone statement of my question

Given a program that takes no argument, we are interested in whether the program will eventually terminate. My question is this:

Theoretically speaking, can we always find a proof of the termination/non-termination of a program?

##### Clarification

Unlike the general halting problem, this problem does not require a mechanical procedure to generate a proof for each program which can potentially depend on the procedure itself, but instead, it allows the proof to depend on the specified program. It is thus a much weaker version.

There are obviously some proofs for some terminations and some non-terminations, and there are cases that remain unknown to this day (such as the evaluation of incrementing a number until finding a counter example of Collatz conjecture).

But more generally, is there any result on this? Is it always possible to prove whether the program terminates or not? Or is it provable that some programs cannot be proved either ways?

(Note that the answer to this question does not require solving, say, Collatz conjecture because it will only say there is a proof maybe that it terminates or maybe that it does not)

##### What I have thought about?

Cases that are easy are these two:

1. If it terminates, we just run the program and the termination proves itself.
2. If it falls into some repetitive periods, we track the history of all variables and we can prove that it does not terminate by remarking that it goes into a loop after certain step.

One case remains where the non-termination will never fall into periods and keep visiting new states. In this case, my first thought is that it comes down (almost) to prove the unboundedness (of some sort) of a sequence (of some kind of structures) defined by a program. So maybe a weaker version of my question would be: Is the unboundedness of a sequence of natural numbers (generated by the program) always provable?

# Answer
> 31 votes
Actually this is no different from the halting problem unsolvability. If you have any formal system T with a proof verifier program V that can reason about programs (as you desire in your question), then let H be the program that does the following on input (P,X):
For each string s in length-lexicographic order:
If V( "Program P halts on input X." , s ) then output "true".
If V( "Program P does not halt on input X." , s ) then output "false".
Here V(Q,s) outputs "true" if s is a valid proof of Q and "false" otherwise. V *always* halts, because that is what it means for T to have a proof verifier program. (And we cannot use and do not care about formal systems that do not.)

Now, **if** for every (P,X) there is always a proof over T of either "Program P halts on input X." or its negation, **then** H solves the halting problem (because H eventually checks each possible proof), which is impossible.

Here I am assuming that your T is sound for program halting (i.e. does not prove a false statement about program halting). Otherwise, it is possible that T proves the wrong thing and hence H fails to solve the halting problem.

By the way, unsolvability of the halting problem and another computability question called the zero-guessing problem are very important facts that can be used to easily prove the **generalized incompleteness theorem**, by essentially the same kind of reasoning. Incidentally, Godel proved his incompleteness theorem for PA under an assumption called ω-consistency, which is essentially equivalent to PA being sound for program halting. Rosser removed that assumption by a clever trick. But Rosser's version also can be proven easily using the zero-guessing problem instead of the halting problem.

# Answer
> 5 votes
> Unlike the general halting problem, this problem does not require a mechanical procedure to generate a proof for each program which can potentially depend on the procedure itself, but instead, it allows the proof to depend on the specified program. It is thus a much weaker version.

The general halting problem already allows such program-specific proofs. Your stated problem is in fact completely identical to the general halting problem. Perhaps you have underestimated the potential complexity of what you call "mechanical procedures"? It is theoretically possible, though incredibly difficult, to create a "mechanical procedure" that duplicates the full capabilities of an expert living sapient human mathematician.

> Or is it provable that some programs cannot be proved either ways?

If a program does halt, then it can be proven by simply running it until it halts. Any proof that a program cannot be proven to halt is therefore inherently a proof that it does not halt. "Cannot be proven either way" is a self-contradictory and thus invalid result of a proof about whether a particular program halts.

# Answer
> 0 votes
When you make an informal statement like "Is it provably true/false that for a program, there exists a proof whether it halts or not?", the "a" article is interpreted as a universal quantifier: if we increase the formality of the question it becomes: for every program P, is there a halting proof?

And this is what the Halting Problem informs us that there isn't, with careful definitions of what is meant by program and proof.

> *Unlike the general halting problem, this problem does not require a mechanical procedure to generate a proof for each program which can potentially depend on the procedure itself, but instead, it allows the proof to depend on the specified program*

Here you seem to be expressing a belief that mechanical generation is qualitatively different from human generation: that if we allow a human to inspect every one of the infinite set of programs, the human may be able to decide halting every case, without it being possible to replicate what the human is doing by an algorithm, because the human isn't simply mechanical but "super mechanical".

Even if that were the case, it would mean that the human is somehow more powerful than a Turing machine. You would then have to carefully articulate the domain which is covered in your claim: that your claim isn't whether a Turing machine can decide halting over the domain of Turing machines, but whether a Human machine (possessing some magic oracle powers that transcend the power of Turing machines) can decide halting over the domain of Turing machines.

If we rephrase the statement along these lines, the answer is a resounding yes: machines from a domain more powerful than Turing machines can decide halting of all Turing machines.

Practically speaking, all we have is computers that are (not even quite) Turing machines. So the Turing machine set is of particular interest, because the results inform us about the limitations of the computers that we have.

If something cannot be "mechanically", you're not going to program your PC into solving it.

> *Given a program that takes no argument*

This "no argument" requirement is a red herring; if you believe it makes any difference, you have to readjust your thinking.

We can take any program P which has an external input that is given to it as an argument, into an equivalent program Q which embeds that input and then takes no argument.

The set of all programs P with no arguments is exactly the same as the set of programs Q(I), which have inputs, for all possible inputs I. All the possible Q(I) pairs can each be combined into a single program image P.

Consider that the machine which Turing used to explore this problem domain doesn't have any arguments either: it is a combination of a simple mechanism, and a tape that loaded with some initial contents.

A program P with no arguments loaded into a machine is exactly the same thing as a Turing tape loaded into a tape machine; we can replace "given a program with no argument" with "given a Turing tape".

# Answer
> -2 votes
If you're really asking about every program then of course not. Such proof would need to consider every possible outcome of every choice within the most complex program imaginable… which would make the proof more complex than the program, which would spin on its own axis until it ceased to matter.

If "for a program…" doesn't mean "for any and all programs" then what does it mean?

# Answer
> -3 votes
This is basically the Church-Turing hypothesis.

We know there are programs P such that no program X can prove that P halts, or that P doesn't halt. That's not what you asked. You asked "can we prove..." The Church-Turing hypothesis claims that everything "we" can do, some program could do. If the Church-Turing hypothesis is correct, then "we" cannot prove for every program that it halts. If it is incorrect, then "we" might be able to prove it for every program.

I can easily write a program that halts if it finds a counter-example to Fermat's Last Theorem, and that *will* eventually find a counter-example if one exists. "We" (or rather Andrew Wiles) proved that this program doesn't halt. It's not at all obvious that a computer program could have found this proof. Church-Turing says "yes".

Just for fun: If that FLT-counter-example-finder halts, then there is actually a very simple proof that it halts. (The proof would look like "The program will halt with a = xxx, b = xxx, c = xxx, n = xxx". ). So if there is no proof that it halts or doesn't halt, then it doesn't halt, but we might not have a proof for it.

---
Tags: logic, halting-problem, termination
---


# Question
Title: Disjoint Set union complexity when makesets, unions and finds follow a certain order
Consider an arbitrary sequence of $m$ MAKESET operations, followed by $u$ UNION operations, followed by $f$ FIND operations, and let $n = m + u + f$ in a disjoint set union data structure. Prove that if we use union by rank and FIND with path compression, all $n$ operations are executed in $O(n)$ time.

I'm not sure how to prove this bound - the obvious answer is something like $O(m + \alpha(u+f))$ but this isn't $O(n)$.

# Answer
> 1 votes
The $m$ makeset and the $u$ union operations are executed in time $O(m+u)$, so we only need to argue about the time spent in the find operations. Since this time is proportional to the overall number of traversed nodes, we can focus on this latter quantity instead.

Imagine that all nodes are initially unmarked. An unmarked node $u$ becomes marked when a find($x$) operation is performed and $u$ lies in the unique path between $x$ and the root of the tree containing $x$. Notice that, as soon as find operation encounters a node $v$ that was previously marked, it completes by traversing $v$ plus at most $1$ additional node. This is because path compression (and the fact that we do not perform any additional merge operation) ensures that $v$ is at depth at most $1$.

The overall time spent by all find operations is then $O(f+t)$, where $t$ is the number of times a node becomes marked. Clearly $t = O(m)$.

---
Tags: time-complexity, disjoint-sets
---


# Question
Title: Computer Architecture MIPS assembler with predictors
This MIPS code is given:

```

loopA: lw $t0, 0($s1)          # $ array element
       addu $t0, $t0, $s3      # add scalar in s3
       sw $t0, 0($s1)          # store result
       addi $s1, $-4           # decrement pointer
       bne $s1, $zero, loopA   # branch if s1!=0

loopB: lw $t0, 0($s2)          # $ array element
       addu $t0, $t0, $s3      # add scalar in s3
       sw $t0, 0($s2)          # store result
       addi $s2, $-4           # decrement pointer
       bne $s2, $zero, loopB   # branch if s2!=0

```

The code is going from top to bottom, passing first trough loopA, and the loopB accordingly. After every passing a constant in $s3 is added to each element(which value is not important).

* The address of the last element of field A is given in the register $s1 and it is equal to 80;
* The address of the last element of field B is given in the register $s2 and it is equal to 100;

We need to use static predictor for branching with strategy that predicts that there will NOT be branching. How many times will there not be stop because of control conflict, in other words how many times the predictions will be right?

The other two question are the same, but:

1. What if we use dynamic predictor with 1 bit, initially set to 0(there will not be branching)?
2. What if we use dynamic predictor with 2 bits, initially set to 11(there will be branching)?

# Answer
I found an answer to this question and want to answer it, in case someone else needs it.

First we find from the question that `$s1` and `$s2` are the last element from their fields, and they are equal to 80 and 100.

First we see that the code goes trough the loopA and then the loopB, we see that

```
addi $s1, $-4   #in loopA

addi $s2, $-4   #in loopB

```

are the same but with the different registers.

After that we see that the program substracts each of them with 4(four) every time the loop goes trough the fields.

So if we find how many 4(fours) are in:

* first: 80
* second: 100

We should be able to find how many iterations are there.

By dividing 80 with four, and 100 with four we get

loopA: 80/4 = ***20***

loopB: 100/4 = ***25***

together = 20+25 = ***45*** iterations in total.

Now we first focus on the static predictor: The static predictor predicts ***static***, which means it will not change no matter what. It is initially set to 0.

1. We see that from the 45 in total iterations the ***static*** predictor will be right only 2 times, when it will exit loopA, and when it will exit loopB. So the answer to the first question is ***2*** times.
2. Second we use dynamic predictor with 1 bit initially set to 0(there will not be branching). This dynamic predictor changes every time when it gets wrong or right value. from 0 to 1 if right, and from 1 to 0 if wrong. From the 45 total iterations, only 4 times the predictor will be wrong. We see that first the predictor is set to 0, so it will mistake one time entering loopA. Then it will change to 1. When exiting loopA it will miss again setting the bit to 0. When entering loopB it will be set to 0, but we find out that there will be branching, so it goes wrong one more time, while it gets the value 1. After that we see that it will be wrong one last time while exiting loopB. So from the total it will ***miss*** 4 times. We need the amount of iterations when the predictor is ***right***, so we substract 45 - 4 = ***41*** times it will be right. The bit will be ***0*** at the end. 0-\>1-\>0-\>1-\>0
3. Lastly with the dynamic predictor we have the same thing, so I will make a smaller explanation. Firstly the bits are set to: 11-\>10-\>11-\>10 (changing of bits) 1 miss when exiting loopA and 1 miss when exiting loopB. 45 - 2 = ***43*** times it will be right with two bits set to ***10*** at the end.
> 1 votes

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