# Question
Title: Why are functional languages Turing complete?
Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far:

* Functional programming is based off of Lambda Calculus, formulated by Alonzo Church.
* Imperative programming is based off of the Turing machine model, made by Alan Turing, Church's student.
* Lambda calculus is as powerful and able as the Turing Machine,
meaning they are equivalent in computational power.

If functional programming is based off of Lambda Calculus and not the Turing machine, then why are some (or all) of them described to be Turing complete, and not Lambda complete or something like that? Is the term "Turing completeness" special in any way to Turing machines, or is it just a word?

Lastly, if imperative languages are based off of the Turing Machine, and computers are basically Turing machines, without infinite memory, does that mean they perform better than functional programming languages on our modern PCs?

If that's the case, then what would be the equivalent of a lambda calculus machine?

I know this seems to be 3 separate questions, but they're all closely related, and each is dependent on the previous question being a valid question to begin with.

# Answer
> 29 votes
**In a nutshell**:

What characterizes imperative programming languages as close to Turing machines and to usual computers such as PCs, (themselves closer to random access machines (RAM) rather than to Turing machine) is the concept of an **explicit memory** that can be modified to store (intermediate results). It is an automata view of computation, with a concept of a state (comprising both finite state control and memory content) that can change as the computation proceed.

Most other models are more abstract. Though they may express the computation as a succession of transformation steps of an original structure, these transformation are applied in a sort of intemporal universe of mathematical meanings. This may preserve properties, such as referential transparency, that may make mathematical analysis simpler. But it is more remote from natural physical models that rely on the concpet of memory.

Thus there are no natural functional machines, except in a larger sense as explained below, since software is not really separable from hardware.

The reference to Turing as the yardstick of computability comes probably from the fact that his model, the Turing machine was closest to this physical realizability constraint, which made it a more intuitive model of computation.

**Further considerations**:

There are many models of computation, which were designed to capture in the most general possible way the concept of a computation. They include Turing machines, actually in many different flavors, the lambda calculus (flavors too), semi-Thue rewriting systems, partial recursive function, combinatory logic.

They all capture some aspects of the various techniques used by mathematicians to express or conduct computations. And most have been used to some extent as the basis of some programming language design (e.g. Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus) and can often be combined in diverse ways in modern programming languages.

One major result is that all these computation models were proved equivalent, which lead to the Church-Turing thesis that no physically realizable models of computation can do more than any of these models. A model of computation is said *Turing complete* if it can be proved to be equivalent to one of these models, hence equivalent to all of them.

The name could have been different. The choice of the Turing machine (TM) as the reference is probably due to the fact that it is probably the simplest of these models, mimicking closely (though simplistically) the way a human computes and fairly easy to implement (in a limited finite form) as a physical device, to such an extent that Turing machines have been constructed with Lego sets. The basic idea requires no mathematical sophistication. It is probably the simplicity and realizability of the model that gave it this reference position.

At the time Alan Turing created his computing device, other proposals were on the table to serve as formal definition of computability, a crucial issue for the foundations of mathematics (see Entscheidungsproblem). The Turing proposal was considered by the experts of the time as the one most convincingly encompassing known work on what calculability should be (see *Computability and Recursion*, R.I. Soare, 1996, see section 3.2). The various proposals were proved equivalent, but Turing's was more convincing. <sub>\[from comments by Yuval Filmus\]</sub>

It should be noted that, from a hardware point of view, our computers are not Turing machines, but rather what is called Random Access Machines (RAM), which are also Turing complete.

Purely imperative language (whatever that might mean) are probably the formalisms used for the most basic models, such as Turing machines, or the assembly language (skipping its binary coding) of computers. Both are notoriously unreadable, and very hard to write significant programs with. Actually, even assembly language has some higher level features to ease programming a bit, compared to direct use of machine instructions. Basic imperative models are closed to the physical worlds, but not very usable.

This led quickly to the development of higher level models of computation, which started mixing to it a variety of computational techniques, such as subprogram and function calls, naming of memory location, scoping of names, quantification and dummy variables, already used in some form in mathematics and logic, and even very abstract concepts such as reflection (Lisp 1958).

The classification of programming languages into programming paradigm such as imperative, functional, logic, object oriented is based of the preeminence of some of these techniques in the design of the language, and the presence or absence fo some computing features that enforce some properties for programs or program fragments written in the language.

Some models are convenient for physical machines. Some others are more convenient for a high-level description of algorithms, it that may depend on the type of algorithm that is to be described. Some theoretician even use non deterministic specification of algorithms, and even that cn be translated in more conventional programming terms. But there is no mismatch problem, because we developed a sophisticated compiler/interpreter technology that can translate each model into another as needed (which is also the basis of the Church-Turing thesis).

Now, you should never look at your computer as raw hardware. It does contain boolean circuitry that does very elementary processing. But much of it is driven by micro-programs inside the computer that you never get to know about. Then you have the operating system that makes your machine appear even different from what the hardware does, On top of that you may have a virtual machine that executes byte-code, and then a high-level language such as Pyva and Jathon, or Haskell, or OCaml, that can be compiled into byte code.

At each level you see a different computation model. It is very hard to separate hardware level from the software level thus to assign a specific computational model to a machine. And since they are all intertranslatable, the idea of an ultimate hardware computation model is pretty much an illusion.

The lambda calculus machine does exist: it is a computer that can reduce lambda calculus expressions. Ad that is easily done.

**About specialized machine architectures**

Actually, complementing Peter Taylor's answer, and following up on hardware/software intertwinning, specialized machines have been produced to be better adapted to a specific paradigm, and had their basic software written in a programming language based on that paradigm.

These include

Fundamentally, these are also imperative hardware structures, but mitigated with special harware features or microprogrammed interpreters to better adapt to the intended paradigm.

Actually, hardware specialized for specific paradigms does not seem to have ever been successful in the long run. The reason is that the compiling technology to implement any paradigm on vanilla hardware became more and more effective, so that specialized hardware was not so much needed. In addition, harware performance was fast improving, but the cost of improvement (including evolution of basic software) was more easily amortized on vanilla hardware than on specialized hardware. Specialized hardware could not compete in the long run.

Nevertheless, and though I have no precise data on this, I would suspect that these ventures left some ideas that did influence the evolution of machines, memories, and instruction sets architecture.

# Answer
> 24 votes
Turing-complete is just a name. You can call it Abdul-complete if you want. Names are decided upon historically and are often named after the "wrong" people. It's a sociological process that has no clear criteria. The name has no meaning beyond its official semantics.

Imperative languages are not based on Turing machines. They are based on RAM machines. Your computer is a RAM machine. Turing machines are a nice theoretical model, but they are not a very good model of actual computers.

Programming languages based on other paradigms can be very successful, even though the underlying CPU doesn't support them natively; for example, printers run a stack language. There is more to programming than machine code.

# Answer
> 12 votes
Because "Turing-complete" just means "it can compute whatever a Turing machine can compute."

# Answer
> 8 votes
One of your questions doesn't seem to have been answered yet:

> If that's the case, then what would be the equivalent of a lambda calculus machine?

A Lisp machine. Hardware designed specifically to fit the LISP model of computation. The Wikipedia article talks about commercial products, but my director of studies at university had a hand-built one in his office.

# Answer
> 1 votes
functional languages in the form of lambda calculus invented by Church were *proven* Turing complete. this is an actual mathematical proof that can be found in published scientific papers by "reducing" lambda calculus to operations/ calculations on Turing machines. around the time of Turings paper 1936 and after, different "comprehensive" models of computation were proposed/ circulating. it was *not immediately realized* that all were equivalent. the proof(s) that they were equivalent were published roughly in the late 1930s and 1940s *after* Turings paper.

the Turing machine is *conceptually (but not functionally) simpler* than the other models and that is likely a significant part of the reason that Turing completeness is named after him. other ideas such as lambda calculus are more abstract and started out/ originated mainly in math/ logic theory. Turing proposed a theoretical *machine*. a *"machine"* is literally a *"physical device"*. its a remarkable conceptual object/ construction that ties together/ unifies two different worlds, the applied and the theoretical. it gives new abstract meaning to physical entities eg "time and space". it is not a mere coincidence that mathematicians sometimes refer to "technology," "machinery," or "devices" of proofs. Turing managed to ingeniously fuse all this in his conceptual invention. its *definition* is quite simple but analysis of it exhibits some of the most extraordinary *emergent behavior* ever seen in the history of scientific/ mathematical thought. Turing was the first scientist/ mathematician to grasp much of this significance/ power/ potential.

---
Tags: computability, turing-machines, programming-languages, lambda-calculus, turing-completeness
---


# Question
Title: Can you get O(n) with a word frequency algorithm?
By a word frequency algorithm: An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document.

For example:

in:"Hello my name is Hello" out: {'Hello':2, 'is':1, 'my':1, 'name':1}

In my implementation, I used a hash table to store the words.

But I've seen uses of a trie, but I don't understand why this improves runtime.

I've read that you can get O(n). I assume with a trie correct?

# Answer
If the size of the alphabet is constant and $n$ denotes the length of the document (i.e. the total number of characters), you can indeed use Tries to get $O(n)$ running time - regardless of the length of the words.

In a Trie, you can search for (or insert) a word in time linear in the length of the word. You can use a Trie to keep track of the words as you encounter them in the text, and in each Trie node corresponding to a word you can store that word's frequency (which is updated each time you encounter it).

The running time of this algorithm is indeed $O(n)$: the sum of all the lengths of the words in the documents is precisely the length of the document. Note that you can also traverse the Trie (and list the words it contains to generate the desired output) in $O(n)$ (since the number of nodes in the Trie is at most $n$).
> 3 votes

