# Question
Title: Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes
I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph partitioning problems are considered NP-hard or even NP-complete, but considering the unique constraints of the input graph, I am hoping that there is an efficient solution.

**Note**: This problem is different than the disjoint-vertex paths problem since each node must be included in one of the paths, whereas the disjoint-vertex problem does not consider this. However, if you think that it could be modified as a better approach than the one I describe, please let me know!

# Input Graph Description

* Given a size $n$ (which will actually range from 5-14), the graph will contain $n^{2}$ nodes arranged in a square matrix format
* Of the $n^{2}$ nodes, there will be $k$ pairs of marked nodes such that there must always exist a path between each pair. $k$ is generally about the same size as $n$, usually within a range of $n \pm 2$ (for smaller $n$, $k$ is usually smaller than $n$ since too many pairs will make the problem unsolvable)
* A given node has at most 4 edges that go up, down, left, or right
* Each node that is directly "adjacent" to another node in one of the 4 previously mentioned directions will have an edge connecting to that node (with the exception of the specially marked nodes, they do not connect to other specially marked nodes from other pairs)

Here is a pictoral example of a simple input:

In this example, $n = 5$ and $k = 4$. Notice that on the top row of nodes, the "adjacent" A and B nodes are not really adjacent (they have no connecting edge). This is what I was trying to explain in my 4th point. Also notice the "marked" nodes I was referring to are circles and are labeled with letters, marking them.

# Problem/Output Graph Description