# Answer
There is a lower bound of $\Omega(n\log n)$ in the comparison model for ELEMENT DISTINCTNESS, which is the following problem: given $n$ elements, decide whether they are all different. Your task can be used to solve ELEMENT DISTINCTNESS, so in the comparison model (if you are only allowed to compare elements) there is no $O(n)$ algorithm.

Using a hash table, you can indeed guarantee a running time of $O(n)$ on average. That doesn't contradict the lower bound since you are taking hashes of strings, which is not allowed in the comparison model.
> 2 votes

---
Tags: algorithms, runtime-analysis, lower-bounds, data-mining, information-retrieval
---


# Question
Title: Finding a segment which has equal number of segments before and after it
I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self:

Given a set of n segments $\[a\_i ,b\_i\]$ where $i=1,..,n$ and $a\_i \< b\_i$. write an algorithm which find a segment that the number of segments $\[a\_l ,b\_l\]$ before it $(b\_l \< a\_i)$ are equal to the number of segments $\[a\_r ,b\_r\]$ after it $(b\_i \< a\_r)$ the algorithm will return its index if found else null

The algorithm should work in $O(n\log n)$ in worst case.

My solution is:

1. running heapsort by $a\_i$ (runs in $O(n\log n)$)
2. running bucket sort by $b\_i$ which each bucket is $a\_i$ (runs in $(O(n))$)
3. loop on each member (X) in reverse order and finding using binary-sort on the rest of the set the segment (Y) which its $b\_i$ is equal or max close to $a\_i$ and writing in the Y the distance of X from the end of list (number of segments which are right of Y) and writing in X the index of Y (number of segments which are left of X). that happens in (runs in $O(nlgn)$)
4. loop on each member the looking up for an element with (left\_count equals right\_count) not equals zero and return it (runs in $O(n)$)
5. if nothing found - return null

So finally the algorithm works in $2lgn + 2n$ which is $O(nlgn)$

Am I right? There is a better solution?

# Answer
Here is an algorithm that achieves $O(n\log n)$ complexity without any elaborate data structures. Just a simple sort and a couple of loops.

1. Sort all the $\\{a\_i,b\_i\\}$ together. Call the resulting sequence $(x\_1,\ldots,x\_{2n})$.
2. Set $n\_a\gets0$, $n\_b\gets0$.
3. Loop for $n\_b$: For $t$ going from $1$ to $2n$ do:
    1. If $x\_t=b\_i$ for some $i$, increment $n\_b$
    2. Else if $x\_t=a\_j$ for some $j$, set $L\_j\gets n\_b$
4. Loop for $n\_a$: For $t$ going from $2n$ down to $1$ do:
    1. If $x\_t=a\_i$ for some $i$, increment $n\_a$
    2. Else if $x\_t=b\_j$ for some $j$, set $R\_j\gets n\_a$
5. Now for each interval $\[a\_i,b\_i\]$, $L\_i$ and $R\_i$ contain the number of intervals to its left and to its right, respectively
6. Final loop: For $i$ going from $1$ to $n$
    1. If $L\_i=R\_i$, return $i$
7. Found nothing: Return null.

You might need to make some additional checks to take care of cases where $a\_i=b\_j$ for $i\not=j$.

Note that equality checks of the form $x\_t=b\_i$ can be done by saving the sorting indices. In other words, if you sort an array $u$ into another array $v$, you can save indices $\pi\_t$ such that $u\_t=v\_{\pi\_t}$.
> 2 votes

# Answer
$O(n \lg n)$ time is achievable without any fancy techniques. So, yes, there is a better solution, if "conceptually simpler" and "simpler to implement" counts as better.

Store all of the intervals in a segment tree. Augment the data structure so that each node stores the number of intervals to the right of that node; as well as the number of intervals to the left of that node. These values can be filled in easily by a bottom-up traversal. Now a simple linear scan can be used to check whether such a segment exists.

The running time is $O(n \lg n)$: it takes $O(n \lg n)$ time to build the tree, $O(n)$ time to do the bottom-up traversal, and $O(n \lg n)$ time to check all the segments (since a segment can be looked up in the tree in $O(\lg n)$ time), for a total of $O(n \lg n)$ time.

---

Can you find an algorithm that is asymptotically faster than $O(n \lg n)$ time? Well, any algorithm that involves sorting will automatically take $\Omega(n \lg n)$ time (under semi-reasonable models), so no such algorithm can be faster than $O(n \lg n)$ time.

It might possible to achieve $O(n)$ time, using fancy techniques -- in particular, by trying to adapt QuickSelect to this problem -- but the resulting algorithm will likely be more complex, so if ease of implementation is a significant factor, such an approach might not better in practice.
> 1 votes

---
Tags: algorithms, time-complexity, search-algorithms, sorting
---


title: Algorithm for finding the root element

text:
# Question
Title: Algorithm for finding the root element
I have the following interface:

```
public interface TreeElement<T>{
    public List<TreeElement<T>> getChildren();
}

```

Now, suppose I have a collection of `TreeElement<T>` representing a ***valid*** tree. How to find it's root element? Is there something more efficient than iterating over the whole collection?

# Answer
I will make slightly stronger assumptions than that are provided in the question: we have a data structure, representing a tree, that consists of an array of vertices of the tree (allowing random access) and given a vertex, we have access to an array containing that vertex' children (again allowing random access). Furthermore we can check vertices for equality, and given a vertex we can (in $O(1)$ time) locate it in the main array.

On a tree of $n$ nodes, any strategy must take at least $\Omega(n)$ time in the worst case.

Consider a path of $n$ vertices. Define a vertex to be "examined" if it is accessed via the main array, via a children array or is reported as the root. Every non-leaf vertex must be examined by the algorithm: if some non-leaf vertex $v$ is not examined, we can make $v$ the root, making $v$'s child a child of $v$'s predecessor. This is not seen by the algorithm and it will incorrectly report the old root: making $v$ changes its children array (which is not seen by the algorithm as $v$ is not accessed at all) and changes the child array of $v$'s parent (which by the assumption of $v$ not being examined is not seen by the algorithm either).

Thus every non-leaf vertex in a path must be examined and any algorithm thus takes $\Omega(n)$ time.
> 4 votes

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


# Question
Title: Disprove that a function exists that counts the turing machines that halt on $\epsilon$
> Let $L(M\_k) = \\{ \langle M \rangle | M \text{ halts on }\epsilon \\} \cap \Sigma^k $
>
> Disprove that $\exists f\colon N \rightarrow \Sigma^\* . f(k)=\langle M\_k \rangle$.

I am not sure where I am wrong:

I said that I can convert the question to whether the language of all the Turing machines that accept the language $L(M\_k)$ is decidable, because if indeed:

$$X = \\{ \langle G \rangle | L(G)=\\{ \langle M \rangle | M \text{ halts on } \epsilon \\} \cap \Sigma^k \\} \in R$$

then there will be enumerator that can count all the Turing machines and therefore there will exist a function from $N$ that will return the description of the Turing machine $M\_k$ (the function will be the enumerator).

And I proved why the $X$ is not decidable and therefore the function $f\colon N \rightarrow \Sigma^\* . f(k)=\langle M\_k \rangle$ does not exist.

Where am I wrong?

# Answer
> 2 votes
Your question seems to be confusing machines and languages. Define $L\_k$ to be the set of encodings of Turing machines of length $k$ that halt on the empty input. The language $L\_k$ is finite, and so computable. In particular, there is a function $f\colon N \to \Sigma^\*$ satisfying $L(f(k)) = L\_k$ (in fact, infinitely many such functions). What you want to show is that there is no *recursive* function satisfying this property.

The proof is by contradiction. Suppose that there were such a computable function $f$. Now suppose you are given the description $\langle T \rangle$ of some Turing machine, of length $k$, and you want to know whether it halts on the empty input. You compute $f(k)$, and check whether $\langle T \rangle \in L(f(k))$.

Here is a more challenging question: Is the function $g(k) = |L\_k|$ computable? (This function gives the number of Turing machines of size $k$ that halt on the empty input.)

---
Tags: turing-machines, undecidability, computation-models
---


# Question
Title: How does Knuth measure the running time of this program?
I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand for the number of times around the loop, and where instruction fetch and memory accesses cost one unit, so for example $r2\gets m$ costs two units because it's an instruction fetch, and you need to fetch $m$ from memory.

My question is what does $a$ mean in these equations? How can the instructions associated with the `not found` label execute more than once, rather than $a$ times? Given the nondeterminism of whether you'll execute the `not found` instructions depending on the contents of $A$, I can expect there's a special way of dealing with it in the analysis, but I don't follow him in the paper where he claims the total running time based on this analysis is $6n+10$. He says (+ 3 if `not found`), implying that $a$ is $1/2$, but using that assumption, the total sum comes out to $6n+8.5$, (+3 if `not found`). Is this some common notation I'm missing? No where in the paper is $a$ defined.

# Answer
Knuth's $a$ is not standard notation. Here it's just a flag which is $0$ if the element was found and $1$ if it wasn't found. When I sum the elements in his table I get $6n + 10 + 3a$, so it's $6n + 10$ if the element is found and $6n + 13$ if it's not found (which is $3$ more).
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis
---


title: Question about the Simon's algorithm

text:
# Question
Title: Question about the Simon's algorithm
This comes from trying to understand the "Simon's algorithm".

So we have a set of $2^n$ kets $|x\_i \rangle$ one each for $i \in \\{0,1\\}^n$. Each $x\_j \in \\{0,1\\}^n$. And we have the further constraint that $x\_i = x\_j$ iff $i = j + s \pmod{2} = j \oplus s$ (bitwise addition modulo $2$) for a certain $s \in \\{0,1\\}^n$. (so every $|x\_k\rangle$ is guaranteed to have a second copy)

Now one has this state given as $\psi\_a = \frac{1}{\sqrt{2^n}}\sum\_{i \in \\{0,1\\}^n} |i\rangle|x\_i\rangle $ So this is a state of some 2 qubit system.

* Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi\_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x\_j\rangle$ for some $j \in \\{0,1\\}^n$?

---

* Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi\_b$s? Then it would make some sense that the only things one sees are these $\psi\_b$ states.

But this would still not clarify the weird probability addition that is happening here as shown below.

---

One notes that the state $\psi\_b$ will be obtained with a probability of $(\bar{\psi\_b} \psi\_a)^2 = (\frac{ 2}{ \sqrt{2^{n+1} }})^2 = 1/2^{n-1}$. These $\psi\_b$s obviously do not span the entire $2^{2n}$ dimensional Hilbert space available to these two qubits. They are not a basis.

* But the probabilities don't add up rightly either $\sum\_b ( \bar{\psi\_b} \psi\_a )^2 = 2$. Wonder is the interpretation of the fact that the probabilites over all these possibilities seem to add up to $2$!
* Some explanations I found say that these states $\psi\_b$ being the only possibilities is forced because of the fact that the second qubit is being measured in the "computational basis". This argument is not clear to me.

# Answer
I'm not sure I get all your questions. I'll try to answer according to my interpretation of what you are asking, and you can clarify if I got you wrong.

> * Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi\_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x\_j\rangle$ for some $j \in \\{0,1\\}^n$?

First, there is no second qubit, but a second system (of $n$ qubits). Next, consider $\psi\_a$, and recall that for any $f(x\_j)$ there are only two preimages $j$ and $j\oplus s$, then if you measure $f(x\_j)$ at the second system, the first system must either be $j$ or $j\oplus s$.

> * Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi\_b$s? Then it would make some sense that the only things one sees are these $\psi\_b$ states.

Kind of. However, you don't measure $\vert\psi\_a\rangle$ directly. There is another hadamard gate which is missing there. I.e., you measure $$(H\otimes I) \left\vert\psi\_a\right\rangle = \frac1{2^n}\sum\_x\sum\_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle$$