* Partition the graph into $k$ subgraphs
* Each subgraph is a path connecting one of the $k$ pairs, making them "endpoints"
* The unlabeled nodes form the intermediary part of the subgraphs/paths
* Since each subgraph is actually a path, the marked nodes will ultimately have degrees of 1, and the unmarked nodes will have degrees of 2.
* Every unmarked node must be used in one of the subgraphs (I originally tried to formulate the problem as a vertex-disjoint paths problem, but I felt that this didn't address the problem of including all the original vertices)

Here is a pictoral representation of the solution to the example input:

# My Approach

Ultimately, I am using backtrack to find the solution. However, instead of plain backtrack search, I reduce the input graph based on some rules I came up with:

### Rules

* If a marked node has only 1 edge, then the node it is adjacent to is "owned" by that marked pair.
* If an unmarked node is owned by one of the $k$ pairs and has more than 2 edges, then 1 or 2 of those edges are pointing to marked nodes of a different pair. These edges are thus removed.
* If an unmarked node is owned by one of the $k$ pairs and has exactly 2 edges, the edge that connects an unowned/unmarked node is now owned by the current pair.
* If there are any unmarked nodes owned by some pair $i$ that are adjacent to unmarked nodes owned by some pair $j$ (where $i \neq j$), then the edges connecting these nodes are removed.
* If an unmarked node owned by some pair $i$ is adjacent to one of the marked nodes in pair $i$ and the degree of that marked node is greater than 1, the edges of the marked node are removed except for the one connecting to the owned unmarked node.

For inputs where $n \< 10$ and where $k$ is small enough (wrt to $n$) such that the marked nodes are not too sparse, the rules reduce the input into the solution, obviating the need for backtrack search. However, with larger/more sparse inputs, the rules barely seem to reduce the initial state, and then backtrack becomes necessary. Unfortunately, the search space seems to be too large to efficiently solve the problem.

# Main Question

Given the constraints of the input graph, is it possible to add to/revise these rules to be able to solve the problem without resorting to a state space search? Or, is it at least possible to add to/revise the rules in order to improve the problem reduction for larger problem inputs?

If it is indeed the case that there is not much else to do in terms of problem reduction via rules, am I better off implementing a heuristic search (like best-first search) to solve this problem? And if so, does anyone have suggestions for formulating such a heuristic? Thanks!

# UPDATE

So I attempted to use best-first search with a few different evaluation functions. I tried to use an A\* type approach ($f(n) = g(n) + h(n)$) but this did not work very well, mainly because I could not find a good function to satisfy $h(n) \leq cost(n, goal)$. Instead I used the number of newly "owned" nodes that the state had after applying the aforementioned rules and subtracting the level of the state in the tree (ultimately, this was a function I wanted to maximize instead of minimize). This worked extremely well for many inputs that were not solved completely by the rules, but still larger inputs are not efficiently found.

I am trying to now find some kind of evaluation function that can measure the potential of a certain state to become more "reduced" by these rules, which will guide search towards the states whose descendants will more likely be the goal state.

In addition, I figured out another invariant property about the goal states: using the definition I gave, the goal state must have exactly $n^{2} - k$ edges (and as mentioned before, "labeled" nodes have degree of 1 and unlabeled degree of 2). Also, if the start state is redefined to include edges between all directly adjacent nodes (so including an edge between A and B nodes for example), then a start state always begins with exactly $2n(n-1)$ edges. With both of these in mind, the solution to each problem must result by removing exactly $n^{2} - 2n + k$ edges from the graph.

Given these extra properties, is there a way to determine a specific set of moves to solve the problem, or at least some kind of evaluation function that will help guide a search towards "better" states?

# Answer
> 1 votes
As it turns out, this puzzle was solved in a competition at Oxford University in 2012. The winning implementation used backtrack search with several heuristics and pruning, and it can solve instances of the puzzle much larger than the maximum 14x14 in milliseconds. Apparently, the problem I was trying to solve is equivalent to another game called Numberlink. For anyone else interested, here is the GitHub page for the implementation, which further explains the heuristics used to solve the problem.

In case the link breaks, I will post a quote from the readme:

> Numberlink solves puzzles using a heavily pruned backtracking search. In particular the following pruning heuristics are used:
>
> Partial links
>
> A dual representation based on link corners
>
> Optimistic validation
>
> There are multiple ways to do backtracking on numberlink puzzles. The most obvious is to start at a source, choose a link to its other end and recurse. Alternatively one can start at all sources at the same time, or you can ignore the sources and systematically fill out the squares on the paper in some order.
>
> Numberlink uses the later approach: It fills out the paper starting in the upper left corner and continuing along the SW-diagonals. For a 4x4 paper the order in which squares are visited is (in base 16):
>
> 0136
>
> 247a
>
> 58bd
>
> 9cef
>
> Backtracking in this systematic give us a lot of advantages compared to starting at the sources:
>
> We never get unconnected squares. We simply always connect a square as we go over it. We never block a source from its other end. To see this notice that blocking a source requires us to have passed it. In passing it we must have connected it to a partial link. The other end of this partial link can not be connected to any other sources or to the side, so it must be in the 'active diagonal'. We always know exactly what squares around us have already been connected. That's the one above us and the one to the left. The directions we need to care about is down and right.

---
Tags: algorithms, graphs, search-problem, partitions, planar-graphs
---


# Question
Title: Language to Construct Finite State Transducer
I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing.

You typically construct finite automata using regular expressions, for example (a | b).

What language does one typically use to construct Finite State Transducers?

You can't use Regular Expressions alone, because that defines only the input string, but I need some method to map corresponding output symbol. I have thought about having something like this ((a,x) | (b, y)), where the tuple (a,x) is composed of the component a input value, and the component x is the corresponding output value. Would that work in general for constructing FST?

# Answer
> 4 votes
Yes, such a specification would work. Basically a FST is a finite state automaton, with different labels on the edges. We can go from FST to regex by a standard algorithm. The same method works with transducers, only the labels are now pairs of strings. The concatenation of labels is done component-wise: $(a,x)(b,y) = (ab,xy)$.

There are several types of FST. To obtain a general one both input and output component are strings, not just letters. It is not difficult to see that alternatively one might require that both input and output are either a letter or the empty string.

All said, I personally prefer as a "language" the finite state graphs: they are easy to "program".

# Answer
> 1 votes
FSM Transducers are like DFAs with output states associated with input states. so transitions can be labeled as symbol pairs (*x*, *y*). see this page, Transducer section in the AT&T FSM library for one (simple) standard file format.

# Answer
> 1 votes
The direct product characterization described above is equivalent to the following which gives you the answer you're looking for: simply continue using regular expressions but subject them to commutativity xy = yx for all x in the input alphabet X and y in the output alphabet Y. The resulting algebra comprises the Kleene algebra of rational subsets of the monoid X^\* x Y^\* formed as the direct product of the two free monoids X^\* and Y^\*.

The transposition xy = yx may be viewed as the algebraic form of the "look ahead" operation.

Denoting the Kleene algebra comprising the rational subsets of a monoid M by RM; the factor algebras R X^\* and R Y^\* embed into R( X^\* x Y^\* ) as w in X^\* |-\> (w, 1) and v in Y^\* |-\> (1, v). So the general rank 1 term (w, v) may be written as either (w,1)(1,v) (which corresponds to taking the product in the order wv) or as (1,v)(w,1) (which corresponds to taking the product in the order vw). So you can simply do away with the construction-by-ordered pairs and write them as mentioned above: as regular expressions with the commutativity condition imposed on the underlying algebra.

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Is there a way to test "Turing completeness"?
I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too.

Is there a minimal test that could determine whether a language or instruction set is Turing compete, or does a test of that sort fall into the domain of undecidability?

It might seem like a trivial or stupid question, but the reason I ask is that it would be a good way to test whether the instructions of a cellular automaton is Turing complete, and if there is such a test, maybe it could help when generating cellular automata.

I'm quite new to both cellular automata and undecidability problems, so go easy on me.

# Answer
I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down to Turing Completeness, but I don't know if any actually exist.

But a general algorithm "look at an arbitrary systems and tell if it's Turing Complete" can't exist. Otherwise we could do this:

```
RunTuringMachine = lambda (M1) . lambda (x). lambda (M2) .
  run M1 on x and discard the result
  run M2 //we only get to this line if M1 halts on x

```

Then, for any inputs M1, x, `RunTuringMachine M1 x` is a Turing-complete system if and only if `M1` halts on input `x`, and we've solved the halting problem.

We could also prove this by Rice's theorem: if we can decide if any system is Turing Complete, then we can decide of a Turing Machine is a Universal Turing Machine, which is impossible by Rice's Theorem.
> 13 votes

# Answer
Is there an **automatic** test for Turing Completeness? I'm not sure. I'm going to guess not since it feels like an analog of the halting problem.

Is there a way for **humans** to tell if a system is Turing Complete? Yes.

It all boils down to the Church-Turing thesis. The TLDR version is that two systems can solve the same set of problems if they can run emulators of each other.

So one way to prove that a system is Turing complete is to emulate a universal Turing machine. The game of life for example was proven to be Turing complete by emulating a universal Turing machine.

> Side note: An actual Turing machine has infinite tape length. Therefore no physical system is technically Turing complete (at minimum the universe has a maximum number of electrons). The usual caveat goes something like: this CPU/programming language is Turing complete if we assume infinite memory.
> 4 votes

---
Tags: computability, computation-models, turing-completeness
---


# Question
Title: Must a recursion be represented only in terms of definition of a recursive function?
In programming languages, must a recursion be represented only in terms of definition of a recursive function?

Does a recursion appear in other cases?

I ask this question, because recursion and loop are two equivalent ways to make a programming language Turing complete. Loop doesn't depend on function, and does recursion also not?

Thanks.

# Answer
> 2 votes
Let's look at the definition of recursion:

> Recursion occurs when a thing is defined in terms of itself or of its type.

This means you need some sort of object (not in the OOP sense), which can be defined in terms of other objects of the same kind.

A function is usually defined as a list of statements in imperative languages or as an expression in functional languages. Statements and expressions can contain function calls, which means a function can be recursive:

```
void f()
{
    f();
}

```

```
let f () = f ()

```

But there are other objects that can (at least potentially) be recursive.

Structures are types that contain fields, of other types:

```
struct S
{
    S* s;
};

```

Classes inherit from other classes, but a class inheriting from itself doesn't make much sense, so it's not allowed in the languages I know:

```
class C : C
{
};

```

(There is a related concept of the curiously recurring template pattern, but that's not really recursion.)

It could also make sense to define a value in terms of itself (for example, when creating a single-value cyclic linked list):

```
var item = new Item { Next = item };

```

Though most languages won't allow this and require you to construct such value in two steps:

```
var item = new Item();
item.Next = item;

```

---

But, for something to be Turing-complete, it has to define a *computation*. These other examples don't do that. Though if you look at more exotic languages, you can find that too.

For example, predicate in Prolog can be defined using other predicates:

```
p :- p.

```

Predicates are in some aspects similar to functions, but they're not really the same.

# Answer
> 2 votes
Recursion appears in programming languages in many forms. The purest form is a fixed-point operator $\mathtt{fix}$ which takes a function $f$ and computes its fixed point: $$\mathtt{fix}(f) = f(\mathtt{fix}(f))$$ In a lazy functional programming language you can define $\mathtt{fix}$ exactly as above, e.g., in Haskell:

```
Prelude> let fix f = f (fix f)
Prelude> :t fix
fix :: (t -> t) -> t

```

Then `fix` can be used for many purposes. Let us look at some examples. First, if we have a recursively defined function $$g(x) = \Phi(g, x)$$ where $\Phi$ is the body of $g$, we can get $g$ defined non-recursively as $$g = \mathtt{fix}(\lambda h \\, x \\,.\\, \Phi(h, x))$$ For instance, in Haskell we can use fix to define the factorial function:

```
Prelude> let fact = fix (\ h x -> if x == 0 then 1 else x * h (x - 1))
Prelude> fact 10
3628800

```

But we can also define other recursive structures. For instance, suppose we want a list $\ell$ such that $$\ell = 1 : 2 : 3 : \ell$$ Then $\ell = \mathtt{fix}(\lambda x \\,.\\, 1 : 2 : 3 : x)$. Indeed:

```
Prelude> fix (\ x -> 1 : 2 : 3 : x)
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1 ....

```

Of course, we do not have to use `fix`, that's just an interesting theoretical gadget. Haskell allows recursive definitions of non-functions:

```
Prelude> let myList = 1 : 2 : 3 : myList
Prelude> myList
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2, ...

```

A less silly example is the list of prime numbers, defined recursively as:

* the first element is $2$
* the rest of the list consists of those numbers $n \geq 3$ which are not divisible by any number $k$ in the list of primes such that $k^2 \leq n$

Let us try:

```
let primes = 2 : [ n | n <- [3..50], all (\k -> n `mod` k /= 0) (takeWhile (\x -> x * x <= n) primes)]
Prelude> primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,11

```

Does this mean we can also define a number $n$ such that $n = n + 1$? Absolutely:

```
Prelude> let n = n + 1
Prelude> n

```

Haskell goes into an infinite loop, of course. The "number" so defined is the "undefined number".

There is also recursion at the level of types. It happens whenever we have a definition of a type which refers to the type itself. Examples are lists, trees, classes in objective-oriented programming, etc. Here too we have a fixed-point operator, except that this times it works at the level of types: given a *type constructor $F$* (a function from types to types), $\mathtt{Fix}(F)$ is a type $T$ such that $T \cong F(T)$. For example, if $$T(X) = \mathtt{unit} + \mathtt{int} \times X$$ then $\mathtt{Fix}(T)$ is the type of lists of integers. (I am skipping details on *which* fixed point is computed by $\mathtt{fix}$ and $\mathtt{Fix}$.)

# Answer
> 1 votes
It is possible to name examples of recursion used to define computations in Turing-complete models that are not based on functions. Unrestricted grammars is one of them.

What you end up creating can always be *interpreted* as a function, nonetheless.

---
Tags: programming-languages
---


# Question
Title: Adding Big-O and little-o notation to get a little-o
Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $A$ to completely sorted in $O(n\log (n/k))$. $n$ is the size of the array, while $k$ is another non-constant parameter given. I want to get a contradiction. Here is my reasoning:

Running the first algorithm followed by the second completely sorts the array, and takes

$$o(n\log k)\ +\ O(n\log(n/k)) = o(n\log k\ +\ n\log(n/k)) =$$ $$o(n(\log k\ +\ \log(n/k))) = o(n\log (k \times n/k)) = o(n\log n)$$

which is a contradiction to the known lower bound to comparison-based sorting algorithms.

My question is: Is my reasoning correct? Why or why not? I've tried to prove it using the definitions, but I'm stuck.

Thanks.

# Answer
> 2 votes
No. You are misusing Landau notation.

1. $o(f) + O(g) \not\subseteq o(f + g)$ even if $f \in O(g)$. The best you can get is $O(f + g)$. If $g \in o(f)$, you get $o(f)$.
2. $\log k$ and $\log n$ are incomparable as long as you can not put $k$ and $n$ in some kind of relation.

Assuming that $k \in \omega(1) \cap O(n)$, you *can* show that both $o(n \log k) \subseteq o(n \log n)$ *and* $O(n \log (n/k)) \subseteq o(n \log n)$. Then, we would indeed deduce that the proposed algorithm would take $o(n \log n)$ comparisons, contradicting the known lower bound.

---
Tags: proof-techniques, landau-notation, lower-bounds
---


# Question
Title: It has been asked to prove that a grammar is unambiguous which seem ambiguous to me
> S-\>aAB
>
> A-\>bBb
>
> B-\>A|epsilon

It seems that the string `abbbb` can be derived by using more than one ways. After using the starting production and the production for A, we get: `S=>abBbB`.

From here, either of the B's can be replaced with epsilon and the other one replaced with bBb. So, there are two ways of deriving `abbbb`.

Isn't this ambiguous grammar?

It's a question from Formal Languages and Automata by Peter Linz (5th edition) Exercise 5.2.16

# Answer
> 2 votes
You need to revisit the definition of ambiguity. The point is not whether multiple derivations exist; all non-linear grammars have many derivations per word. You have to check if there is only one left-derivation per word. Equivalently, you can check right-derivations or syntax trees.

If you think this grammar is ambiguous, prove it by giving two different syntax trees for some word.

If you think it is unambiguous, see here for how to prove that; it's often more tricky.

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


# Question
Title: Is it possible to have multiple languages accepted by a DFA?
Is it possible to have multiple languages in a DFA? in my example in the image, I think the language L={w | w = 0x where x is {0}\* } is accepted and the language L={w | w = 0x11 where x is {0}\* } could be accepted as well.

# Answer
> 2 votes
Revisit the definition of the language a finite automaton *accepts*: it is the set of exactly the words the automaton has an accepting computation for. *All* these words, but *no others*. This set is always unique.

Here, the accepted language does indeed have *sub*sets

* $\\{ 00x \mid x \in \\{0\\}^\* \\}$ and
* $\\{ 0x11 \mid x \in \\{0\\}^\* \\}$.

You will have to check if that are really *all* accepted words. This may be simpler to do after minimizing the automaton.

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


# Question
Title: Prove that the set of recursive languages is infinite
I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ?

Edit : The above question has small mistake as pointed out in one of the comments .. Since every recursive language has infinitely many deciders .. the two questions are indeed not equivalent . For people who are wondering why there are infintely many deciders , take a decider D and keep on adding some useless states, transitions, tape symbols so that you get new decider with a larger description than D and since you can continue this process indefinitely , there exists infinitely many deciders for a recursive language.

# Answer
> 3 votes
* The language `{0}`.
* The language `{00}`.
* The language `{000}`.
* The language `{0000}`.
* The language `{00000}`.
* The language `{000000}`.
* The language `{0000000}`.
* The language `{00000000}`.
* The language `{000000000}`.
* The language `{0000000000}`.
* The language `{00000000000}`.
* The language `{000000000000}`.
* The language `{0000000000000}`.
* The language `{00000000000000}`.
* The language `{000000000000000}`.
* The language `{0000000000000000}`.
* The language `{00000000000000000}`.
* The language `{000000000000000000}`.
* The language `{0000000000000000000}`.
* The language `{00000000000000000000}`.
* The language `{000000000000000000000}`.
* The language `{0000000000000000000000}`.
* The language `{00000000000000000000000}`.
* The language `{000000000000000000000000}`.
* The language `{0000000000000000000000000}`.
* The language `{00000000000000000000000000}`.
* The language `{000000000000000000000000000}`.
* The language `{0000000000000000000000000000}`.
* The language `{00000000000000000000000000000}`.
* The language `{000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* The language `{0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}`.
* Which leads to the idea that we should consider the infinitely many languages of the form $\\{0^n\\}$ where $n \in \mathbb{N}$.

# Answer
> 2 votes
What we want to prove is that there are infinitely many recursive languages. Consider the languages ( over $\\{0,1\\}$ ) $L\_i=\\{w\\;|\text{ if } w \text{ has } i \text{ ones } \\}$. Now each of the languages $L\_i$ for $i \ge 0$ is decidable. And the set containing languages $L\_i$'s is infinite ( though countable ). As the set of recursive languages contains all $L\_i$, it is also infinite.

---
Tags: computability, turing-machines, combinatorics
---


title: How can you prove 3^n is not O(n^2)?

text:
# Question
Title: How can you prove 3^n is not O(n^2)?
I can obviously tell by inspection that it is not true but I cannot figure out how to prove it with witnesses (C and k). Thanks!

# Answer
> -1 votes
Let's assume that $3^n = O(n^2)$.

This would by definition mean that there are real positive numbers $a$ and $b$ such that for any sufficiently large $n$ (or to say as $lim\_{n \to +\infty}$):

$ an^2 \leq 3^n \leq bn^2 $

Dividing everything by $3^n$ we get:

$ a\frac{n^2}{3^n} \leq 1 \leq b\frac{n^2}{3^n}$

And since if we let $lim\_{n \to +\infty}$ we get a contradiction:

$ 0 \leq 1 \leq 0 $

Hence inital statement is false and $ 3^n \neq O(n^2) $

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Is the halting problem decidable for pure programs on an ideal computer?
It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems that a pure program's halting on an ideal computer would be decidable through e.g. static analysis.

Is this in fact the case? If not, what are some counterexamples or papers disproving this claim?

# Answer
Here is a proof of undecidability by reduction from the Halting problem.

**Reduction:** Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ and $x$ on the tape and simulates $M$ on $x$ until $M$ halts.

The behaviour of this new machine $H$ is independent of the input tape, so it is a *pure* Turing Machine on which only static analysis is applicable. If static analysis were sufficient, then it could show whether $H$ halts, which would show whether $M$ halts on $x$, which would solve the halting problem for impure machines, which we know is undecidable, and therefore your problem is undecidable too.
> 38 votes

# Answer
No it is not, and moreover it does not depend on I/O.

Simple counterexample: write a program to find a perfect odd number (this is an open problem: we do not know yet whether one exists) - it does not take any input and does not perform any *impure* tasks; it may halt when it finds one, or may work infinitely (in the case such a number does not exist). Now if static analysis was powerful enough to determine the halting case it would be used to answer this (and many more questions) where halting would mean positive existence of such a number and not halting would mean there is no such number, but unfortunately static analysis is not that powerful.
> 16 votes

# Answer
The classical proof by diagonalization **is a pure machine**, not only it is a pure Turing Machine, but **it does not rely on "Open Problems".**

In example, a Turing machine that executes the Collatz Conjecture has unkown halting status, but that relies on our ignorance about the Collatz Conjecture, one day we might proove that Collatz was right and then we would became able to decide the Halting status of the conjecture (Either for some inputs does not halt, or Always halts).

So the Collatz Conjecture could already answer your question (Temporarily at least), but **it relies on something we don't know**. Instead the classical proof is a solved problem: **we already know that's undecideable**.
> 2 votes

# Answer
Just for the record, the standard proof of the undecideability of the halting problem relies on the same idea as quines: that it's possible to write a program some sub-term of which evaluates to the source code for the whole program. Then, if there was a function `halts` that, given source code for a program, returned True if that program halted on all input and False otherwise, this would be a legal program:

```
prog() = if halts "prog" then prog() else ()

```

where `"prog"` would be some expression that evaluated to the source code for `prog`; however, you can quickly see that `prog` halts (for all inputs) iff it doesn't halt, which is a contradiction. Nothing in this proof relies on I/O in any way (do you need I/O to write a quine?).

By the way, you might want to look in to "dialog-based I/O" for further evidence that I/O is entirely irrelevant to your problem (basically, programs that do I/O can be reduced to programs that take input as (explicit) functional arguments and return output as (explicit) additional results in a lazy language). Unfortunately, I can't find a reasonable, un-biased (or pro-dialog) page on the web right now.
> 0 votes

---
Tags: halting-problem, static-analysis
---


# Question
Title: What are common formal techniques for proving functional code correct?
I want to provide proofs for parts of a Haskell program I'm writing as part of my thesis. So far however, I failed to find a good reference work.

*Graham Hutton's* introductory book *Programming in Haskell* (Google Books)—which I read while learning Haskell—touches on a few techniques for reasoning about programs such as

* equational reasoning
* using non-overlapping patterns
* list induction

in chapter 13 but it's not very in-depth.

Are there any books or article you can recommend which provide a more detailed overview of formal proving techniques for Haskell, or other functional, code?

# Answer
One of the de facto methods for proving results in functional programming is via Richard Bird's group.

In particular, you ask for an in-depth or at least more comprehensive approach to equational reasoning and list induction and this is provided in Lectures on Constructive Functional Programming.

More generally, the text "Algebra of Programming", by Bird and de Moor, also deals with the correctness of functional algorithms such as optimisation and dynamic programming problems.

---

If you come across other useful resources for this problem, please mention them and perhaps we can turn this post into a wiki.
> 5 votes

# Answer
You can start with

> Topics include basic concepts of logic, computer-assisted theorem proving, the Coq proof assistant, functional programming, operational semantics, Hoare logic, and static type systems. The exposition is intended for a broad range of readers, from advanced undergraduates to PhD students and researchers. No specific background in logic or programming languages is assumed, though a degree of mathematical maturity will be helpful.

You can skip (or skim) the programming language theory parts and only learn how to deal with formal proofs starting from Preface up to IndPrinciples. The book is really well-written and illuminating.

Then you might want to proceed with

> In this volume you will learn how to specify and verify (prove the correctness of) sorting algorithms, binary search trees, balanced binary search trees, and priority queues. Before using this book, you should have some understanding of these algorithms and data structures, available in any standard undergraduate algorithms textbook. You should understand all the material in Software Foundations Volume 1 (Logic Foundations)

A note of warning: VFA is still in beta-release!
> 6 votes

# Answer
It turns out that an excellent source of proof techniques and examples for proving things about pure functional languages is proof assistants which usually include *as part of their specification language* a pure functional language on which it is possible to reason equationally.

One might want to consult a book like Certified Programing with Dependent Types for an in-depth introduction to this kind of reasoning in a specific proof assistant, namely Coq.
> 5 votes

# Answer
I suggest to use program logics. They deal much better with effects than typing systems.

There are numerous program logics for functional languages. This becomes interesting with effects. See e.g. Logical Reasoning for Higher-Order Functions with Local State.

Work by Arthur Charguéraud integrates the program logic approach with proof assistants, see e.g. this overview page.
> 4 votes

---
Tags: reference-request, proof-techniques, functional-programming, books, software-verification
---


title: How to make a language homoiconic

text:
# Question
Title: How to make a language homoiconic
According to this article the following line of Lisp code prints "Hello world" to standard output.

```
(format t "hello, world")

```

Lisp, which is a homoiconic language, can treat code as data in this way:

> Now imagine that we wrote the following macro:
>
> `(defmacro backwards (expr) (reverse expr))`
>
> backwards is the name of the macro, which takes an expression (represented as a list), and reverses it. Here’s "Hello, world" again, this time using the macro:
>
> `(backwards ("hello, world" t format))`
>
> When the Lisp compiler sees that line of code, it looks at the first atom in the list (`backwards`), and notices that it names a macro. It passes the unevaluated list `("hello, world" t format)` to the macro, which rearranges the list to `(format t "hello, world")`. The resulting list replaces the macro expression, and it is what will be evaluated at run-time. The Lisp environment will see that its first atom (`format`) is a function, and evaluate it, passing it the rest of the arguments.

In Lisp achieving this task is easy (correct me if I'm wrong) because code is implemented as list (s-expressions?).

Now take a look at this OCaml (which is not a homoiconic language) snippet:

```
let print () =
    let message = "Hello world" in
    print_endline message
;;

```

Imagine you want to add homoiconicity to OCaml, which uses a much more complex syntax compared to Lisp. How would you do that? Does the language has to have a particularly easy syntax to achieve homoiconicity?

**EDIT**: from this topic I found another way to achieve homoiconicity which is different from Lisp's: the one implemented in the io language. It may partially answer this question.

> Here, let’s start with a simple block:
>
> ```
> Io> plus := block(a, b, a + b)
> ==> method(a, b,
>         a + b
>     )
> Io> plus call(2, 3)
> ==> 5
>
> ```
>
> Okay, so the block works. The plus block added two numbers.
>
> Now let’s do some introspection on this little fellow.
>
> ```
> Io> plus argumentNames
> ==> list("a", "b")
> Io> plus code
> ==> block(a, b, a +(b))
> Io> plus message name
> ==> a
> Io> plus message next
> ==> +(b)
> Io> plus message next name
> ==> +
>
> ```
>
> Hot holy cold mold. Not only can you get the names of the block params. And not only can you get a string of the block’s complete source code. You can sneak into the code and traverse the messages inside. And most amazing of all: it’s awfully easy and natural. True to Io’s quest. Ruby’s mirror can’t see any of that.
>
> But, whoa whoa, hey now, don’t touch that dial.
>
> ```
> Io> plus message next setName("-")
> ==> -(b)
> Io> plus
> ==> method(a, b,
>         a - b
>     )
> Io> plus call(2, 3)
> ==> -1
>
> ```

# Answer
You can make any language homoiconic. Essentially you do this by 'mirroring' the language (meaning for any language constructor you add a corresponding representation of that constructor as data, think AST). You also need to add a couple of additional operations like quoting and unquoting. That's more or less it.

Lisp had that early on because of its easy syntax, but W. Taha's MetaML family of languages showed that it's possible to do for any language.

The whole process is outlined in Modelling homogeneous generative meta-programming. A more lightweight introduction to the same material is here.
> 12 votes

# Answer
The Ocaml compiler is written in Ocaml itself, so *certainly* there is a way to manipulate Ocaml ASTs in Ocaml.

One might imagine adding a built-in type `ocaml_syntax` to the language, and having a `defmacro` built-in function, which takes an input of type, say

```
f : ocaml_syntax -> ocaml_syntax

```

Now what is the *type* of `defmacro`? Well that really depends on the input, as even if `f` is the identity function, the type of the resulting piece of code is dependent on the piece of syntax passed in.

This problem does not arise in lisp, since the language is dynamically typed, and no type needs to be ascribed to the macro itself at compile time. One solution would be to have

```
defmacro : (ocaml_syntax -> ocaml_syntax) -> 'a

```

which would allow the macro to be used in *any* context. But this is unsafe, of course, it would allow a `bool` to be used in stead of a `string`, crashing the program at run-time.

The only principled solution in a statically-typed language would be to have *dependent types* in which the result type of `defmacro` would be dependent on the input. Things get quite complicated at this point though, and I would start by pointing you at the nice dissertation by David Raymond Christiansen.

In conclusion: having complicated syntax is not an issue, since there are many ways to represent the syntax inside the language, and possibly use meta-programing like a `quote` operation to embed the "simple" syntax into the internal `ocaml_syntax`.

The issue is making this well-typed, in particular having a run-time macro mechanism that does not allow for type errors.

Having a *compile-time* mechanism for macros in a language like Ocaml is possible of course, see e.g. MetaOcaml.

Also possibly useful: Jane street on meta-programing in Ocaml
> 7 votes

# Answer
As an example consider F# (based on OCaml). F# is not fully homoiconic, but supports getting the code of a function as an AST under certain circumstances.

In F#, your `print` would be represented as an `Expr` that is printed as:

```
Let (message, Value ("Hello world"), Call (None, print_endline, [message]))

```

To highlight the structure better, here is an alternative way how you could create the same `Expr`:

```
let messageVar = Var("message", typeof<string>)
let expr = Expr.Let(messageVar,
                    Expr.Value("Hello world"),
                    Expr.Call(print_endline_method, [Expr.Var(messageVar)]))

```
> 2 votes

---
Tags: programming-languages, functional-programming
---


title: Why aren't numbers stored this way?

text:
# Question
Title: Why aren't numbers stored this way?
I read that the further you get from 0, the less precision, due the way they are stored.

So why aren't numbers stored like this: $32$ bits for representing a value between $-2^{31}$ and $2^{31}-1$ before the decimal point and another $32$ bits for representing the precision. $\frac{1}{2^{32}} = 0,00000000023$, which would be a fairly precise interval.

With this type of storage there would be no precision loss at high values.

# Answer
> 6 votes
In a floating point, by definition, the point floats. What you're proposing is fixed point (which is occasionally used in practice).

A normal IEEE 754 64-bit double precision can store values in the range from $-10^{308}$ to $10^{308}$. This is a much larger range than your system can store given 64 bits (you would need nearly 800 bits to achieve the same).

The precision loss is often acceptable. When you are dealing with a very large value (like $10^{308}$) what comes at the $10^{\textrm{th}}$ place after the decimal point has no significant impact on the outcome of your calculation. When you are dealing with a very small value (like $10^{-20}$), what comes at the $10^{\textrm{th}}$ place after the decimal point has a huge impact on your calculation.

Using floating point thus makes a lot of sense: you get a level of precision that is appropriate for the range of values you're dealing with, and it can represent a very wide range of values in limited space.

# Answer
> 3 votes
The gravitational constant is about $6.67 \times 10^{-11} N m^2 kg^{-2}$.

You would want a scheme that allows storing this number at the full known precision. Unfortunately, it is about 1 quarter of the smallest non-zero number that your scheme can represent.

Avogadro's constant is about $6 \times 10^{23} mol^{-1}$.

The opposite problem; this is more than $10^{14}$ times larger than the largest number in your scheme.

IEEE 754 format floating point numbers can approximate numbers in a huge range. You have been misled by the notion that precision is lower as you go further away from zero. But *relative* precision stays the same.

---
Tags: number-formats
---


# Question
Title: Do static and dynamic scoping matter to the closure of a function?
If I am correct,

* The closure of a function is the non-local environment of the function.
* the non-local environment of a function is different depending on static or dynamic scoping.

So is the closure of a function also different depending on static or dynamic scoping?

Thanks.

# Answer
> 6 votes
I'd view it this way:

* In dynamic scoping, functions only ever access the local environment
* In lexical scoping, functions access the environment in which they are created. Because this is non-local to their calling environment, it must be stored in a closure.

Closures really aren't a thing in dynamic scoping: instead of looking for variables in the closure, you look for variables in the environment in which the function was called.

The process of closing over (storing) the environment is what makes static scoping static scoping.

---
Tags: programming-languages
---


title: How do you prove Sigma Star is regular

text:
# Question
Title: How do you prove Sigma Star is regular
I noticed in another answer on this forum

> Note that the languages ∅, {ϵ} and Σ\* are regular.

How do you prove Sigma Star is regular.

# Answer
> 1 votes
It's easy to design a DFA that accepts $\Sigma^\*$. Or, if your definition of regular languages is in terms of regular expressions, then the regular expression $(a\_1\mid\dots\mid a\_k)^\*$ matches $\Sigma^\*$, where $\Sigma = \\{a\_1, \dots, a\_k\\}$.

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


title: How would P2P Kriegspiel be designed?

text:
# Question
Title: How would P2P Kriegspiel be designed?
Kriegspiel chess is a variant of chess in which each player is not aware of where the opponent's pieces are. In a human match, a trusted intermediary relays piece losses, legality of moves etc. This is, of course possible on a computer as well. What would a peer to peer implementation of Kriegspiel look like, in terms of algorithms for authentication, one in which:

1. There is nobody sending or receiving information besides the two players.
2. Each player can independently verify the information sent is true (storing previous data is of course allowed)
3. All the functions of the intermediary are filled (players are aware of invalid moves, and of when pieces are taken.
4. No player is sent information which makes him certain of information he shouldn't know (e.g the position of the opponent's pieces) besides logical means, of course.

I have looked into zero knowledge proofs somewhat, and was interested in a way they could be implemented in a situation like this.

How would a cheat-proof version of P2P Kriegspiel be implemented?

or, alternatively since that question was deemed too vague

What computer science concepts, protocols, and general algorithms would go into the implementation of such a game?

# Answer
> 2 votes
It would use secure 2-party computation. There would probably be commitments to the statuses of the pieces and oblivious transfers to simulate referee responses and zero-knowledge protocols to show that the players are behaving as they should with respect to the above 2 parts.

If you're taking the oblivious transfer functionality as given and assuming the players are semi-honest, then I'm willing to try coming up with more details here.  On the other hand, if you're interested in how the oblivious transfers would be performed or how the zero-knowledge protocols would work, then you should ask on crypto.

---
Tags: correctness-proof, authentication, peer-to-peer
---


# Question
Title: How does consistency imply that a heuristic is also admissible?
A heuristic function $h (n)$ is...

* *Consistent* if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal.
* *Admissible* if $h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.

# Answer
> 14 votes
To proof the statement in your question, let us proof that *consistency* implies *admissibility* whereas the opposite is not necessarily true. This would make *consistency* a stronger condition than the latter.

*Consistency implies admissibility:*

Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is *admissible* (where $t$ is a goal) since edge costs are assumed to be non-negative and thus, the optimal cost from one node to itself is necessarily 0. This certainly holds in case the heuristic function is *admissible* but we want to proof that *consistency* necessarily implies *admissibility*. For this, let us assume further that $h(t)=0$ for any goal ---and this fact will be used in the base case below.

The proof proceeds by induction:

**Base case**: take any predecessor of the goal node $t$. Let $n$ denote it, so that $t$ is a successor of $n$. If the heuristic function is *consistent*, then $h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$ and hence, $h$ behaves admissibly in this case.

Note that the base case does not assume that the edge $\langle n, t\rangle$ is necessarily the optimal solution from $n$ to $t$ and, indeed, there might be a different path from $n$ to $t$ with a lower cost. The importance of the base case, is that $h(n)\leq c(n,t)$ for all ancestors of node $t$! This result will be reused in the induction step.

**Induction step**: consider a node $n$. The optimal cost to reach the goal $t$ from $n$, $h^\*(n)$, is computed as: $\min\_{m\in\mathrm{SCS(n)}}\\{c(n,m)+h^\*(m)\\}$, where $\mathrm{SCS}(n)$ is the set of successors of node $n$. As *consistency* is assumed by hypothesis, then $h(n)\leq c(n,n')+h(n')$. Furthermore, as $h(n')\leq h^\*(n')$ is assumed by the induction step then $h(n)\leq c(n,n')+h^\*(n')$ and this is true for all successors $n'$ of node $n$. In other words: $h(n)\leq \min\_{m\in\mathrm{SCS(n)}}\\{c(n,m)+h^\*(m)\\} = h^\*(n)$, so that $h(n)\leq h^\*(n)$.

*Admissibility does not necessarily imply consistency:*

For this, a simple example suffices. Consider a graph which consists of a single path with 10 nodes: $\langle n\_0, n\_1, n\_2, ..., n\_9\rangle$, where the goal is $n\_9$. Let us assume *wlog* that all edge costs are equal to 1. Obviously $h^\*(n\_0)=9$, and let us make $h(n\_0)=8$, $h(n\_i)=1, 1\leq i\<9$ and $h(n\_9)=0$. Clearly, the heuristic function is *addmissible*:

1. $h(t)=0$
2. $h(n\_i)=1\leq h^\*(n\_i)=(9-i)$, $\forall i, 1\leq i\<9$.
3. Finally, $h(n\_0)=8\leq h^\*(n\_0)=9$.

However, $h(n)$ is not *consistent* and $h(n\_0)=8 \> c(n\_0, n\_1)+h(n\_1)=1+1=2$.

Hope this helps,

---
Tags: algorithms, shortest-path, heuristics
---


# Question
Title: Prove a language is regular - Regular language of 0's and 1's
I'm new to regular languages and I've been struggling to solve one for a while. The question is:

> If there exists a regular language L1 which has an alphabet {0,1}, prove that L2 is also a regular language if L2 comprises of strings x where x = ABC where B is an element in L1 and A and C are strings comprised of 0's and 1's.

I intuitively believe that since we know L1 is a regular language, we know that any string of 0's and 1's is a regular language. Hence, L2 should be a regular language as it is comprised of only 0's and 1's (by definition). Apparently, this is the wrong approach. Can someone assist me in solving this problem?

Thank you!

EDIT:

I realize my explanation was off. We know that L1 is a regular language composed of strings of "0" and "1", for example, "000111", "010101", could exist as elements in this language. If there are finite elements inside the language, then clearly by mutlipying it by two constant strings, we will get a finite output (hence regular). However, if it is not finite, that means it must have a regular expression that describes the language. Thus, any concatenation with two similar strings will still be that same regular expression with two constants added on top of it (hence still represented by a reg ex and thus a regular language).

Where is my logic flawed?

Thank you!

# Answer
> 0 votes
**Hint**. The language $L\_2$ is the concatenation of the languages $U$ and $L\_1$, namely $L\_2 = U\circ L\_1\circ U$, where $U$ is the set of all strings over $\\{0,1\\}$.

* Is $U$ a regular language?
* If so, what do you know about the concatenation of regular languages?

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


# Question
Title: Relationship between height and depth of a binary tree
The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree.

The following binary tree is full according to the wikipedia definition (every node has 0 or 2 children), n = 11, h = 4 but n is not greater than $2^4 - 1 = 15$.

Am I missing something?

```
                        .
                       /  \
                      a    .
                          / \
                         b   .
                            / \
                           .   .
                          / \ / \
                         c  d e  f

```

# Answer
You're not missing anything: it's a typo, which I've fixed. The page gives two separate definitions of "full binary tree" (a recursive one and the one you quote) and both of them include the following trees, which have even fewer nodes than yours ($2n-1$, to be precise):

```
  o
 / \
o   o
   / \
  o   .
       .
        .
         \
          o
         / \
        o   o

```
> 3 votes

# Answer
If you think about how you get these bounds¹ it's quite clear that they apply to *complete* binary trees, using terms from the article.

To be fair, the terminology around binary trees is ambiguous, overloaded, and inconsistent in the literature. It becomes worse if you use multiple languages. Hence, it comes to no surprise that a crowd-edited medium without real quality control such as Wikipedia would have errors.

---

1. Hint: $\sum 2^i$
> 2 votes

---
Tags: graphs, trees, binary-trees
---


# Question
Title: If f(n) = Θ(g(n)) then what all can one say about f(h(n)) and Θ(g(h(n))
I was going across some problems which translated the fact that $\log (n!) = \Theta(n\log n)$ to give $$\log(\lceil\log n\rceil!) = \Theta(\lceil\log n\rceil \log \lceil\log n\rceil)$$ and therefore $\log(\lceil \log n\rceil!) = \omega(\lg n)$.

Now I just have this intuition that this sort of conversions shouldn't and wouldn't be always right.

Would it be right to think that.

Any justification as to why am I wrong in thinking that and guidance to what I should have a look at, what texts I should go through to understand it better for myself are very much appreciated.

Thank you.

# Answer
> 6 votes
In general, you can prove nothing. You know $f(n) = \Theta(g(n))$. Now assume f (n) = g (n) = n for all n except g (n) = 0 if n ≤ 1000. And h (n) = 1000 for all n.

So we now have f (h (n)) = 1000 and g (h (n)) = 0.

The problem is that $O (n)$ and $\Theta (n)$ only work for large n. You are fine if h (n) -\> inf, or if you look specifically at f (n) and h (n).

If the limit of h (n) is infinity, then you overcome the problem that $\Theta(g(n))$ only gives you information for n ≥ N for some possibly large N, because h (n) will eventually be greater than that N.

# Answer
> 2 votes
Below, I'm assuming that the domain of all function is the non-negative reals.

By definition, $f(n) = \Theta(g(n))$ if there exist $N \geq 0$ and $A,B \> 0$ such that $$ n \geq N \Longrightarrow A g(n) \leq f(n) \leq B g(n). $$ If there exists a constant $c \> 0$ such that $f(n),g(n) \geq c$ for all $n$ and $f,g$ are continuous, then we can in fact take $N = 0$ (perhaps modifying $A,B$ in the process). This means that for all $n$, it holds that $$ A g(n) \leq f(n) \leq B g(n). $$ Assuming that $h(n) \geq 0$ for all $n$, this implies that $$ A g(h(n)) \leq f(h(n)) \leq B g(h(n)), $$ and so $f(h(n)) = \Theta(g(h(n))$.

Even without assuming that $N = 0$, we can make the same conclusion if $\lim\_{n\to\infty} h(n) = \infty$. In that case, there exists $M$ such that $n \geq M$ implies $h(n) \geq N$, and so $$ n \geq M \Longrightarrow A g(h(n)) \leq f(h(n)) \leq B g(h(n)), $$ again implying $f(h(n)) = \Theta(g(h(n))$.

# Answer
> 2 votes
Why would there be a problem? You know that $\log (t!) = \Theta(t\log t)$. Why would it matter whether you call the thing $t$ or $\lceil\log n\rceil$? (As long as you can make $\lceil\log n\rceil$ large enough for the asymptotic relationship to kick in; and you can.)

---
Tags: asymptotics, landau-notation
---


# Question
Title: How much information, in bits, is conveyed by a 3-bit output representing how many 1s in a 7-bit input?
Let's say I have a combinational device that has an input of 7 bits and outputs a 3-bit binary number that reflects the number of 1s among the 7 bits. How much information would be conveyed by the following outputs: 000 and 001? I know information, in bits, is calculated by log2(1/p), and p is M/N, where N is the number of equally probable choices, and M is the amount of choices left after being given a piece of data.

# Answer
Assuming the 7-bit input is chosen randomly, the entropy of the number of 1s is $$ \sum\_{i=0}^7 \frac{\binom{7}{i}}{2^7} \log \frac{2^7}{\binom{7}{i}} \approx 2.45 \text{ bits}. $$ This is because the probability that the number of 1s is $i$ equals $\binom{7}{i}/2^7$.

You are asking how much information is conveyed by particular outputs, and this can be interpreted as the loss in entropy: if $X$ is the random 7-bit input and $Y$ is its sum, you could define the information conveyed by $Y=i$ as $H(X)-H(X|Y=i)$. Since $X$ has uniform distribution, $$ H(X) - H(X|Y=i) = \log 2^7 - \log \binom{7}{i} = \log \frac{2^7}{\binom{7}{i}}. $$ The information conveyed by different outputs, under this definition, works out to be roughly (in bits): $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline H(X) - H(X|Y=i) & 7 & 4.19 & 2.61 & 1.87 & 1.87 & 2.61 & 4.19 & 7 \\\hline \end{array} $$ The weighted average of these values equals the entropy calculated above.
> 2 votes

---
Tags: information-theory
---


# Question
Title: Can g(n) be same for big O and omega notation for f(n)
I have been studying asymptotic notation and I understand that in big O notation $f(n) \<=c1\*g(n)$ and in omega notation we have $f(n)\>= c2\*g(n)$ where $c1$ and $c2$ are some constant.

Now I was wondering if the function $g(n)$ here are the same and the big O and omega of $f(n)$ is determined by constants $c1$ and $c2$. Or if the $g(n)$ is different for O and omega.

If $g(n)$ is indeed same can anyone explain with example how is it possible as I can think of the examples in which $g(n)$ is different in both cases.

# Answer
> 1 votes
If you write down $f \in O(g)$ and $f \in \Omega(g)$ then you clearly intend both instances of "$g$" to refer to the same function. Otherwise, it would be pretty confusing.

Note how this is equivalent to $f \in \Theta(g)$.

If, however, you write down $f \in O(n^2)$ and $f \in \Omega(n)$ and want to unfold both the definition of $O$ and $\Omega$, you'll have to instantiate two different "$g$"s. That is, you'd write

$\qquad c\_1 g\_1(n) \leq f(n) \leq c\_2 g\_2(n)$

for all $n \geq n\_0$ for some $c\_1, c\_2 \> 0$ and $n\_0 \geq 0$. Here, we know that $g\_1 = n \mapsto n$ and $g\_2 = n \mapsto n^2$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: What does this definition of a Primary key mean?
My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated.

> Let $R$ be a relation. Then the primary key for $R$ is a subset of the set of attributes of $R$, say $K$, satisfying the following two properties:
>
> 1. Uniqueness Property: No two distinct tuples of $R$ have the same value for $K$.
> 2. Irreducibility Property: No proper subset of $K$ has the uniqueness property.

I'm getting lost by the Irreducibility property.

# Answer
Consider the following table:

```
FirstName  LastName  Pet  FavColour
-----------------------------------
Alice      Jones     dog  red
Alice      Smith     dog  green
Bob        Smith     cat  blue

```

A key is any set of attributes: any subset of {FirstName, LastName, Pet, FavColour}. The uniqueness property says that no two records can have the same values for the attributes in a key. So, for example, {FavColour} is a key that has the uniqueness property: no two records have the same value for it. {Firstname, Lastname} is also unique: no two records have the same first and last name. {Pet}, on the other hand, is not unique, since the first and second records have the same value for that attribute.

Now, {FirstName, LastName, Pet, FavColour} is also a unique key: no two records have the same value for all the attributes. But that's kind of a silly key, right? Irreducibility says that, if you remove any of the attributes from your key, it stops being unique. So {Firstname, LastName, Pet, FavColour} isn't irreducible because, if you remove FavColour, you get the key {FirstName, LastName, Pet}, which still has uniqueness. And *that* isn't irreducible because you can throw away Pet and get {FirstName, LastName}, which is still unique. However, {FirstName, LastName} is irreducible because neither {FirstName} nor {LastName} is unique: there are two people with the same first name and two people with the same last name.
> 8 votes

# Answer
Note how $K$ can be a *set* of columns. Irreducibility means that you have to pick *minimal* sets of columns.

*Nota bene:* They should require $K \neq \emptyset$.

For instance, consider this relation.

```
A   B   C

1   4   4
2   4   6
3   6   6

```

Let us investigate all possible keys.

1. `A` -- unique and irreducible.
2. `B` -- not unique.
3. `C` -- not unique.
4. `A,B` -- reducible to `A`.
5. `A,C` -- reducible to `A`.
6. `B,C` -- unique and irreducible.
7. `A,B,C` -- reducible to `A`.

Hence, there are two choices for primare keys here: `A` and `B,C`.
> 14 votes

# Answer
Irreducibility simply refers to a minimum set of attributes that we can't go below without losing uniqueness. For example, in a table of people, we may find (Lastname, Firstname) are unique while (Lastname) and (Firstname) are not.

Once we have uniqueness we can keep adding attributes without losing it, so irreducibility addresses that problem.
> 1 votes

---
Tags: database-theory
---


# Question
Title: Circle Hough Transform. Improvement by knowing edge direction
I'm studying Hough Transform. I have fully understood the HT for detecting lines and successfully implemented it. I have more problems with the circle detection HT. Given a circle, if the radius is known i have to work in a 2d parameter space (each point in the image space becomes a circle in the parameter space; the intersection of all the circles gives me the center of the image circle). If the radius is not known the parameter space becomes 3d. What i don't understand is why if i know the direction of the edges, even if my radius is unknown the parameter space lowers to 2d.

# Answer
Consider circles of the form

$$(x - a)^2 + (y - b)^2 = r^2$$

The Circular Hough Transform with unknown radius and unknown gradient information has a parameter space $(a, b, r) \in H$. Given a single edge point we'd end up drawing a right cone increasing along the positive $r$ axis with its tip centered at $(x, y, 0)$.

Now to your question. When you know the gradient $\nabla I(x,y)$ of an edge point, $(x,y)$ from your image $I$, you have a vector originating from the center of the circle pointing outward. Since you have your edge point $(x,y)$ the center $(a, b)$ must lie somewhere along the lines $(x,y) \pm r \nabla I(x,y)$. There is only one variable in that statement, $r$.

Now the Circular Hough Transform becomes: for each edge point $(x,y)$, and for each plausible radius $r$, calculate $(a, b) = (x, y) \pm r \nabla I(x,y)$ and increment the accumulator array index $(a, b, r)$ by $1$. Then you go a do your usual vote counting to find the most likely parameters $(a, b, r)$.

For further details refer to D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes" Pattern Recognition. Vol.13. 1981. Extends this concept to ellipses, general analytic curves, and the general transform.
> 2 votes

---
Tags: image-processing, computer-vision
---


# Question
Title: In Asyptotic notation if g(n) < f(n) is it possible to have f(n)<=c*g(n)
I am studying asymptotic notation and I was thinking of a possibility where if g(n) \< f(n) is it possible to have f(n)\<=c*g(n). For example if - f(n)=6n+5 and g(n)=4n+5, such that it possible to say (6n+5)\<=2*(4n+5) where 2 is c. Are f(n) and g(n) here valid function in term of asymptotic notation.

# Answer
> 2 votes
Everything depends on the type of relation you want to define between f and g.

In O and Ω you just have to find one c\>0 and one N for which the corresponding inequality between f and g holds and the relation shall be established.

In o and ω you have to show that for every c\>0 you can find some N such that the corresponding inequality shall hold for all n \> N.

Perhaps this can help you understand it better.

---
Tags: asymptotics
---


# Question
Title: Why does the interrupt disable method to achieve mutual exclusion not work for multiprocessor systems?
The interrupt disable method to achieve mutual exclusion works for uniprocessor systems. Why does the interrupt disable method to achieve mutual exclusion not work for multiprocessor systems?

# Answer
Mutual exclusion means that during some time, a certain piece of code (called a critical section) has exclusive control over a resource. Interrupts can break that because they cause control to be transferred from critical section to the interrupt handler. Code running on other processors can break that because they can access the resource at the same time. Therefore, on a multiprocessor machine, disabling interrupts is not sufficient to achieve mutual exclusion. There also needs to be a way to prevent the other processors from accessing the resource.

Disabling interrupts is sufficient when it's the only way for the critical section to lose control. On a multiprocessor machine, the critical section does not have exclusive control in the first place.
> 7 votes

---
Tags: operating-systems
---


# Question
Title: Book containing many important CS papers
Several years ago my professor gave me a book that contained the most important computer science papers, including Von Neuman's paper on architectures and Dijkstra's Go-To paper. The book was an older, blue hard-cover.

Sadly, it got lost somewhere... and so I thought this might be a good place to see if anybody can point me at its editors, title, place where I can purchase it?

Does anybody know the book?

# Answer
> 8 votes
If I had to bet, I'd say:

> **Great Papers in Computer Science**
>
> Author: Laplante, Phillip A.
>
> Publisher: West Publishing Co.

(this one or an older edition).

---

### Contents

* **Algorithms and Data Structures**

+ 1.1 The Complexity of Theorem Proving Procedures (Stephen A. Cook)
    + 1.2 On the Conceptual Complexity of Algorithms (J. Hartmanis, R. E. Stearns)
    + 1.3 Quicksort (C. A. R. Hoare)
    + 1.4 Finite Automata and Their Decision Problems (M. O. Rabin, D. Scott)
* **Programming Languages**

+ 2.1 The FORTRAN Automatic Coding System (J. W. Backus, et al.)
    + 2.2 An Axiomatic Basis for Computer Programming (C. A. R. Hoare)
    + 2.3 An Axiomatic Definition of the Programming Language Pascal (C. A. R. Hoare, N. Wirth)
    + 2.4 The Contour Model of Block Structured Processes (John B. Johnston)
    + 2.5 On the Translation of Languages from Left to Right (Donald E. Knuth)
    + 2.6 Revised Report on the Algorithmic Language ALGOL 60 (Peter Naur, et al.)
* **Architecture**

+ 3.1 First Draft of a Report on the EFVAC (John von Neumann)
    + 3.2 A Symbolic Analysis of Relay and Switching Circuits (Claude E. Shannon)
    + 3.3 Alto: A Personal Computer (C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, D. R Boggs)
    + 3.4 The Best Way to Design an Automatic Calculating Machine (M. V. Wilkes)
* **Numerical and Scientific Computing**

+ 4.1 On Computable Numbers, with an Application to the Entscheidungsproblem (A. M. Turing)
    + 4.2 On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction (A. M.Turing)
* **Operating Systems**

+ 5.1 Cooperating Sequential Processes (Edsger W. Dijkstra)
    + 5.2 Solution of a Problem in Concurrent Process Control (Edsger W. Dijkstra)
    + 5.3 A Formal System for Information Retrieval from Files (David Hsiao, Frank Harary)
* **Software Methodology and Engineering**

+ 6.1 No Silver Bullet — Essence and Accidents of Software Engineering (Frederick P. Brooks)
    + 6.2 Guarded Commands, Nondeterminancy, and Formal Derivation of Programs (Edsger W. Dijkstra)
    + 6.3 Go To Statement Considered Harmful (Edsger W. Dijkstra)
    + 6.4 Proof of Correctness of Data Representations (C. A. R. Hoare)
    + 6.5 On the Criteria to be Used in Decomposing Systems into Modules (David L. Parnas)
    + 6.6 A Rational Design Process: How and Why to Fake It (David L. Parnas, Paul C. Clements)
    + 6.7 Global Variables Considered Harmful (W. Wulf, M. Shaw)
* **Databases**

+ 7.1 The Theory of Joins in Relational Databases (A. V. Aho, C. Beeri, and J. D. Ullman)
    + 7.2 Organization and Maintenance of Large Ordered Indexes (R. Bayer, E. Mccreight)
    + 7.3 The Entity Relationship Model - Toward A Unified View of Data (Peter Pin-Shan Chen)
    + 7.4 A Relational Model of Data for Large Shared Data Banks (E. F. Codd)
* **Artificial Intelligence and Robotics**

+ 8.1 Steps Toward Artificial Intelligence (Marvin L. Minsky)
    + 8.2 Matter, Mind, and Models (Marvin L. Minsky)
    + 8.3 Fusion, Propagation, and Structuring in Belief Networks (Judea Pearl)
    + 8.4 Computing Machinery and intelligence (A. M.Turing)
* **Human-Computer Communications**

+ 9.1 Programming Considered as a Human Activity (Edsger W. Dijkstra)
* **History**

+ 10.1 Programming in America in the 1950s - Some Personal Impressions (John Backus)
    + 10.2 The Evolution of Data-Base Management Systems (James P. Fry, Edgar H. Sibley)
    + 10.3 The Evolution of the UNIX Time-Sharing System (Dennis M. Ritchie)

---
Tags: reference-request, books
---


# Question
Title: What is the quickest way to allocate a set of points to a fixed number groups based on Euclidean distances from a point in each group?
Example, if i have certain geographic points in an array A=\[a,b,c,d...n\] and have 10 points distributed in the solution space B= \[1,2,3...10\], how can I allocate each member of A to the nearest point in B in the quickest way.

# Answer
> 1 votes
This looks very much like the Nearest neighbor problem. The asymptotically most efficient approach is probably computing a k-d-tree on the points in B. Constructing the tree takes $O(|B| \log |B|)$ and lookup is logarithmic, so an additional $O(|A| \log |A|)$ to find all nearest neighbours.

Please not that the constant factors for the naive approach where you just compute the distance to each point in B and take the minimum are really good. CPUs are very good at just summing squared differences. In practice it will be hard to beat that unless B is really huge.

---
Tags: algorithms, code-generation
---


# Question
Title: Difference between Normative annexes and Informative annexes in ADA 95
I was reading the ADA 95 reference manual. I came across these two words in annexes Normative and informative . I couldnt find the difference between those. Your help will be much appreciated.

# Answer
> 5 votes
"Normative" means something that has to be followed, part of the standard. "Informative" is explanations meant to be understood by mere human beings, and that might be ambiguous or inaccurate. It is *not* to be relied on. Read it to understand, refer to the normative parts where it matters.

# Answer
> -1 votes
"Informative" annexes are a clever way to add requirements and details originally missed or poorly defined by the standard developers. These "corrections" are largely due to the developers academic bias and the general lack of real world experiencing producing actual product. But make no mistake, you'll be expected to meet informative annex content just as if it were in the body.

# Answer
> -5 votes
Normative is it is and informative is it could be. One is certainly settled while the other is yet settled.

---
Tags: reference-request, programming-languages, books
---