Now if you re-arrange it properly, it should give \begin{align\*} \frac1{2^n}\sum\_{x\in\\{0,1\\}^n}\sum\_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle &= \frac1{2^n}\sum\_{j\in XS}\sum\_i (-1)^{i\cdot j}\left\vert i\right\rangle\left\vert f(j)\right\rangle + (-1)^{i\cdot (j\oplus s)}\left\vert f(j\oplus s)\right\rangle \\ &= \frac1{2^n}\sum\_{j\in XS}\sum\_i \left ((-1)^{i\cdot j}+(-1)^{i\cdot j}(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \\ &= \frac1{2^n}\sum\_{j\in XS}\sum\_i (-1)^{i\cdot j}\left(1+(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \end{align\*} Where $XS\subseteq \\{0,1\\}^n$ is the largest subset such that if $j\in XS$ then $\forall j'\in XS, f(j)\ne f(j')$; so that the sum over $j$ is only over half the space and we don't count twice $x=j$ and $x=j\oplus s$. But note that $f(j)=f(j\oplus s)$ which we use in the second transition.

The above shows that for any $i$ for which $s\cdot i=1 \mod 2$ there is a destructive interference that cancels these terms, and you are left with only $i$'s for which $s\cdot i=0 \mod 2$. Thus, any $i$ you will measure (at the first system) must satisfy $s\cdot i=0 \mod 2$.
> 1 votes

---
Tags: complexity-theory, information-theory, quantum-computing
---


# Question
Title: Defining the halting problem for non-deterministic automata
The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic.

Hence my own understanding of the halting problem is primarily for deterministic TM, though I am aware that it may be considered for other kinds of automata.

I also noticed that determinism is often more or less implicit in the way people often refer to TM or to the halting problem. The wikipedia page on the halting problem is a good example of that.

But, there seem no reason for such a limitation. Given a family $\mathcal F$ of automata that can be non-deterministic, the halting problem for $\mathcal F$ may be defined as:

> Is there a uniform decision procedure such that, given an automaton $A\in\mathcal F$ and an input $x$, it can decide whether there is a halting computation of $A$ on input $x$.

(This is not quite the same as saying that the computation of $A$ with input $x$ will terminate.)

Indeed, that seem the only way to give some sense to discussions about the halting problem for Linear Bounded Automata (LBA) which are primarily non-deterministic automata.

So my question is whether I am correct, and whether there is a reason (and which reason) for this apparently second class treatment of the halting problem for non-deterministic automata.

# Answer
There are a few reasons I think we put less effort into the Halting problem for non-deterministic models.

The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$:

* Does there exist a valid run of $M$ on $x$ which halts?
* Does there exist a valid run of $M$ on $x$ which doesn't halt? i.e. do all valid runs halt?

For deterministic machines, these are identical, since there is exactly one valid run of $M$ on an input $x$. But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application.

Secondly, non-deterministic models are already unrealistic: they assume that you either have a magical box telling you which path to take, or that you have some form of infinite parallelism. Since non-deterministic and deterministic Turing Machines are equivalent in power, in most cases you just convert the machine into a determinstic one before you worry about halting.

As an extension of this, we don't care because proving something about a non-deterministic machine is at least as hard as proving something about an equivalent deterministic machine. We already know that there's no solution to the deterministic Halting Problem, so all it's really useful for is proving other problems undecidable through reductions. And it's always going to be less work to reduce to the deterministic halting problem, since it's easier than it's non-deterministic counterpart.
> 12 votes

# Answer
The halting problem is the quintessential $\Sigma\_1$-complete problem, since it can be stated as:

> $H(P,x) \leftrightarrow \exists c \\, \text{ s. t. $c$ is a halting computing of $P$ on $x$}$.

This suggests that your definition is a correct one. In general, every $\Sigma\_1$-complete definition is "correct".
> 6 votes

# Answer
you say there is an "apparent second class treatment" of the halting problem for nondeterministic machines. it does appear that nondeterminism was not considered historically until long after Turings creation of the deterministic TM & this may have something to do with research focus in the area. however the main point here is that the nondeterministic problem can easily be reduced to the deterministic problem, so one only needs to study the deterministic problem "without loss of generality".

furthermore, to counter the idea of "2nd class" here is at least one ref/ paper that studies the halting problem for nondeterministic machines and finds useful/ deep connections. some circumstantial evidence along the lines that CS research is so vast/ specialized, sometimes some starting research has been done in most areas, even seemingly narrow, and it can approach nearly meaningless or hairsplitting to rank different problems in their importance. and quite to the contrary, nondeterminism seems a very deep/ ubiquitous/ crosscutting concept in CS (key open questions like P vs NP are on it) & that aspect is likely to continue long into the future.

> Abstract. The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of different areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.
> 2 votes

# Answer
## In a nutshell

There seems to be no good reason to neglect the halting problem in settings that are not the classical one of deterministic Turing machines, other than the fact that the classical halting problem answers some major mathematical questions (such as the Entscheidungsproblem), while variants are only interesting (?) technical issues, but with less impact on the foundations.

After reviewing some of the arguments given in previous answers, I analyze and compare the two proposals by jmite for a possible definition of "*nondeterministic*" halting in the case of nondeterministic automata. The issue is not to define what halting means for a single computation, but what it should mean for the set of possible computations of a given nondeterministic automaton $A$ on a given input $x$. This can then serve as a basis for defining the halting problem on nondeterministic automata.

According to jmite's answer, this nondeterministic halting can be defined as corresponding to the existence of at least one halting computation (*existential halting*), or alternatively to requiring that all possible computation be halting (*universal halting*). These two definitions correspond to two different definitions of the nondeterministic halting problem.

I show that, for Turing machines, the two definitions corresponds to two distinct ways of determinizing the machine by dovetailing. From this, I infer that the two variants of the nondeterministic halting problem are both Turing equivalent to the classical deterministic halting problem.

However, I also show that each of these definitions of halting is directly related to a corresponding definition of the language recognized by a Turing machine, and this relation can be simply expressed on the condition of choosing consistent definitions.

Hence, given the usual definition of the language recognized by a nondeterministic automaton, the natural definition of nondeterministic halting is existential halting, as proposed in the original question.

Most of this analysis naturally extends to other types of automata, though the dovetailing constructions are often not available within less powerful families than Turing machines.

## Introduction

I am writing this as an answer since it partially answers my question after more thoughts about it, taking existing answers into account. Also, editing my question after three answers might in this case confuse issues, and I would rather leave the question as originally written to avoid that.

I first discuss some of my disagreements with the given answers. The point is not to disparage fair attempts at answering my question (my thanks for all answers), but to get to the bottom of issues by discussing or disputing technical points.

I think the original question hardly needs context or motivation. The halting problem is one of the major questions we ask about automata on the one hand, and nondeterminism is one very common and useful features of many automata on the other hand. Furthermore, nondeterminism is not just a common theoretical device to simplify proofs, but an essential feature of some families of automata, such as the linear bounded automaton (LBA), at least at the time of this writing.

Hence it is quite natural to wonder whether the halting problem has meaning, or a preferred meaning, which and why, in the case of nondeterministic automata.

## Is the nonderterministic halting problem well addressed?

My question wonders why the halting problem for nondeterministic automata seems to receive *second class* treatment, which did generate a downvote and an answer by vzn. The answer by vzn, which is really more a long comment, insists that "*nondeterminism seems a very deep/ ubiquitous/ crosscutting concept in CS*", which I never doubted. It also gives one reference to some reasearch on halting for nondeterministic machines which is not surprising, but does not really address my point. My point is that I do not recall actually seeing a definition of the halting problem aimed at nondeterministic machines, though I did read some litterature in the field. It is not addressed, AFAIK, in my reference textbook (Hopcroft+Ullman 1979). It seem often implicit in the mind of people that they are considering deterministic automata, usually Turing machines, whose reference definition is deterministic.

For example, in the question Why is the halting problem decidable for LBA?, Yuval Filmus forgot in his answer that LBAs are nondeterministic devices - but brilliantly saved his answer with a 4 words comment.

As a last witness to the fact that this issue is not well addressed in general (despite some specialized research), I would call the fact that the issue has to be discussed here.

The answer from jmite is the only one that actually attempts to explain why it might not be well addressed. His first argument is that there are two possible definitions, but I believe that this situation should rather encourage more analysis to determine which definition would be most appropriate. I attempt to do that below.

He also suggests that, since a nondeterministic TM can always be converted into an equivalent deterministic one, there is not much point in worrying about the issue of halting in the nondeterministic case. I am not fully convinced, but it may be perceived as a good reason by many. However, the argument does not apply to Linear Bounded Automata (LBA), because it is still an open problem whether deterministic LBA are equivalent to nondeterministic LBA. And there are other families of automata for which the deterministic subfamily is weaker that the whole nondeterministic family (PDA for example).

I also disagree with the last point, asserting that we should not be concerned with nondeterministic halting because proofs are easier with deterministic machines. Raphael objected to that in a comment: "*I usually find reductions to harder problems easier*". Indeed, for many types of automata, the nondeterministic version serves mainly to simplify proofs, such as reduction to that type of automaton. Having in addition two forms of halting that may be used, as suggested by jmite himself, could even be considered an advantage as it give more flexibility to address problems.

## On the definition of the nondeterministic halting problem

<sub> Note: the use of the word "universal" in the following text refers to universal quantification, NOT to universal Turing machines</sub>

The answer from jmite is the most detailed.

This answer conjectures that nondeterministic automata foster less effort on the halting problem because it can be defined in two different ways (the terminology is mine):

* **existential halting**: is there a halting computation of automaton $M$ on input $x$?
* **universal halting**: are there only halting computations of automaton $M$ on input $x$?

The only definition I had suggested adequate is *existential halting*.

**Proposition 1**: When a nondeterministic automaton is universally halting on input $x$, it can only have a finite number of halting computations on that input.

**Proof**: This is easily proved with König's lemma, since the number of possible nondeterministic choices at each step is bounded for a given automaton. If there were infinitely many halting computations, we could label each configuration with each of the computational paths leading to it, which would make a computation graph with infinitely many nodes, but only finite nondeterministic branching at each node. By König's lemma, this implies the existence of an infinite computational path, corresponding to a non-halting computation.

## The case of (nondeterministic) Turing machines

So now, let's examine halting in the case of nondeterministic Turing machine (NTM).

To analyze the two definitions, the simplest is indeed to consider deterministic versions of non deterministic machines, which can be achieved, as recalled by Hendrik Jan, by dovetailing of all possible computations.

But there are (at least) two ways of dovetailing computations for determinization, though only one is usually considered:

* **existential dovetailing determinization** which simulates all computations in parallel and terminates when one of the simulated computations terminates.
* **universal dovetailing determinization** which simulates all computations in parallel and terminates only when all of the simulated computations terminate. But it can conceivably enumerates in some way the terminating computations, or count them.

**Proposition 2**:

* A nondeterministic TM $M$ is existentially halting on input $x$ iff its existential dovetailing determinization $M\_\exists$ is a TM that halts on input $x$.
* A nondeterministic TM $M$ is universally halting on input $x$ iff its universal dovetailing determinization $M\_\forall$ is a TM that halts on input $x$.

**Proof**: The proof for the existential case is obvious. For the universal case, the universal dovetailing determinization will halt iff it simulates a finite number of computations, all of which are halting. Given a nondeterministic TM $M$, if it halts universally on input $x$, then, by proposition 1, it has only a finite number of distinct computations, which all halt. Hence its universal dovetailing determinization $M\_\forall$ halts on input $x$. The converse is straightforward.

**Theorem 3**: The halting problem for deterministic TM, and the existential and universal halting problems for nondeterministic TM are Turing equivalent.

**Proof**: This results from proposition 2 and from the fact that deterministic TMs are a subset of nondeterministic TM, where both existential and universal halting reduce to simple deterministic halting.

Hence, from a computability point of view, and I am tempted to say from a symbol pushing point of view, it seems that it does not really matter which definition is chosen, existential or universal, for the nondeterministic halting problem.

## Why choose one definition of NTM halting, and which

However, is there much sense to a determinization process that does not preserve the language recognized by the original automaton?

The essence of the use of nondeterminism in language recognition is that it assumes an oracle that is supposed to guess a right computational path whenever there is one that will lead to acceptance, *a fundamentally existential view*.

In a nondeterministic computation, there is no difference between rejection on halting and non-halting. In both cases, no conclusion can be drawn. The language recognized is not changed if you replace rejection on halting by a non-halting infinite loop, which can be done for all nondeterministic automata I can think of, including NFA (just add a looping $\epsilon$-transition on the failure states). This is also true of deterministic automata, provided there is a special symbol marking the end of the input, as usually done for LBA.

Thus acceptance by halting may be seen as a canonical form of acceptance for nondeterministic automata.

Considering this canonical view, the **halting problem** may also be expressed equivalently as the **recognition problem**:

> Is there a uniform procedure that, given a language $L$ recognized by a Turing machine $M$, can decide for any word $x$ whether $x\in L$?

This evidences the close ties between recursive enumerabiliy and the halting problem. This equivalence between deciding halting of the TM $M$ on input $x$ and containement of $x$ in the language $M$ recognizes is true for both deterministic TM and for nondeterministic ones, provided we consider the existential definition of nondeterministic halting.

However, in the case universal halting, this close relation is lost. A similar statement can be made, but for a different language than the one recognized by the NTM (or alternatively for a different, universal, definition of what is the language recognized by a NTM).

When developing a theory, it is essential to use consistent definitions so as to emphasize structures and relations in their simplest and most perspicuous form. It is quite clear that in the present case, consistency with other definitions suggests that **existential halting is the natural definition of halting for nondeterministic Turing machines.**

Of course, one may always be interested in analyzing universal halting. Similarly, one could also develop a theory of universal acceptance for NTM based on the requirement that a string $x$ is accepted iff all computation on input $x$ halt and accept. But, apparently, it is not considered a major issue in the theory of Turing machines.

## The case of other families of automata

Parts of the above analysis cannot be extended to most families of nondeterministic automata. For example a pushdown atomaton (PDA) may define languages that cannot be recognized by a deterministic PDA. The same may be true of LBAs. Other parts can be extended to all nondeterministic families.

Regarding the definition of nondeterministic halting, even though the reasoning used in the Turing machine case may not be usable, it seems that the only sensible choice is to adopt a definition which is consistent with the one used for nondeterministic Turing machines, hence the existential definition.

The definition of the Halting problem for these families of nondeterministic automata follows, and conforms the definition proposed in the question.
> 2 votes

---
Tags: turing-machines, automata, nondeterminism, halting-problem, linear-bounded-automata
---


# Question
Title: Running time function for an algorithm with while and for loop
I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, `int i=n` and `int s=0`.

Also, I know that the *while loop* is represented by $\lfloor \log\_2n \rfloor + 1$, but the *for loop* depends on the value of $i$ which decrements by half.

So, the first time the for loop performs $n$ times, the second time the for loop performs $n/2$ times, and so on. How can I represent this behavior?

I suppose that, at the end, the result is the product of both behaviors.

```
int i = n; int s = 0;
while(i > 0) {
    for(j = 1; j <= i; ++j) s++;
    i /= 2;
}

```

# Answer
> 2 votes
For each value of $i$, the inner loop runs $i$ times, and so the running time of the body of the outer loop with a given value `i` is in $\Theta(i)$. The values of `i`, as you mention, are $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \cdots, 1$, and so the overall running time is $$ \Theta(n + n/2 + n/4 + \cdots + 1) = \Theta(n). $$ Here we use the fact that the infinite series $1 + 1/2 + 1/4 + \cdots$ converges (to $2$).

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: What is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?

# Answer
It is not too hard to search for it using SageMath. The graph you are looking for seems to be the Wagner graph.

It takes a couple of minutes to run, you can check it yourself here.
> 4 votes

---
Tags: algorithms, graphs, combinatorics, spanning-trees
---


# Question
Title: Proof by induction over rules for mutually recursive relations
Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):

$\frac{a \cdot x \Downarrow e ~~ e \downarrow v}{a \cdot x \downarrow v}{\tiny PROJECT} ~~~~~~~ \frac{a \downarrow \\{ \ldots x = e \ldots \\}}{a \cdot x \Downarrow e}{\tiny{FLAT}}$

If I want to prove something about this semantics, I would naturally use induction over rules or judgements. However, when I arrive at rule *PROJECT*, I would have to make an assertion about $\Downarrow$. And to do so, I would have to return to $\downarrow$.

1. Is it legit to just merge the proofs for both relations and assume the induction hypothesis for $\Downarrow$ when dealing with $\downarrow$?
2. Is there some clean way to **not** merge the proofs but deal with them separately (something similar to break the recursion of functions)?

# Answer
Yes, it's legit; no, you'll, (usually) *have* to "merge" the proofs.

You are trying to prove some property of an *inductively* defined set. You can do so using (structural) induction along the inductive order induced by your definition.

In a nutshell, you'll assume the property for all terms up to "size" (t.b.d.) $n$ (which has to apply to all rule premises) and conclude the property for terms up to size $n+1$ (the conclusions).

In your case, coming up with a good measure of size may be the hardest part, since $a⋅x⇓e$ and $a⋅x↓v$ are of the same "size" if you count operators. What size measure will work is impossible to say without seeing the whole calculus, though. Of course, for structural induction you don't strictly need such a measure; you can just follow the inductive order (see here for examples). As long as your semantics is well-defined, that should work.
> 3 votes

---
Tags: proof-techniques, recursion, induction
---


# Question
Title: Is badly written code derogatory to the compiler?
I was having a heated debate with a friend of mine (who considers me an idiot, mind you) and we were arguing about whether a compiler has an index, or coefficient, that judges how poorly code is written. Things such as useless for loops, declared variables that aren't used, excessively verbose parameter names, and the likes. He told me that there is no such "stupid" thing. I got mad and told him that the index exists and that smart people writing compilers wanted to make the compiler have "feelings" where it would analyze the code, generate the coefficient using an algorithm, and change how well it compiles the code based of how poorly the person wrote the code.

I guess, to alleviate any confusion, what I'm asking is, do compilers have feelings? Err, well not literally, figuratively, by using an algorithm and code quality coefficient.

All answers are greatly appreciated! Thank you!

# Answer
So, something similar to what you're describing exists, but not the way exactly.

A compiler can't generally identify "bad" code. In particular, it cannot usually fix incorrect code. If you make a mistake, not only is it undecidable for the compiler to tell if you made a mistake, but there's no specification of your program for the compiler to compare to, determining if it is a mistake.

There are some general exceptions to this, the most notable one being typechecking. But there, the compiler isn't keeping any sort of coefficient, it just rejects poorly-typed code, or emits a warning.

For improve code, there is a part of the compiler called an optimizer. It will look for easy tricks that will speed up your code. Some of its tools include:

* Reordering instructions to improve speed
* Replacing a function with its definition, to reduce the overhead of calling a function (inlining)
* Evaluating expressions only involving constants
* Removing run-time safety checks when it knows they're not needed
* Storing sub-expressions that are used more than once

However, this is not at all focused on "bad" code. It is more focused on finding ways to generate fast machine code in a way that is simply not practical to do by hand. Writing code using functions is certainly not bad, but the compiler is able to make it faster in a way that a good programmer would never write.

The compiler can't do magic. If you use a slow algorithm, like BubbleSort instead of QuickSort, the compiler can't fix that for you.

There are some measures of code quality, but these are generally not included in a compiler. Rather, they are part of separate code-auditing tools.
> 7 votes

# Answer
It's generally true that compilers are designed with reasonably-written code in mind. Automatically generated code (to pick one example) often triggers pathological behaviour in immature compilers. That sort of thing makes for a great test case.

jmite is correct that compilers don't really have a notion of "bad code". A compiler is not allowed to turn legal input into incorrect output.

Apart from compiler-detectable errors (e.g. type errors), in some languages (most notably C) there is a notion of "undefined behaviour". If you write code which exhibits undefined behaviour, the compiler may be allowed to do whatever it likes, including nasal demons.

Having said that, that some code, while correct, is so "bad" that it is not worth a compiler writer's time to try to do anything useful with it. If we ignore floating point roundoff for a moment, a compiler *could* optimise this:

```
x = sin(theta)*sin(theta) + cos(theta)*cos(theta);

```

into this:

```
x = 1.0;

```

It would save a lot of time, too; transcendental functions are quite expensive as these things go. In that sense, it looks like a great optimisation.

But is it actually worth the compiler's time to look for this sort of thing? The attitude among compiler writers is that if you write this, you deserve the generated code that you get. There are far more important things that the compiler should spend its time optimising.

So badly-written source code may result in inefficient target code.
> 1 votes

# Answer
A compiler is first and foremost a translator. Therefore, if you feed bad code to a compiler, it will probably output bad code.

But a compiler does **not** have any form of code quality index that controls compilation quality. It may produce a warning that a variable is unused (helps detect bugs), and it might optimize useless loops (makes code faster), but it won't care how one names variables: A compiler is a tool, designed to help the developer, not hinder their work. With that in mind, deliberately worsen a compiler's quality seems indeed like a stupid thing to do.
> 1 votes

---
Tags: compilers
---


# Question
Title: A reference for pseudocode for Monge-Elkan algorithm?
Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm?

I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. Also, I have seen some implementations in Java (preference), but they are part of the larger package and with a complex inheritance and composition hierarchies.

I was wondering if someone can point me to a pseudocode for the algorithm, so that I could implement it myself.

# Answer
> 5 votes
Algorithm description

The input string are broken into tokens. The best matching token are compared to get the monge-elkan score.

Ex:

Input string 1: "paul johnson"

Input string 2 : "johson paule"

Score : 0.94

The algorithm uses similarity function (Example : Jaro-Winkler or Levenshtein score) as inner function. The inner function is used to compute the scores of the best matching token.

Ex: jaro\_winkler("paul","johson") = 0

jaro\_winkler("paul","paule") = 0.96

jaro\_winkler("johnson","paule") = 0.0

jaro\_winkler("johnson","johson") = 0.92

Monge\_elkan = final\_score = 1/2\*(0.92+0.96) = 0.94

```
 //Python pseudocode
cummax = 0
for ws in s.split(" "):
  maxscore=0
  for wt in t.split(" "):
    maxscore = max(maxscore,j.jaro_winkler(ws,wt))
  cummax += maxscore
score = cummax/len(s.split(" "))

```

You can check the implementation in secondstring and in sopremo . The implementation in sopremo is ported to Apache Flink as well.

# Answer
> 3 votes
There are apparently several different variants of the Monge–Elkan metric. You can check out Cohen, Ravikumar and Fienberg, A comparison of string metrics for matching names and records, which describes several different metrics (not only Monge–Elkan). Many other online references also exist.

---
Tags: algorithms, reference-request, strings, string-metrics
---


# Question
Title: Efficient algorithm for conversion of hexadecimal fraction to decimal fraction
Let's say I have some very long hex fraction like this:

```
0.3F30A21306AEFCBADE3230A593EFAEB395A39E

```

What are some algorithms with an acceptable complexity to convert it to the associated decimal string:

```
0.246835...

```

?

# Answer
> 2 votes
You can do better than quadratic in the length of the fraction, but doing so requires fast (subquadratic) multiplication algorithms such as Karatsuba or Schönhage-Strassen. First, multiply by a suitably large power of 10 to obtain an integer (note that the exponent of this power is at most linear in the length of the fraction). The problem is now to convert a hexadecimal integer to decimal.

Suppose multiplication of two $n$-bit integers takes $M(n)$ time ($O(n\log n\log \log n)$ with Schönhage-Strassen).

Conversion between (general) bases can be done using divide and conquer. Given a hexadecimal integer $k\<10^n$, recursively compute decimal representations of $\left \lfloor{\frac{k}{10^{\left \lfloor{n/2}\right \rfloor}}}\right \rfloor$ and $k\textrm{ mod }10^{\left \lfloor{n/2}\right \rfloor}$. The decimal representation of $k$ can then be found by concatenating the two recursively computed representations.

Since division and mod can both be done in $O(M(n))$ time, on an $n$-bit integer this algorithm has running time $T(n)=2T(n/2)+O(M(n))$. For Schönhage-Strassen multiplication, this evaluates to $O(n\log n\log n\log \log n)$.

---
Tags: algorithms, efficiency, number-formats, base-conversion
---


title: Removing edges of a weighted graph

text:
# Question
Title: Removing edges of a weighted graph
I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $\[0,1\]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ non relevant. What I have tried so far is removing edge values that are below median or 60% - 70% quantile. Another approach I have tried is to generate random graphs and calculate random edge similarity as $ randSim = \frac{\\#edges\\\_drawn}{\\#edges\\\_sampled}$ and remove edges with vales \<= random similarity. The issue I am facing is that the first approach is too arbitrary and very few edges are removed using the second approach. Do you have suggestions for other edge pruning approaches ?

Thank you.

# Answer
Your current approaches are very ad hoc, so they don't sound promising. Instead, I think you're going to need some domain knowledge. I suggest you start by characterizing the process by which the graph was generated. First, try to develop a probabilistic model that describes the distribution on such graphs (absent noise). Then, develop a probabilistic noise that describes the noise.

Suppose $X$ is a random variable that represents the original graph, and $Y$ is the random graph after adding noise to $X$. You observe the value of $Y$, say $y$. Now your goal is to estimate $X$. So, this becomes a probabilistic inference problem. One approach will be to use maximum likelihood methods: find the value $x$ that maximizes $p(x|y)$ (where $p(x|y) = \Pr\[X=x|Y=y\]$). To do this, you'll need to know the probability distribution $p(x)$ on $X$ and the probability distribution $p(y|x)$ on $Y$ (conditioned on $X$); then you can use Bayes rule and find the $x$ that maximizes the likelihood value $p(x|y)$ by noting that

$$\begin{align\*} p(x|y) &= p(y|x) p(x)/p(y)\\ &= {p(y|x) p(x) \over \sum\_{x'} p(y|x') p(x')}.\end{align\*}$$

Since $y$ is fixed, the denominator is a constant (it does not depend on $x$). Therefore, maximizing $p(x|y)$ is equivalent to maximizing $p(y|x) p(x)$. So, once you have a probabilistic model for $X$ and $Y$ and know the distributions $p(x)$ and $p(y|x)$, you can then try to infer the original noiseless graph by finding the value $x$ that maximizes $p(y|x) p(x)$.
> 2 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Controlling overflow and loss of precision during floating point multiplication
I have a large number of floating point numbers (~10,000 numbers) , each having 6 digits after decimal. Now, the multiplication of all these numbers would yield about 60,000 digits. But the double range is for 15 digits only. How can I get my product with minimum loss in precision?

I thought of storing the numbers as 6 digit long long integers and storing their exponents elsewhere. But this appears cumbersome and may not yield correct result. Is there an alternate easier way to do this?

# Answer
> 3 votes
Multiplication of floating point numbers is considered uncritical with respect to accuracy. If your input is only accurate to 6 digits, there is no point in computing the output to 60,000 digits. The expected relative error after 10,000 multiplications is $\sqrt{10,000}\epsilon=100\epsilon$ with $\epsilon\<10^{-14}$ for double precision. This is more than enough precision for your case.

Overflow and underflow on the other hand can indeed happen during multiplication. In practice, I would prefer to work with numbers in a range where I know that this won't happen. However, this may not always be possible. One can use frexp to split floating-point numbers into significant and exponent, multiply the significants separately and add the exponents together, and use ldexp for putting the result back together. However, doing this naively by applying frexp for every number and multiplying all 10,000 significants together at once would be a bad idea, because it would be slow and nearly guarantee underflow. But if done intelligently (appropriate grouping), it will yield the correct result, and the speed difference will be almost unnoticeable.

# Answer
> 2 votes
You can use a multi-precision software floating point package such as MPFR. MPFR will use however many bits for the mantissa as you ask it to. That said, I'm not sure why you need 60,000 digits of precision.

---
Tags: floating-point, multiplication, numerical-algorithms
---


# Question
Title: Computational complexity based in the input size
In an answer to a previous question Luke Mathieson wrote:

> A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n=O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^n)$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

Can you explain to me how if the running time is $O(m)$ goes to $O(2^n)$?

# Answer
Let the length of the input (in bits) be $n$ and let the number represented be $m$. We have $n \approx \log\_2 m$ (that's how many bits it takes to write down the number $m$) so $m\approx 2^n$.
> 3 votes

---
Tags: complexity-theory
---


title: Parse DAG into task tree

text:
# Question
Title: Parse DAG into task tree
Suppose we have a DAG of tasks:

Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).

I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:

```
Seq(
    1,
    2,
    Par(
        Seq(7, 8, 9),
        Seq(
            3,
            Par(4, 5, 6),
            10
        )
    )
)

```

Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).

More on optimality criteria: all tasks' have the same execution time `T`. Execution time of `Seq(1, 2 ... N)` equals to `N * T`. `Par(1, 2 ... N) = T`.

I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.

If we add edge from 7 to 4 (proposal from comments), then one of representations may be:

```
Seq(
    1,
    2,
    Par(
        7,
        3
    ),
    Par(
        Seq(8, 9),
        Seq(
            Par(4, 5, 6),
            10
        )
    )
)

```

# Answer
Your problem is equivalent to scheduling unit-time tasks on infintely many machines with precedence constraints (which are by necessity DAGs) minimizing the maximum completion time. In scheduling literature, this is called *project scheduling* and also denoted as $P\_{\infty} \mid \text{prec} \mid C\_{\max}$.

This problem is known to be amenable to the *critical path method* (CPM) which creates an optimal schedule in time $O(n^2)$, $n$ the number of tasks.

Given a schedule $s : \mathbb{N}^2 \to T$ that maps pairs of time slot and machine indices to tasks, you can derive a tree consistent with the precedence DAG of the form

$\qquad\displaystyle \mathrm{Seq}\bigl( \mathrm{Par}(s(1,1), \dots, s(1,i\_{1})),\ \dots,\ \mathrm{Par}(s(t,1), \dots, s(t,i\_{t}))\bigr)$;

here, $t$ is the time of the last scheduled task, and $i\_j$ is the maximum index of busy machines at time $j$. (I assume that at any given time $j$, machines $1, \dots, i\_j$ are busy and $i\_j+1, \dots$ idle.)

If that schedule is optimal, the tree is, too. It does not hold information about the original DAG, though.
> 1 votes

---
Tags: algorithms, compilers, dag
---


# Question
Title: Proof of Strong Duality Via Farkas Lemma
I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the problem:

Let A.1: Minimize $c^tX$ subject to $AX\ge b$, $X \ge 0$

Let A.2 (Dual): Maximize $Y^tb$ subject to $A^tY \le c$, $Y \ge 0$

Farkas' Lemma states: Given a matrix $D$ and a row vector $d$, either there exists a column vector $v$ such that $Dv \le 0$ and the scalar $dv$ is strictly positive, or there exists a non-negative row vector $w$ such that $wD = d$, but not both.

The strong duality theorem states: If a linear program has a finite optimal solution, then so does its dual, and the optimal values of the objective functions are equal.

Prove this using the following hint: If it is false, then there cannot be any solutions to

$$AX \ge b, \\; A^tY \le c, \\; X \ge 0,\\; Y\ge 0, \\; c^tX \le Y^tb.$$

My attempt at a solution picks up from the hint. If someone will help me complete the proof, I want it to follow my line of reasoning. I know there are many other proofs of this out there.

Let $X'$ be optimal for A.1, and let $c^tX' = \lambda$.

Assume for contradiction that the hypothesis is wrong:

$$\begin{bmatrix} A^t & -c\\ 0 & -1 \end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \le \begin{bmatrix} 0\\ 0 \end{bmatrix}, \quad \begin{bmatrix} b^t & -\lambda\end{bmatrix} \begin{bmatrix} Y\\1\end{bmatrix} \ge 0 \text{ is unsolvable.}$$

By Farkas' Lemma, we know the following system is solvable:

$$\begin{bmatrix} X & w\_2\end{bmatrix} \begin{bmatrix} A^t & -c\\0 & -1\end{bmatrix} \ge \begin{bmatrix} b^t & -\lambda\end{bmatrix}, \text{ where $X,w\_2 \ge 0$.}$$

Now, from the system above, we may write $XA^t \ge b^t$, and $Xc \le \lambda - w\_2$.

If $w\_2$ is greater than $0$, then we have found a contradiction with the assumption that $X'$ was optimal for A.1. However, one cannot reach that conclusion if $w\_2$ is exactly $0$.

I feel like I can't be that far off from a correct complete proof as I've followed exactly the hint, and the use of Farkas' Lemma which was explained on the previous page. If someone could help me finish/correct the proof, I'd be greatly appreciative.

# Answer
The following is based on the book **"Combinatorial Optimization"** by *Papadimitriou and Steiglitz* (chapter 3)

On LP duality, they first state a theorem that when a LP has a feasible solution, the dual also has one and on optimality their costs are equal (Theorem 3.1 in the book, based on the simplex algorithm)

This follows from the fact that the dual cost is always dominated by the primal cost.

i.e let $x$ and $\pi$ the solutions to the primal and dual respectively, then (i.e $c'$ is **transpose vector** of $c$)

$$c'x \ge \pi'Ax \ge \pi'b$$

So if the primal has a feasible solution so does the dual and on optimality they (the costs) are equal.

Then the Farkas Lemma (theorem 3.5 in the book) is proved based on this theorem.

But one can reverse the proof of Farkas Lemma in the book and prove Th. 3.1 from Farkas Lemma (Th. 3.5)

A sketch:

Farkas' Lemma states that (as stated in book):

> Given vectors $a\_i \in R^n$, $i = 1,..m$ and another vector $c \in R^n$,
>
> iff $y'a\_i \ge 0, \forall i \implies y'c \ge 0$, then $c \in C(a\_i)$ (i.e $c$ is in the cone generated by $a\_i$)

Consider a LP:

$$\min{c'y}$$ $$a\_i'y \ge 0, i =1..m$$ $$y \ne 0$$

The LP is feasible and bounded because $y = 0$ is a feasible point and $c'y \ge 0$ (by the lemma)

$c$ can be expressed as linear combination of the $a\_i$'s using a vector $\pi$, where $\pi\_i \ge 0$, i.e

$$c = \sum\_1^m{\pi\_i a\_i}$$

Constructing the dual of the LP as:

$$A\_j = col(a\_{ij}, i=1..m) \in R^m$$ $$a\_i = col(a\_{ij}, j=1..n) \in R^n$$

gives the dual LP:

$$\max{0}$$ $$\pi'A\_j = c\_j, j = 1..n$$ $$\pi \ge 0$$

which has a feasible solution ($\pi$) and equal cost at optimality (**strong duality theorem**)
> 1 votes

# Answer
Instead of lambda use lambda - epsilon - one ends up with the desired contradiction. Hence for any epsilon \>0 there exists a Y\_eps s.t. b^T Y\_eps \> lambda - epsilon.Taking the maximum over all Y\_epsilons, max (bT Y\_eps) \>= lambda. Hence they are equal. Is the maximum value is attained? That remains to be shown, but we can get as close as we want.
> -1 votes

---
Tags: linear-programming, linear-algebra
---


# Question
Title: Would a class in Linear Optimization/Programming be useful for a CS degree?
Would a class in Linear Optimization/Programming be useful for a CS degree?

What is it used for or how useful is it.

Can someone please help me decide. Thanks in advance

# Answer
> 0 votes
I think it depends on what do you want to do after graduating. Linear Optimization/Programming is more theoretical than practical, it will definetly be useful (take it) if you want to work as an academic/researcher but it won't be that helpful if you want to be a software developer.

---
Tags: education
---


# Question
Title: Showing that the language of graphs and nodes on an odd cycle is in NL
> Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear in that cycle is odd. Find the smallest class (NP, P or NL) that contains L.

Clearly L is in NP, I didn't manage to show that it is in P so I tried to show that it's NP-Complete, however the answer in the textbook is NL?

# Answer
> 1 votes
The question is ambiguous. Specifically, it is not clear what "different vertices that appear in that cycle" means. It can mean two things (1) the size of the set of nodes that appear in the path, or (2) the total number of nodes in that path, i.e., the length of that cycle (minus 1).

If the interpretation is (2), then the language is clearly NL: you perform a random walk (of length $\le n$), counting the number of nodes you see. If you get back to $v$ and the number of nodes is odd, you accept, otherwise you reject.

If the interpretation is (1), I don't see an immediate way to show it is in NL.

---
Tags: complexity-theory, graphs, space-complexity
---


# Question
Title: Number of operations performed in increment operators
How many operations are performed in the following in order to get a running time function of an algorithm:

1. `x = x + 1`
2. `x += 1`
3. `x++`

I know that in (1) there are 2 operations: an assignment and an addition.

Does the same criteria apply to (2) and (3)?

# Answer
> 3 votes
Depends. For the purpose of formal analysis, this is usually below our threshold of modelling. Just make a reasonable assumption, or forbid syntactic sugar in your model syntax.

Note that, if you are analysing at this level of detail, working with higher-level languages can be painful. If you want to follow Donald Knuth's lead,

1. fix a (manageable) machine model and
2. fix a low-level machine language.

The express your algorithms and this language and analyse. They may not look as nice as high-level pseudocode versions, but analysis is unambiguous.

# Answer
> 0 votes
All of these statements are equivalent, and take $O(1)$ time (I'm assuming `x` has basic type like integer or floating point). Their actual "physical" running time depends on many factors. For example, whether $x$ is stored in memory, on the stack, or in a register. Pipelining issues can also be relevant, and it is hard to predict the actual running time of any particular statement; in particular, the running times of *other* statements could be affected due to pipelining issues or even caching issues. Asymptotic analysis avoids these issues by simply stating the running time as $O(1)$.

Naturally, there are problems with asymptotic analysis: it ignores constants! There are at least two ways of dealing with that. One is to count something very specific, like comparisons in a sorting algorithm. The other is to forget about asymptotic analysis and just run simulations, empirically determining the running time (though this also suffers from similar issues, for example it could depend on what other processes are currently running on the system).

---
Tags: algorithm-analysis, runtime-analysis, compilers, code-generation
---


# Question
Title: Unable to understand a definition of an instruction in a compiler schedule
Recently I've accepted a job offer to work on compiler design. To be properly prepared I've decided to review the material. The book that is being used for that is Cooper and Torczon's *Engineering a Compiler*. That's the one we used in a class. On page 645 there is a definition of a schedule, but I can't figure out what it means

Here is the definition:

> Given a dependence graph $D$ for a code fragment, a schedule $S$ maps each node $n\in N$ to a nonnegative integer that denotes the cycle in which it should be issued, assuming that the first operation issues in cycle 1. This provides a clear and concise definition of an instruction, namely, the $i^{th}$ instruction is the set of operations $\\{n \space | \space S(n) = i\\}$

I can't understand what this is saying. Can someone phrase this in a simpler way?

# Answer
> 4 votes
I lent my copy of Cooper and Torczon to someone and never got it back, so I can't look up the context. (It's a good book in general (which is why I didn't get it back)).

The definition of *instruction* here is unusual. It corresponds more closely to what you might expect in a *Very Long Instruction Word* (VLIW) computer or in horizontal microcode.

In a VLIW machine, each *instruction* is made up of a small fixed number of independent operations. A typical example would be something like: at most one branch instruction, at most two memory operations, and at most two arithmetic operations. So you'd expect each instruction to be made up of five operations (some of which might be "no-ops"). So there are going to be two constraints here, and the definition of *instruction* given by Cooper and Torczon has not yet taken into account those constraints. (I suspect that they will start discussing the constraints in the pages just after page 645).

To be more specific: a VLIW instruction is a set of operations that can be executed simultaneously/concurrently. The operations must be (1) independent of each other and (2) the hardware must have sufficient function units to execute all the operations in the set simultaneously.

Cooper and Torczon are probably about to introduce some *list scheduling* heuristics. In list scheduling you assign a non-negative integer to each operation such that (1) the dependence dag $D$ is "satisfied" (for all directed edges $x \rightarrow y$, $S(x) \lt S(y)$). And (2) the set of operations scheduled on each cycle is feasible given the available hardware. For example, in a greedy list scheduling heuristic you would traverse the dependence DAG in some topological order placing each instruction at the earliest cycle which satisfies both conditions.

# Answer
> 1 votes
I think I understood it.

An instruction $i$ is a set of operations that can execute in cycle $i$. For example, let's say we have the following program (set of operations)

> mult
> add
> div
> sub
> load
> store

And lets say because of the dependencies mult and div can execute in cycle 1, add and sub can execute in cycle 2, load can execute in cycle 3 and store can execute in cycle 4.

Provided there is enough hardware to execute these operations we get the following:

> instruction 1: mult and div
> instruction 2: add and sub
> instruction 3: load
> instruction 4: store

---
Tags: compilers
---


# Question
Title: Determine if items can be ordered grouping two simultaneous criteria
For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together.

Obviously trying every possible ordering is out of the question.

For example, if each item has a number and a letter, the following sequence satisfies the condition:

```
A1->A2->A3->B3->B4->C4->D4
\---A----/  \-B--/  \-C--/
 1   2  \-3--/  \---4----/

```

But the following sets cannot possibly be ordered in this way:

```
A1, A2, A3, B1, C2, D3

A1, A2, B1, B2

```

I came up with a solution which is a little long to describe and seems to work, but I was curious:

Is this a known problem? Can it be reduced to a known problem?

# Answer
> 3 votes
There is a $O(n)$ time algorithm for your problem, using standard graph algorithms. You basically reduce it to connected components decomposition, which can be done in linear time.

Build an undirected (multi-)graph, where we have one vertex for each letter in the input. For each pair of items that share the same number, say Xi and Yi, add an undirected edge between X and Y. This might introduce repeated edges. That's ok. Leave them as is; don't collapse them down to a single edge.

Once you have this graph, your items can be ordered if and only if every connected component of this graph is a simple path. You can test this condition by decomposing into connected components using standard algorithms, then for each connected component, checking that no vertex has degree $\ge 3$ and that either (i) the component consists of only a single vertex, or (b) there exist exactly two vertices in the component with degree 1. The whole thing can be done in linear time.

---

The idea here is that we're trying to find an ordering of the letters (the vertices), subject to some constraints: each edge (X,Y) represents a constraint that the letter X has to be adjacent to Y in the final ordering of letters. The graph I defined above encodes exactly the constraints that apply, if we want to find an ordering of the items. Notice that there exists a valid ordering of the items if and only if there exists a valid ordering of the letters that respects the edge-constraints: given an ordering of the letters, each letter represents the group of items containing that letter, and you can easily arrange what order to put the numbers in.

The key insight here is to build a graph with one vertex per *letter* rather than one vertex per item. Once you do that, everything falls out more or less straightforwardly.

Credits: I thank Raphael for a crucial idea that helped me find this, AlexDev for pointing out some subtleties that helped me work out the details, and reinierpost, whose answer helped me realize a few other tricky details.

By the way, you might notice that my solution ends up looking very similar to reinierpost's elegant algorithm. Indeed, when the graph is connected, my solution is equivalent to his algorithm: his y\[A\] is just the degree of the vertex A in the graph I defined. The difference comes when the graph is not connected; my algorithm handles that case correctly, but I think his algorithm gets a few corner cases wrong. Nonetheless, the ideas are extremely similar -- and I hope my exposition helps understand the ideas behind his elegant algorithm.

---

This algorithm also generalizes to the case where you have more than two attributes. For instance, suppose each item has a letter, a number, and a color. Start by forming a graph with a vertex per letter and an edge (X,Y) whenever there are two items that share an attribute and whose letters are X,Y respectively; use the same techniques to look for a valid ordering of the letters. Then, for each letter, you need to look for a valid ordering of the items containing that letter. This can be done by a recursive call. There is a slight twist, in that during recursive calls you might have an additional constraint indicating which item the sequence must start and/or end at, but it's easy to adjust the algorithm to take this into account. In this way you get an algorithm whose running time is $O(kn)$, where $n$ is the number of items and $k$ the number of attributes.

---
Tags: graphs, reference-request, decision-problem
---


# Question
Title: What is the purpose of using NIL for representing null nodes?
In my *Algorithms and Data Structures* course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word `NIL` to denote for example a child of a node (in a tree) that does not exist.

Once, during a lecture, instead of saying `NIL`, my classmate said `null`, and the professor corrected him, and I don't understand why professors emphasise this word.

Is there a reason why people use the word `NIL` instead of `null`, or `none`, or any other word? Does `NIL` have some particular meaning that the others do not have? Is there some historical reason?

Note that I have seen also a few places around the web where, e.g., the word `null` was used instead of `NIL`, but usually this last one is used.

# Answer
> 32 votes
As far as I'm concerned, `null`, `nil`, `none` and `nothing` are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming languages implement this differently, and some languages might not have any such concept. In languages with pointers, it's a null pointer. In many object-oriented languages, null is not an object: calling any method on it is an error. To give a few examples:

* In Lisp, `nil` is commonly used to stand for the absence of a value. Unlike most other languages, `nil` has structure — it's a symbol whose name is `"NIL"`. It's also the empty list (because a list should be a cons cell, but sometimes there is no cons cell because the list is empty). Whether it's implemented by a null pointer under the hood, or as a symbol like any other, is implementation-dependent.
* In Pascal, `nil` is a pointer value (valid in any pointer type) that may not be dereferenced.
* In C and C++, any pointer type includes a `NULL` value which is distinct from any pointer to a valid object.
* In Smalltalk, `nil` is an object with no method defined.
* In Java and in C#, `null` is a value of any object type. Any attempt to access a field or method of `null` triggers an exception.
* In Perl, `undef` is distinct from any other scalar value and used throughout the language and library to indicate the absence of a “real” value.
* In Python, `None` is distinct from any other value and used throughout the language and library to indicate the absence of a “real” value.
* In ML (SML, OCaml), `None` is a value of the any type in the type scheme `'a option`, which contains `None` and `Some x` for any `x` of type `'a`.
* In Haskell, the similar concept uses the names `Nothing` and `Just x` for the values and `Maybe a` for the type.

In algorithm presentations, which name is used tends to stem from the background of the presenter or the language that is used in code examples.

In semantics presentations, different names may be used to refer to e.g. the `NULL` identifier which denotes a pointer constant in the language, and the $\mathsf{nil}$ value in the semantics. I don't think there's any standard naming scheme, and some presentations leave it up to a font difference, or don't go into concrete syntax at all.

It's possible that your lecturer wants to use the word `null` for a null pointer constant in the programming language used in the course (Java or C#?), and `NIL` to denote the absence of a node in some data structures, which may or may not be implemented as a null pointer constant (for example, as seen above, in Lisp, `NIL` is often not implemented as a null pointer). This distinction would be relevant when discussing implementation techniques for data structures. When discussing the data structures themselves, the null-pointer-constant concept is irrelevant, only the not-equal-to-any-other-value concept matters.

There is no standard naming scheme. Another lecturer or textbook could use different names.

# Answer
> 5 votes
I believe the reason for the use of both *nil* and *null* is that the former is primarily a noun, and the latter primarily an adjective (I checked on the web and in my paper dictionnary: American Heritage 1992).

Regarding meaning and history, NIL is a contraction from Latin "nihil" which means "nothing".

To my knowledge, the use of the name `nil` to denote a *null pointer* was introduced with the programming language Lisp (1958).

A *null pointer* is a pointer value that is supposed to point to nothing, and should thus not be dereferenced. In most cases, pointers are simply memory addresses. Any variable (i.e., any location) that is intended to contain such a pointer will always contain some configuration of bits, and any such configuration can be read as a memory address. Hence it is often the case that the value `nil` will be the address of a memory area that is forbidden to the program, thus causing some form of failure (possibly interrupt) if the program attempts to dereference `nil`, which can only be an error.

Having a unique predefined standard value to play this role is essential in languages using pointers explicitly, since it is important to be able to test whether a pointer is atually pointing to some memory location, or not. Typically, in Lisp, a list was built as a succession of "cons" pairs containing a "car" pointer to a list element and a "cdr" pointer to the next pair. In the last pair of the list, the second pointer was `nil`.

This corresponds to the recursive definition of a list as either an empty list, or a list element concatenated to a list. Hence a list with no element was represented by `nil`. This empty list happens to be the identity of the list monoid.

Since lists can be used to represent sets, the empty set can in that case also be represented by `nil`.

**Thus `nil` was historically a special pointer value, but came to be understood as a special identity value for other more abstract domains, such as lists or sets.**

A pointer equal to `nil` was a null pointer, null being a adjective rather than a substantive (i.e. a noun).

The coordinated use of both word, as adjective and noun is quite consistent with other practice. The qualifier *null* is often used for the zero of an algebraic structure, such as the identity of a monoid: the *null element*. Lists form a monoid, where the value nil is the identity. The same is true of sets (though they form an algebra with many more properties). One says similarly that an integer is *null* when it is zero.

There are lots of variations on the use of these words an others, such as none, depending on authors and idiosyncrasies of programming languages.

**The two major connotations are**, as explained above

* **as a standard "undefined value", actually representing the absence of any usable value.**
* **as identity value of some domain**

This shows that it is not quite accurate to assert that NIL is "*a value which represents the “absence of a value*", as done by Gilles in the accepted answer. It depends on the language and its uses. The programming language LISP probably introduced NIL in the programming terminology 55 years ago. **In LISP, `NIL` is the empty list, and can equivalently be noted `()` which is the natural representation of the empty list.** It does not represent the absence of a value. It is sometimes used as place-holder for missing values, though that is often to be avoided precisely because the empty list is a value. What stands for a missing value in a structure in any arbitrary object, chosen by the programmer, that cannot be confused with acceptable values.

The two concepts are rather different, even though we have shown above that they can be related. It might be interesting to have a mode detailed taxonomie of the use of the terminology enumerated by Gilles'answer, to see whether the uses of each of these words are oriented more towards one connotation or the other.

Names are no more than what they are assigned to mean in a given context, by whoever is defining the discourse. Some uses are more common, more natural, or more consistent, but one should always check for definitions and make sure what meaning was intended in each context. And one should not always expect terminology to have been chosen with taste or consistency.

# Answer
> 1 votes
NIL is an object with a value that tells the programmer the object is not valid. It's particularly useful in C++ where NULL is defined as 0. If you de-reference NULL in C++, you get undefined behavior. If you de-reference NIL (a pointer to an empty object that you defined), you get an object that you can tell is beyond the end of your data structure. It's great for preventing catastrophic program failures and detecting errors.

You can use NIL in cases like doubly-linked lists, having it be the beginning and end of the list to keep track of both the head and tail, and make sure that -\>next and -\>prev pointers never de-reference NULL.

---
Tags: algorithms, terminology, data-structures, notation
---


# Question
Title: What are transitive successor and transitive predecessor in the graph?
I'm reading a book on compilers, *Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon* and I came a across two new terms that I can't understand, they are:

> transitive successor and transitive predecessor of a node $i$

I tried to find definitions of those online, but I'm having hard time with it. Everything I find talks about transitive reduction.

Can someone give a clear definition of this? Any help is appreciated.

# Answer
> 1 votes
If you ask Google with "transitive successor" (including the double quotes) you get several book references, and access to some pages (which I cannot read right now, because of a local problem). Considering that *successor* is a relation between the nodes of the directed graph, "transitive successor" should naturally be its transitive closure. One book is apparently using the term "direct successor" to be precise and avoid confusion with "transitive successor" which could occur when using "successor" alone.

# Answer
> 1 votes
Unfortunately I don't own your book, but I can conjecture what these terms mean.

In words, a *transitive successor* of $i$ is a successor of $i$, or a successor of a successor of $i$, or a successor of a successor of a successor of $i$, or ...

Here is a formal definition. We define an $n$-fold successor inductively:

1. $i$ is the only $0$-fold successor of itself.
2. $j$ is an $(n+1)$-fold successor of $i$ if $j$ is the $n$-fold successor of some successor $k$ of $i$.

For example, $j$ is a $1$-fold successor of $i$ iff it is a successor of $i$, and $j$ is a $2$-fold successor of $i$ if for some $k$, $j$ is a successor of $k$ and $k$ is a successor of $i$.

A *transitive successor* of $i$ is an $n$-fold successor of $i$ for some $n \geq 1$ (or perhaps $n \geq 0$, depending on your definition).

We can give an alternative definition using the language of directed graphs. Draw a graph in which there is an edge from $i$ to $j$ iff $j$ is a successor of $i$. A transitive successor of $i$ is then any vertex reachable from $i$, that is, any vertex $j$ such that there is some directed path from $i$ to $j$.

---
Tags: graphs, compilers
---


# Question
Title: Best introductory "algorithms"/"more than just coding" comp sci book?
I've been programming in languages (C/C++/Ruby/Java/HTML) for some time now and am currently entering my senior year of high school. I'm taking AP Comp Sci, which uses Java, but want to have a better grasp of some of the more "math-y" concepts in computer science, like hashes/algorithms/etc. For someone who has done basic object oriented programming but doesn't know any of the algorithmic aspects of computer science (And wants to know them before he goes off to college), what books would you recommend that cover algorithms and the more mathematical stuff in a way that's easy for your rudimentary programmer to understand?

Some examples I've heard given are "Introduction to Algorithms" and "Structure and Interpretation of Computer Programs"; I was going to go with **Introduction to Algorithms** but it's around 80 dollars new, and I'm not sure if **SICP** has any of the algorithmic math I want to pursue. Haha, I guess all I'm asking for is personal opinions from people that have studied algorithm books and can give honest personal opinions.

Any and all feedback is appreciated; Thank you!

-Neil

# Answer
> -1 votes
Check out *From Mathematics to General Programming* by Alexander Stepanov and Daniel E. Rose.

Beginning with the basics of number theory you progress up to dealing with content that is typically covered in a 3/400 level abstract algebra course (depending on the institution).

---
Tags: algorithms, books
---


# Question
Title: Is my understanding of what an algorithm is correct?
1. My definition of an algorithm is a finite sequence of operations provided by an abstract machine, where the operations are executed one after another in the order specified by the sequence.
2. Different machines may provide different sets of operations, so the definition of an algorithm depends on the abstract machine and can be different on different abstract machines.

Thanks.

# Answer
While very vague, I don't see anything inherently wrong with your "definition", nor do I know strictly better ones.

See also here.
> 1 votes

# Answer
One of my professors gave us this definition of algorithms when he was about to introduce Turing Machines:

> An algorithm is a finite sequence of instructions which always terminates and gives us a result.

Therefore an algorithm requires termination as well as the production of a result, otherwise it is nothing more than a procedure which is a sequence of operations/instructions.

A procedure may be effectively calculable by pen/paper method, but an algorithm is effectively computable by a Turing machine.
> 1 votes

---
Tags: algorithms, terminology
---