# Question
Title: How to determine the time and memory complexity for solving a sliding-tile puzzle?
I have seen many posts which were related to algorithms for solving an **N⨯N puzzle**, but I could not figure out the **time complexity** or **memory complexity** in these algorithms, especially when we want to apply `DFS` and `BFS` for solving our puzzle.

For example, if we assume that at first, the elements are not at their place, but the desired state would be like the below picture. What would be the time and memory complexity, if we want to show them by using ***Big O*** notation?  In this link, it has been told that we can not always find a solution using `DFS` and it is not complete, and also there is an explanation on how to solve the puzzle using `BFS`, but nothing is said about the time and memory complexity.

I will be grateful for a more detailed explanation of these algorithms when they are used for solving a puzzle because I am just a beginner in this field.

# Answer
> 8 votes
The complexity of the BFS and DFS algorithms depend heavily on the graph being analyzed, and the search strategy being used. If we have a method to consistently get "closer" to a solution, then the search can be much more efficient than if we blindly stumble everywhere hoping to find what we need. In this case, I'm going to ignore heuristics for simplicity, and assume that by a BFS solution you mean "blindly try every combination of moves from the start until we find a solution."

The complexity of a BFS over an arbitrary tree with branching factor $b$ and maximum depth $m$ is $O(b^m)$. A branching factor is how many (on average) neighbors there are for every position. The maximum depth is how far we can possibly be from the target position. Some more information on where this fact comes from is available over on StackOverflow.

In this case, the complexity depends on understanding a few things about the puzzle, and the tree that is being searched.

To compute the complexity of a breadth-first search on an $n\times n$ 15-puzzle, we need to know these values.

The branching factor is easier, it's the number of moves we have available. The position can have either 2, 3, or 4 neighbors depending on whether the empty slot is in the center, edge, or corner. There's an exact formula for the branching factor based on how many of these there are. For an $n\times n$ puzzle:

$$\frac{2\cdot 4+3\cdot 4(n-2)+4(n-2)^2}{n^2}=4\frac{n-1}{n}$$

The maximum depth is a little more complicated. The big idea is that for an $n\times n$ puzzle, each individual piece can be at most $2n-1$ positions away from its destination (on opposite corners). On average, if you randomly place pieces on the board, you will get some linear proportion of this value\* for each of the $n^2-1$ positions. Multiplying these, we get something on the order of $O(n^3)$.

Putting these two values together, we get that the complexity is:

$$O\left((4\tfrac{n-1}{n})^{n^3}\right)\in O\left(4^{n^3}\right)$$

In practice you can reduce this complexity a bit by choosing a smarter algorithm. For instance, keeping track of visited states to avoid repeated effort will at worst hit the $O(n^2!)$ positions, which is a considerable improvement (at the cost of much worse memory complexity). Heuristic searching reduces this bound by even more, and if we permit finding *any* solution rather than the *best* solution, there are algorithms that hit the $O(n^3)$ move bound directly\*.

* More information on this can be found in Chris Calabro, Solving the 15-Puzzle, 2005

---
Tags: artificial-intelligence, depth-first-search, breadth-first-search
---


# Question
Title: Assume we know that (1) $A$ reduces to $B$ in time $O(f(n))$ time and (2) $B$ reduces to $A$. What can we say about the time for $B$ -> $A$?
The question is basically the title. If two NP-Complete problems reduce to each other, do we know that the reductions take equal amounts of time? What about space? Does this apply for all 'invertible' reductions?

# Answer
I don't think you'll find a positive answer, since it would imply $\mathsf{P} \neq \mathsf{NP}$. Indeed you can show that $\mathsf{P}=\mathsf{NP}$ implies that the answer is "no" (and hence you have the contrapositive implication).

If $\mathsf{P}=\mathsf{NP}$ then all problems within $P$, except for $\emptyset$ and $\Sigma^\*$, are $\mathsf{NP}$-complete and reduce to each other. Consider now a finite language $A \in \mathsf{P} \setminus \\{ \emptyset, \Sigma^\* \\}$ and and any language $B \in \mathsf{B}$ that can't be decided in constant time (e.g., "is the number of 0s" in the input even?"). Clearly $A$ can be reduced to $B$ in time $O(1)$, (check if the input is in $A$ in constant time, and return either a fixed yes-instance of $B$ or a fixed no-instance of $B$), but $B$ cannot be reduced to $A$ in the same time.

Perhaps somebody can point out a non-conditional argument for the answer being "no".
> 1 votes

---
Tags: turing-machines, np-complete, reductions
---


# Question
Title: Invariant in Kosaraju's algorithm for SCCs
I am studying graph algorithms, and I know that in algorithm theory there has to be an invariant of sorts that stays the same during the algorithm run that makes the algorithm valid and right to use. But I can't seem to find the invariant in Kosaraju's algorithm for finding strongly connected components. What is it that stays the same when we traverse the inverted graph in order produced by DFS-traversing the original one?

# Answer
I think that there are several invariant, but the one that seems most important is the following:

« for any edge $(u, v)\in E$, if the SCC of $u$ has been visited, then the SCC of $v$ has been visited »

That means that you are visiting SCC's from sinks to sources.
> 2 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: How does one define transcendental numbers (such as Pi) in theory of general recursive functions
On a **turing machine** and in the **lambda calculus** one can define transcendental numbers such as Pi, the golden ratio, etc. These are computatible functions with 0-arity that never terminate. In the theory of **general recursive functions** (which also defines the same class of functions as **turing machines** and **lambda calculus**) the output is always a natural number N, or undefined. How does one define transcendental numbers in the theory of **general recursive functions** (mathematical functions defined by Gödel)

# Answer
> 4 votes
If you are only interested in transcendental (or at least only irrational) numbers, you can safely identify the number $x$ with the function $d\_x : \mathbb{N} \to \mathbb{N}$ that on input $n$ outputs the $n$-th digit of the decimal expansion of $x$.

If you want all real numbers, that does not lead to a satisfactory theory of computation. A suitable way to handle reals there is to let a function $f : \mathbb{N} \to \mathbb{N}$ code a real number $x$ if $$\forall n \in \mathbb{N} \ |\nu(f(n)) - x| \< 2^{-n}$$ where $\nu : \mathbb{N} \to \mathbb{Q}$ is some standard bijection. This means that there are many functions coding the same real, but that is unavoidable.

---
Tags: turing-machines, computability, lambda-calculus, generating-functions
---


# Question
Title: Matching students with companies based on their preference
I have a list of companies with *n* timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to.

Is there an algorithm to efficiently match those students to timeslots, taking the student's preferences into account?

I already did some research, and I think I could find some answers in the field of Graph Theory, but I'm really new to this.

Your help would be really appreciated.

Thank you in advance.

# Answer
One approach is to model this as a weighted bipartite matching problem, also known as the assignment problem. This is appropriate if the objective function you're trying to maximize is the sum of "goodness scores" associated with each timeslot that gets filled.

Another approach is to model this as an instance of the stable marriage algorithm. This is appropriate if you're trying to achieve some other goal, namely, that no pair of students or companies would be happier by switching places with each other.

These will give you different solutions that try to achieve different aims.
> 1 votes

# Answer
Co-operative Education | University of Waterloo pioneered this kind of thing in the 1960s.

I (and thousands of other students) were paired with all of our top-10 choices for interviews, I don't remember anyone having problems with it, and that was 50 years ago.

They currently handle 7000+ employers. You might talk to someone at UW to see what algorithms they use.
> 0 votes

---
Tags: algorithms, graphs, matching, bipartite-matching
---


# Question
Title: What is the meaning of the term "computational process" in the book SICP?
I'm trying to read chapter one of the famous book : Structure and Interpretation of computer programs.

The chapter one starts with a mysterious paragraph:

> We are about to study the idea of a **computational process**. Computational processes are abstract beings that inhabit computers. **As they evolve**, processes manipulate other abstract things called data. The evolution of a process is **directed** **by a pattern of rules called a program**. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

> A computational process is indeed much like a sorcerer's idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer's spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

What is really a computational process ? And how does that relate to programs in the context of the above paragraphs ?

# Answer
Computer programs are generally written to do something i.e. transform some input to some usually different output. That is the computational process that they are implementing.

Let's look at a concrete example. On unix there's a program named sort, the computational process it implements is sorting. There are various command line options that allow the exact nature of the sorting to be configured so that sort can be used for many common tasks requiring the lines of a file or other input to be sorted.
> 1 votes

# Answer
The most concrete concept mentioned in that definition is *a program*, which is created (notice: not usually written) by a programmer. Okay, maybe a programmer is a more concrete concept, but this is beside the point.

I *say not usually written* because programs are modernly written in high-level programming languages and then at some point translated into machine code instructions (often assuming intermediate forms along the way).

Those instructions are binary input signals (i.e. bits) represented by coded instructions understandable by a computer.

They are loaded into the main memory for the computer CPU (central processing unit, also called processor) to execute them.

The program itself is just a specific bit pattern.

Those instructions are decoded by the hardware into signals that control the various parts of the processor and main memory (RAM), in particular the ALU (arithmetic logic unit), causing it to operate on the data present in processor-local registers, which are loaded and stored from/to the main memory.

That electron dance performing an evolving data manipulation characterizes a computational process.

I believe this is no different than saying that a regular computer process run by e.g. a modern operating system on (ultimately) a CPU performs an evolving data manipulation (I refer to the ones you can see on Windows Task Manager, for instance).

As the process is executed, the data manipulation evolves -- although I'd daresay an infinite loop also could be called an evolving process.

You can see how this description matches the definition you provided.
> 0 votes

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


# Question
Title: Machine Learning algorithm to learn submodular set functions
I'm looking for some machine learning algorithm to train on data that are sampled from some submodular set function and I want the learned model predictions also obey submodularity. For example linear regression can do this (because it's linear hence it produce a model that obey both submodularity and supermodularity) but I want a model that is not linear and can capture some non-linear relationships in the data.
I played with SVR (support vector regression) with some kernels but could not prove anything useful.

# Answer
> 0 votes
One possible approach is to train a model that is guaranteed, by the design of its architecture, to represent a submodular function. The following research paper looks like it might be helpful for that:

Deep submodular functions: Definitions and learning. Brian W. Dolhansky and Jeff A. Bilmes. NeurIPS 2016.

---

Another possible approach might be to learn a set function, and then add a regularization/penalty term to the loss function to penalize any violations of submodularity. There are various methods for learning a set function. One very simple one, if the universe that the set is contained within is small enough, is to simply apply a one-hot encoding of the set, then feed that feature vector to a normal network. If the universe is large, there are more sophisticated methods in the research literature, e.g.,

Deep Sets. Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, Alexander J. Smola. NeurIPS 2017.

Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks. Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, Yee Whye Teh. Proceedings on Machine Learning Research.

Then, if $f\_\theta(S)$ represents the value of the function on set $S$ (using parameters $\theta), we can introduce a penalty term as follows:

$$\Psi(\theta) = \max\_{S,T} \max(f\_\theta(S \cup T) + f\_\theta(S \cap T) - f\_\theta(S) - f\_\theta(T),0).$$

Now add $\Psi(\theta)$ to the loss function, and then train as usual, with this modified loss function. To make this work, you'll need to find a way to compute $\Psi(\theta)$, or at least to estimate it. I'm not immediately sure how to do that, and it might depend on the specific model you use.

---
Tags: machine-learning, kernel-functions
---


# Question
Title: Models of computation less powerful than DFA
I wonder if there are "standard" models of computation that are less powerful than DFA that are still "mathematically interesting"? It is evident that restricting the set of DFAs in various conceivable ways easily yields examples, but would any of those generate considerably interesting mathematical questions?

# Answer
> 2 votes
You might be interested in branching programs, e.g., branching programs of bounded width (say, width 3, or width 5) and bounded length (say, linear length).

You might be interested in probabilistically checkable proofs, where we focus on proofs that can be checked by a very limited form of computation -- namely, a randomized program that only looks at a constant number of bits of the proof. That is an extremely limited model of computation, which leads to some challenging mathematics/theory.

---
Tags: finite-automata, computation-models
---


# Question
Title: Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?
Consider a data structure that has only two functions. extract\_lowerthan\_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)?

Using a 2 tree, a min heap and max heap will ensure that the root of min heap is always the median and allow us to extract an element smaller than median with O(1) cost. However, the insertion would run in O(logn). Since we could amortize these cost there should be a structure which performs both these operations in O(1) where we somehow mask the cost of insertion in extraction but I cant think of anything

# Answer
> 3 votes
#### Amassing many elements significantly lower than median at once

The basic idea is to maintain a list of small elements that are guaranteed to be lower than median. Also maintain a list of all other elements that may or may not be lower than median, which will accept all new elements.

`extract_lowerthan_median` pops an element from the list of small elements most of the time. `insert` appends a new element to the list of other elements most of the time.

When there is no "small elements" or there are too many "other elements", the two lists will be adjusted so that the list of small elements will contain the $\lfloor n/4\rfloor$ smallest elements of all current elements, which can be selected using $O(n)$ operations. The very low frequency of this adjustment ensures the amortized cost of both `extract_lowerthan_median` and `insert` be $O(1)$.

#### The data structure in detail

For simplicity, assume no two numbers are equal.

Assume the median means the middle number when $n$ is odd or the mean of the middle two numbers when $n$ is even. "A number lower (smaller) than median" means any number that is smaller than the median. With the assumption of no equal numbers, a number among the given numbers lower than median also means a number such that the number of numbers larger than it is not smaller than the number of numbers not larger than it.

Build a data structure $D$ with two disjoint (unsorted) lists and a number,

* `small_nums`, a list of small numbers, which is empty initially,
* `other_nums`, a list of numbers, which is empty initially,
* `capacity`, a natural number, which is $0$ initially,

with three functions:

* `extract_lowerthan_median()`:

1. If `small_nums` is empty,
        1. If `len(other_nums) < 8`, return accordingly. That means, if the smallest element is lower than median, pop it from `other_nums` and return it. Otherwise, return none. (`len(a_collection)` is the number of elements in `a_collection`.)
        2. Else, call `amass_small_numbers()`
    2. Pop an element from `small_nums` and return it.
* `insert(new_num)`:

1. Append `new_num` to `other_nums`.
    2. If `len(other_nums) > 5 * capacity`, call `amass_small_numbers()`. This step ensures any element poped from `small_nums` will be lower than median.
* `amass_small_numbers()`:

1. Move all numbers in `small_nums` into `other_nums`.
    2. set `capacity` to `len(other_nums)//4`. (`//` is the integer division such as `7//3=2`). Note that `capacity` is guaranteed to $\ge2$.
    3. Find the (`capacity + 1`)-th smallest element in `other_nums`, using a **linear-time $k$-th-smallest-element selection algorithm** as explained here or here. Denote it by `p`.
    4. Move all `capacity` elements in `other_nums` that are smaller than `p` to `small_nums`.

#### Some minor variations.

* greybeard suggested that `insert(new_num)` at step 1 add `new_num` to `small_nums` instead of `other_nums` if `new_num < p`, where `p` is the pivot computed in the last call to `amass_small_numbers`. (If not, add to `other_nums` as before.)

To implement this variation, the data structure should have one additional variable to store that pivot `p` and another additional variable `pop_count` to store the number of calls to `extract_lowerthan_median` since last call to `amass_small_numbers`. The condition `len(other_nums) > 5 * capacity` at the step 2 of `insert(new_num)` should then be replaced by `len(other_nums) >= 8 and (len(small_nums) + len(other_nums) + pop_count > 6 * capacity or len(small_nums) == 0)`.

This variation may boost the performance, especially when there are lots of `extract_lowerthan_median`.
* Dmitry presented a simplified version.

After amassing the $n/4$ smallest numbers, call `extract_lowerthan_median` and `insert()` at most $n/4$ times together. Neither `extract_lowerthan_median` nor `insert` calls `amass_small_numbers`.

# Answer
> 1 votes
John's answer is probably correct, but I just want to present a simple version that demonstrates the idea (in particular, I ignore the cases when $n$ is small, when there are duplicates, or when $4$ doesn't divide $n$; you can figure them out):

```
Let A be the initial array
while true:
    n := A.length
    Small := n/4 smallest elements of A, in any order
    Others := the rest of the elements of A
    process the next n/4 queries:
        For insert queries: add the new element to Others
        For extract queries: extract any element from Small
    A := (arbitrary) concatenation of Small and Others

```

You can find `Small` and `Others` in $O(n)$ using QuickSelect.

---
Tags: algorithms, data-structures, amortized-analysis
---


title: Consequences of the Halting Problem

text:
# Question
Title: Consequences of the Halting Problem
The halting problem is **semi-decidable**. Does that mean that:

* If a program *terminates* it can always be established/determined?
* If a program does *not terminate*
    + It can sometimes be established/determined?
    + It can sometimes not be established/determined?

When we write programs we can clearly proof in some instances that the program terminates or that it will never terminate. But, simply there are some programs for which we can't proof termination for all inputs.

# Answer
> 2 votes
The Halting Problem is semi-decidable, also called recognizable, and that means there is a Turing Machine $H$ that will, given a Turing Machine $M$ as input, accept $\langle M, s\rangle$ if and only if it halts in finite time on bounded input $s$ and otherwise will reject or fail to halt itself. This means, in a certain sense, that a TM that halts in finite time on an input $s$ can always be recognized as such.

However, there is no upper bound on how long $H$ can run for an arbitrary input $\langle M, s\rangle$. This means the results of $H$ are useful only for establishing that certain machines halt, but never for establishing that other machines *don't* halt – after all, even after running $H(\langle M, s\rangle)$ for arbitrarily long we cannot say with certainty whether $M$ does not halt on $s$, or whether $H(\langle M, s\rangle)$ just needs more time to compute. Therefore we cannot, with perfect certainty, know which TMs halt and which ones don't – but fixing a string $s$ and running $H$ on different TMs will give us a set of TMs that certainly halt on $s$ that grows the more time $H$ is given.

There is no general procedure for recognizing non-halting TMs: any putative non-halting recognizer will fail to recognize some subset of non-halting TMs as non-halting. However, there are partial recognizers for non-halting: this is the simplest to see with restricted cases of TM. For instance a TM that moves right with every state transition can be determined to never halt if it visits the same state twice after reading to the right of its input.

# Answer
> 0 votes
I think you are right.

If a program terminates, it can always be determined by running the universal TM to simulate the program trivially. If a program does not terminate, it can be determined sometimes by recognizing some special structures like infinite loop; or cannot be determined when the input is something in the part that causes HALT to be undecidable.

---
Tags: turing-machines, halting-problem, nondeterminism, semi-decidability, termination
---


# Question
Title: Way to call and explain: "potentially infinite set of attributes" in databases
This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms.

Let's say we have a database in which one entity is split into two tables: main and meta. The main table is a matrix where rows are instances (for instance each row is an order), columns are attributes (for instance order id, customer name). The meta table is a key-value store of other attributes where you'll see columns for the instance id, key, and value. Visual representation of this example below.

The thing about this structure is that it allows an instance to have an infinite number of properties, because any property of an 'order' just becomes a row in the 'meta' table.

So my question is: Is there a computer science term for 'potentially infinite set of properties'? I was thinking about 'indiscrete set', but I suspect this is not the correct way to describe this.

I am experimenting with this database structure, inspired by the Wordpress database. Also building a Laravel package that supports this structure: https://packagist.org/packages/phitech/entities. I personally think this is a practical data structure. But besides that, I feel I lack some knowledge and context to what I am actually doing. I'd like to learn this and also be able to describe it. That's why my question. This is not meant to be a discussion, which wouldn't be appropriate on SE. Just curious about your knowledge about this.

# Answer
> 2 votes
Your "potentially infinite" (I would say: finite but unbounded) list of properties is known, depending on the programming language, as an *association list, property list, dictionary, associative array*, or *hash*. No doubt other terms are in use as well; I haven't used more than some 20-30 different languages. In mathematics, it is known as a *function* or *mapping* with a finite domain.

Your idea is known as EAV (Entity-Attribute-Value model).

It is regarded with suspicion by relational database designers: use it if your set of attributes varies strongly at runtime, or if you aren't going to need to perform complex querying on your data, but be aware of losing the advantages of database normalization (value type checking, constraint checking).

---
Tags: data-structures, sets, database-theory
---


# Question
Title: A query regarding Strongly NP Complete problem reduction/definition
Given a known strongly NP Complete problem $A$. If there is a polynomial time transformation from $A$ to another problem NP Complete problem $B$ does that imply anything about if $B$ is always/automatically strongly NP complete or not?

I don't think that it is necessary that $B$ is always/automatically strongly NP Complete but some other sources seem to suggest the opposite. Thus a bit confused.

# Answer
> 2 votes
Take any strongly NP Complete problem for A and any NP Complete B for which we know a pseudo-polynomial time algorithm. Is there a poly-time reduction from A to B? (remember that B is NPC) That should answer your question.

---
Tags: complexity-theory, np-complete
---


# Question
Title: Are there some programs for which the only proof of termination, is running of the program, and waiting to see if it stops, no matter how long?
The halting problem is **semi-decidable**, which means that if a program terminates then it will always be able to be determined.

Some programs can be proven to terminate without running them, with say:

* induction
* typed theories, such as typed lambda calculus.
* Ackermann function

Are there some programs for which there is no other proof system except for the computation itself, where no properties of the program is know in advanced? And hence if so, it would make sense that some non-terminating programs, even though it can be proven to terminate *eventually*, we don't know how long that proof would take to compute, because it would not be known if the program simply needs to run for longer, because as stated above, not even the property of how long the program should run before we can determine if it should have terminated yet, is known in advanced.

Are there *some* programs for which the only proof of termination, is the actual running of the program, and waiting to see if it stops, no matter how long it takes to complete?

# Answer
> 1 votes
"Are there some programs for which there is no other proof system except for the computation itself, where no properties of the program is know in advanced?" No. For a Turing machine T and input X such that T(X) halts, there is a formal system consisting of the appropriate Turing machine axioms and the axiom "T(X) halts" that proves T(X) halts.

To really answer this question, you'd need a defined formal system and definition for computation versus other forms of proof.

# Answer
> 1 votes
Since for all programs with a set of possible inputs which are countably infinite \[except 0-arry functions i.e. constant functions\], it would not be possible even to run the program until it terminates for all inputs.

Therefor it would not even be possible to prove termination by simply running the program until it terminates.

---
Tags: turing-machines, computability, halting-problem, semi-decidability
---


# Question
Title: How are processor instructions stored in RAM?
I've recently been designing a simple 8-bit microprocessor, similar to the Intel 8008. It doesn't make use of anything advanced as pipelining, as my knowledge isn't at that level yet to know how to implement it.

The address length of 14 bits, and an instruction lengths ranging from 1 to 3 bytes.

I've been researching, and I found that instructions generally span across multiple addresses in memory. For example, a 2 byte instruction could store the opcode-byte in one address, and a one-byte data value in the following.

However, when fetching an instruction from memory, does this mean that the processor has to make up to 3 memory calls just for the fetch stage?

I.e. - loading the MAR with the PC address, incrementing the PC, and loading from memory into part of the instruction register, repeated up to three times.

Or, is there a different way to store the instructions to get around this? Just to note, my processor also doesn't use any caching, meaning it has to get instructions and data exclusively from RAM.

Also, how would this work for jump instructions? If I want to jump to a specific instruction in the program, but don't know the address in memory because of all the other multi-length instructions.

I would appreciate feedback on any of these questions.

# Answer
> 4 votes
Some processors - generally, 32-bit RISC ones - make sure that all instructions fit in one location in memory. This works for them because 32 bits is enough to fit plenty of instructions, and it makes it easy for the processor to load instructions. All the instruction operands are included as part of the instruction. The instructions are often bigger than they need to be, but the simplicity can be worth it.

8-bit processors don't do this, because you can't really fit enough instructions in only 8 bits. You can only fit 256 instructions, in fact. If they have 4-bit operands (not enough) you can only fit 16 instructions (also not enough). So multi-byte instructions are a necessity.

However, 256 is plenty of *opcodes*. In the 8-bit era it was typical that a CPU would read a 1-byte opcode, and then the operands (if any) would be in the next 1 or 2 bytes.

> I.e. - loading the MAR with the PC address, incrementing the PC, and loading from memory into part of the instruction register, repeated up to three times.

Almost. You could do this. But 8-bit CPUs generally do **not** have 3-byte instruction registers. Instead, the instructions are designed so only the opcode needs to be stored in the opcode register is needed, and the operand bytes can go directly to their final destination. An instruction like `ADD BC, 1234` might process the bytes like this:

1. load the MAR with the PC address, increment the PC, and load from memory into the opcode register
2. load the MAR with the PC address, increment the PC, load from memory into the ALU right input, load from register C into the ALU left input, set the ALU mode to ADD, store from the ALU output into register C
3. load the MAR with the PC address, increment the PC, load from memory into the ALU right input, load from register B into the ALU left input, set the ALU mode to ADC (add-with-carry), store from the ALU output into register B

To keep track of the steps, you might find it helpful to add a step counter "mini-register" which increments each cycle, except at the end of the instruction when it resets. Then you can use the opcode register and the step counter and combinational logic to select what the CPU should do in the current clock cycle. If you use a ROM chip instead of combinational logic, the contents of the ROM are called microcode.

---

For jump and call instructions specifically (with 16-bit addresses), the Z80 CPU uses an extra, hidden 16-bit register called WZ. Normally you would load 16 bits from memory into a register by loading one half, then the other half. But when you are loading into the program counter, you can't do this, because if you load the first half of the program counter then it messes up the address you load the second half from. So it loads the halves into WZ and then transfers WZ to PC.

To save having a WZ register, a different idea is to make the programmer load the address into a register, then jump to the address in the register. You can still have relative jumps (add an 8-bit value to the PC) and page-relative jumps (loading the lower 8 bits only) without needing any extra registers.

---

> Also, how would this work for jump instructions? If I want to jump to a specific instruction in the program, but don't know the address in memory because of all the other multi-length instructions

You do know the address. Each instruction has an address, and you tell the CPU to jump to the address of the instruction.

---
Tags: memory-management, cpu, memory-access, instruction-set
---


# Question
Title: Applications affected by memory performance
I'm writing a paper on the topic of applications affected more by memory performance than processor performance. I've got a lot written regarding the gap between the two, however I can't seem to find anything about the applications that might benefit more from memory performance.

I suppose these are applications that make a large amount of memory references, but I have no idea what kind of applications would make such large number of references to make it stand out?

Can you please give me any pointers on how to proceed, some links?

# Answer
> 0 votes
Performance is mostly restricted by the number of cache lines you have to read. Let's say you have 256 bit = 32 bytes cache lines: Then reading one byte from RAM takes almost as long as reading 32 bytes. So an application that reads small amounts of data from random locations takes much more time per byte.

Then the requirement is of course that your data doesn't fit into cache. So random reads of small items in a range that exceeds cache size is bad.

Next, you will often have to do address translation: You have a logical address, but your processor needs the physical address. For that you have a page table, with one entry in the page table often covering 4KB. So if each access goes into a different page, then each access needs to read a different page table entry, and if you use more page table entries than are cached, you go slower again.

So worst case are applications that access small amounts of data in a large area, at random locations far apart. And of course modifies them which takes longer again.

For example, take a two gigabyte byte array and write

```
for (j = 0; j < 65536; ++j)
    for (I = 0; I < 2000000000; I += 65536)
        array [I + j] += 1;

```

This may take two reads from RAM and one write for each access.

---
Tags: performance, memory-access
---


# Question
Title: Equivalence between Lambda Calculus [Church] and Computable Partial Functions [Godel]
In order to show that Lambda calculus and Turing machines are equivalent it is sufficient to show that you can simulate one in the other \[both ways\].

We can observe it in action. Can one do the same on general recursive functions \[ie mathematical functions as defined by Godel\]

Are there any reference reading materials?

# Answer
> 0 votes
To simulate the lambda calculus on a Turing machine, all you need to do is build an interpreter for the lambda calculus. That is easy. If you want a reference, I recommend Structure and Interpretation of Computer Programs. In general, what are describing falls within computability theory, so I recommend studying a good textbook on that subject. There are many.

---
Tags: computability, lambda-calculus, computation-models
---


# Question
Title: Reducing Vertex Cover (or Independent Set) to Vertex Cover and Independent Set at the same time
In order to show that the next problem is NP-hard:

Problem: Vertex Cover and Independent Set

Input: Graph G and integer k

Output: Does G have a vertex cover of k and an independent set of k?

The sets does not have to be complementary (just about size k). I have tried to reduce Vertex Cover but I cannot find how to ensure that when there is a vertex cover in G, the problem above outputs true and deal with the independent set of the same size k. I have thought of doing something with the fact that vertex cover is the complement of independent set but since there is the same value for k I have no idea for that.

# Answer
If you want a reduction from Vertex Cover: given $(G, k)$ an input of VC, create a graph $G'$ with a copy of $G$ and an additionnal $k$ vertices with no additionnal edge.

Then $G'$ has a vertex cover and an independant set of size $k$ if and only if $G$ has a vertex cover of size $k$.
> 0 votes

---
Tags: algorithms, graphs, np-complete, np-hard, vertex-cover
---


# Question
Title: Is it possible to determine if a 0-arity function [a program with no input] will always terminate
The halting problem concerns programs which take input. By framing the halting problem on the diagonal argument it is clear why this is so.

What about programs with no input, constant functions.

Can it always be determined if they terminate?

# Answer
No, given any program-input pair $(T,x)$ (formally a Turing machine and a word in $\Sigma^\*$ for some alphabet $\Sigma$) you can construct a Turing machine with no input that first writes down $x$ and then simulates $T$.

It follows that the problem is undecidable.
> 5 votes

---
Tags: turing-machines, computability, halting-problem, decidability
---


# Question
Title: Constructive Graph Isomorphism Algorithm Literature
I have consulted the literature concerning graph isomorphism algorithms, and all papers I could find involve finding a *canonical representation* of a graph. So to decide whether two graphs are isomorphic, you just check if they have the same canonical representation (i.e. the same equivalence class).

There is, also, an other way to proceed: try to build explicitly the isomorphism between the two graphs, and answer Yes or No depending on the success of the task. One can think, for instance, to a constructive algorithm that incrementally build a bijection, using backtracking.

I was not able to find any literature related to the second topic. I understand that canonical representation is a better idea in general, but I am quite surprised that nobody ever tried to tackle the constructive approach. Maybe it is too naive ? My question is: do you know any literature on that topic, that I could have missed ?

# Answer
> 1 votes
A canonical labeling of a graph is a labeling of the nodes. One can construct the isomorphism mapping by tracking how the nodes are labeled when computing the canonical form, and undoing the mapping with the two graphs. In particular, the labeling is usually a coloring where each node of a given color is connected to the same quantity of nodes of the same set of colors.

Given that two nodes in either graph map to the same color, then those nodes can safely be mapped to each other. Considerable detail on how these colorings are generated is provided in McKay & Piperno, *Practical graph isomorphism, II*, 2014. This coloring is also the approach taken in the relatively recent breakthrough in Babai, *Graph isomorphism in quasipolynomial time*, 2016.

That said, there are some algorithms that build mappings directly. A common algorithm in practice is the VF2 algorithm by Cordolla et al., *An improved algorithm for matching large graphs*, 2001 which computes a mapping recursively.

---
Tags: graphs, graph-isomorphism
---


# Question
Title: Number of bit string interpretations correct?
Suppose you are given a bit string $B\[1 ... n\]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-padding) bits should be inverted from $0$ to $1$ and vice versa.

According to my intuition, the total number of interpretations is $$ I(B) = \sum\_{i = 0}^n \binom{n}{i} i! 2^i. $$ The idea is that we choose all bit combinations, one by one. Then, we permute each combination. Finally, we multiply by $2^i$ in order to take the bit inversions into account.

Is this formula correct?

**Example**

$p$ as padding, meaningless bit. $b$ as non-padding, meaningful bit. $\bar{b}$ as meaningful, inverted bit.

1. $pp$
2. $pb$
3. $p\bar{b}$
4. $bp$
5. $\bar{b}p$
6. $bb^\prime$
7. $b\bar{b^\prime}$
8. $\bar{b}b^\prime$
9. $\bar{b}\bar{b^\prime}$
10. $b^\prime b$
11. $b^\prime \bar{b}$
12. $\bar{b^\prime}b$
13. $\bar{b^\prime}\bar{b}$

Note that $I(B\[1 … 2\]) = 13$.

# Answer
When there are $i$ significant bits, you can form $2^i$ arrangements that can be permuted in $i!$ ways, and interspersed each with the remaining $n-i$ bits. Hence in total

$$\sum\_{i=0}^n2^ii!\binom ni.$$

E.g., for $n=2$,

$$1\cdot1\cdot1+2\cdot1\cdot2+4\cdot2\cdot1=13.$$

This just confirms your findings.
> 2 votes

---
Tags: strings, information-theory, bit-manipulation
---


# Question
Title: How does a text file distinguish a letter and number in binary
In a text file you can write both the letter 'A' and number '65'. But obviously one of these data will be saved with different bits while the ASCII standard gives the letter 'A' the binary code for 65. Does a .txt file use some sort of container for different interpretations of binary? How does this work?

# Answer
I don't understand what you mean by container. But any file, may it be a text file, image, videos, executables, etc. are stored in binary. Now the interpretation of a file is dependent on the particular program that will read it. As for text editors, it will interpret the content based on a selected character enconding. Most text editor will try to auto detect the encoding for a given file and some might have a default expected enconding.
> 3 votes

---
Tags: binary
---


# Question
Title: Name for algorithms whose runtime only depends on the problem size?
I'm looking for the name of the family of algorithms whose exact runtime is dependent *only* on the size of the input. An example of such an algorithm would be naive $O(n^3)$ matrix multiplication. If we know $n$, we know exactly how many operations it will execute and how many cycles it will take to complete (ignore real world things like cache misses, context switching, etc.). An algorithm that would not be in that family is Quick sort ($O(n^2)$) since the number of operations is dependent on the contents of the list being sorted. Divider algorithms that only depend on the number of bits of the operands would be in this family, but Euclid's algorithm would not because it finishes faster for some numbers than others.

In other words, suppose you have the algorithm implemented in assembler and the cpu runs one instruction per cycle. Then the value of the program counter $pc(t, n)$ is a function of time $t$ and problem size $n$. The total number of cycles to compute the solution is known in advance.

# Answer
> -1 votes
ETA: adjusted to "size-based constant time algorithms". Indeed, as pointed out, constant time typically refers to constant time on all inputs. In average-case and worst-case analysis, typically the time is per size n, so in that contest the algorithms that do not change behaviour on each given size are (size-based) constant time. The traditional definition of constant time would be an "overall" constant time (for all sizes).

It is reasonable to refer to such algorithms as "(size-based) constant-time algorithms". Their worst-case and average-case time (for instance measured in number of comparisons) is the same as the constant time c\[n\] which the algorithm takes to execute on inputs of size n. This includes Bubble-Sort but not Insertion-Sort (when measuring the time as the number of comparisons executed by the algorithm on lists of fixed size n).

---
Tags: algorithms, terminology
---


# Question
Title: VC dimension of the class of polynomial classifiers of degree $n$
I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"

## The general idea is as follows:

Consider a binary classiﬁcation problem with the instance domain being $X = \mathbb R$.

For every $n \in \mathbb N$ let $H\_n$ be the class of polynomial classiﬁers of degree $n$; namely, $H\_n$ is the set of all classiﬁers of the form $h(x) = \operatorname{sign}(p(x))$, where $p\colon \mathbb R \to \mathbb R$ is a polynomial of degree $n$.

Prove that the VC dimension of $H\_n$ is $n+1$.

# Answer
> 3 votes
The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$.

On the other hand, for any set of $n+1$ pairs $(x\_1,y\_1),\ldots,(x\_{n+1},y\_{n+1})$, there is a polynomial of degree $n$ which interpolates them, given by the Lagrange interpolation formula. Using $y\_i = \pm 1$, you can easily show that *any* set of $n+1$ points is shattered. Therefore the VC dimension is exactly $n+1$.

# Answer
> 1 votes
Here is a proof (not the only one). This proof appeals to the fact that our hypothesis class is a subset of a linear hypothesis class of degree $n+1$.

Let $\cal{P}\_n$ denote the set of all d-degree polynomials $p\_n: \mathbb{R} \to \mathbb{R}$.

Define the hypothesis class as follows: $$ \cal{H}\_{P\_n} := \\{ f\_n : f\_d(x) = \textbf{sign}(p\_n(x)), \quad x \in \mathbb{R},\quad p\_n \in \cal{P}\_n \\} $$

That is, $\cal{H}\_{P\_n}$ is the set of all d-degree classifiers.

We want to show that $VC(\cal{H}\_{P\_n}) = n + 1$. We will do so in two steps.

---

**Step 1**: Show that $VC(\cal{H}\_{P\_n}) \le n + 1$.

*Proof*: In this step, we are showing that $\cal{H}\_{P\_n}$ is a subset of the class of all linear classifiers $f\_l:\mathbb{R}^{n+1} \to \mathbb{R}$.

That is, denote the class of all such linear classifiers as $\cal{H}\_{l\_{d+1}}:= \\{f\_l: f\_l(x) = \textbf{sign}(\langle w, x \rangle), \quad w, x \in \mathbb{R}^{n+1}\\}$. Take as given that $VC(\cal{H}\_{l\_{n+1}}) = n + 1$.

Then, notice we can write any polynomial $p\_n$ as a dot product between a vector of constants $c \in \mathbb{R}^{n+1}$ and a basis vector $\phi(x) :=\\{1, x, x^2, \dots, x^n\\}$, that is: $p\_d(x) = \langle w, \phi(x) \rangle$.

Then, we can see that a polynomial is a type of linear function in the space of $\phi(x)$. Hence, (and you might need to do some thinking here to convince yourself),

$$ \cal{H}\_{P\_n} \subset \cal{H}\_{l\_{n+1}} $$

Since the VC dimension of a smaller class of functions is less than or equal to the VC dimension of a greater class of functions,

$$ VC(\cal{H}\_{P\_n}) \le VC(\cal{H}\_{l\_{n+1}}) = n +1 $$

Hence, $VC(\cal{H}\_{P\_n}) \le n + 1$.

---

**Step 2**: Show that $VC(\cal{H}\_{P\_n}) \ge n + 1$.

*Proof*: The idea of this step is to show that $\cal{H}\_{P\_n}$ shatters *at least* $n + 1$ points. In order words, we want to show that we can find a set of $n+1$ points $\\{x\_1, x\_2,...,x\_{n+1}\\} \subset \mathbb{R}$ such that $\\{(f\_d(x\_1), f\_d(x\_2),\dots, f\_d(x\_{n+1}) ): f\_d\in \cal{H}\_{P\_n}\\}=\\{-1,1\\}^{n+1}$. (In other words, we can produce any possible label vector $y\in \mathbb{R}^{n+1}$, $y\_i \in \\{-1,1\\} \forall i \in \[n+1\]$, using functions from our hypothesis class $\cal{H}\_{P\_n}$).

Here, you can use Vandermonte's Matrix Theorem that says that the $(n+1)\times(n+1)$ matrix produced by making columns out of $\phi(x\_i), i \in \[n+1\]$ is invertible if and only if the $x\_i$'s are all distinct (no duplicates). Writing this explicitly:

$$ \begin{bmatrix} \phi(x\_1) & \dots & \phi(x\_{n+1})\\ \downarrow & & \downarrow \end{bmatrix} = \begin{bmatrix} 1 & 1 & \dots & 1\\ x\_1 & x\_2 & \dots & x\_{n+1}\\ x\_1^2 & x\_2^2 & \dots & x\_{n+1}^2\\ \vdots & & \dots & \vdots\\ x\_1^{n+1} & x\_2^{n+1} & \dots & x\_{n+1}^{n+1}\\ \end{bmatrix} $$

That is to say, $\phi(x\_1), \dots \phi(x\_{n+1})$ are linearly independent, and since this is a square matrix, the rows are also linearly independent. Notice that the rows represent a single polynomial function when you pass a constant vector $c \in \mathbb{R}^{n+1}$. Therefore, the rows span $\mathbb{R}^{n+1}$. That is, for any point $v \in \mathbb{R}^{n+1}$, there exists a unique solution $w\in \mathbb{R}^{n+1}$ such that $w\_0 + w\_1 x\_i + w\_2 x\_i^2 + \dots + w\_n x\_i^n = v\_i, \quad \forall i \in \[n+1\]$.

Moreover, this is true for a label vector $y \in \mathbb{R}^{n+1}$. In other words, given a set of (distinct) points $\\{x\_1,\dots, x\_{n+1}\\}$ and associated (arbitrary) labels we can find weights $w \in \mathbb{R}^{n+1}$ to create a d-degree polynomial $p\_d$ that perfectly interpolates each point $y\_i \in \\{-1,1\\}, \forall i \in \[n+1\]$.

Hence, $\cal{H}\_{P\_n}$ shatters $n+1$ points. Therefore, $VC(\cal{H}\_{P\_n}) \ge n + 1$.

---

**Step 3**: Show $VC(\cal{H}\_{P\_n}) = n + 1$.

*Proof*: By steps 1 and 2, it follows that $VC(\cal{H}\_{P\_n}) = n + 1$.

q.e.d.

---
Tags: learning-theory, vc-dimension
---


# Question
Title: How to derive selections from a series of numbers
I am sure this question has been asked, but I was unable to search for it in a manner that would give me the solution. So I will present it here.

I seen this in another database years ago, and I want to implement it in one of my apps. It is perfect:

```
Pets
1. fish
2. dog
4. cat
8. monkey
16. mice
32. snakes
64. rock

```

If someone want a fish, cat, and a pet rock, that could be stored as 69. I could never figure out how to extract the 69 to get the rock, cat and fish.

What is this method called, and what is the best way to reverse this?

# Answer
> 0 votes
This is just the regular representation of a binary number, where the no. of bits represent the no. of types of that entity(pets in this case). You simply assign each bit position a unique type and then the bit value tells you whether that type is included or not. Binary representation is suitable cause you have 2 options for each type, which can be encoded in a binary number.

```
                     +------+--------+------+--------+-----+-----+------+
                     |  2^6 |   2^5  |  2^4 |   2^3  | 2^2 | 2^1 |  2^0 |
                     +======+========+======+========+=====+=====+======+
                     | rock | snakes | mice | monkey | cat | dog | fish |
                     +------+--------+------+--------+-----+-----+------+
                     |   1  |    0   |   0  |    0   |  1  |  0  |   1  |
                     +------+--------+------+--------+-----+-----+------+
                                 1000101(base2) => 69(base10)

```

In general if you have $n$ unique choices$(0.....n-1)$, then each unique unique selection can be represented as a decimal number by $$N = \sum\_{i=0}^{n-1}b\_{i}\*2^{i}$$

where $b\_{i}$ = bit at position $i$

If from this number you want to know what that selection was you'll need to check the bits individually which can be done as follows

```
input(N)
while (N > 0) do:
    bit = N % 2 (check this bit to know the selection of each type, this checks from LSB to MSB(from fish to rock in this case))
    N = N / 2

```

---
Tags: database-theory
---


# Question
Title: Show that the the language $L = \{0^kww0^m | k,m \ge 1, w \in \{0, 1\}^*\}$ is nonregular
Caveat. You have to show this specifically by showing there exists an infinite set that is pairwise distinguishable with respect to L.

This question was on a quiz which we had 12 minutes to complete (this wasn't the only question!) I can see that this isn't a regular language but I cannot come up with any set that is pairwise distinguishable with respect to L. (No you can't use the pumping lemma). This will probably be on an exam I'm taking tomorrow so your help is greatly appreciated.

# Answer
> 0 votes
Let $$\mathcal{D}\_L := \\{ 0^j 1 0^j 1 \mid j \ge 1\\}$$ be the desired set. Clearly it is infinite. We show that a subset of the set is pairwise distinguishable with respect to the given language $L$.

For any two strings $0^i 1 0^i 1$ and $0^{i+1} 1 0^{i+1} 1, \text{ }(\text{for }i \ge 2)$ in $\mathcal{D}\_L$, we have — by appending the string $0^{i+1}$ — that $0^i 1 0^i 1 0^{i+1} \in L$ whereas $0^{i+1} 1 0^{i+1} 1 0^{i+1} \notin L$. Thus, the two strings are distinguishable. More generally, for every pair of strings $x, y \in \mathcal{D}\_L$, there is a string $z$ (appropriately chosen) such that $xz \in L \Leftrightarrow yz \notin L$.

Since we know that for a set, $\mathcal{D}\_L$, of pairwise distinguishable strings with respect to $L$, any DFA for $L$ must have at least $\vert \mathcal{D}\_L \vert$ states; and since in our case $\vert \mathcal{D}\_L \vert$ is infinite, we conclude that no DFA can decide $L$. So, it is not regular.

---
Tags: regular-languages
---


title: Quantum Turing machine

text:
# Question
Title: Quantum Turing machine
Is there a formal definition of a 'Quantum Turing machine'? I am mainly interested in how the tape position would move.

> https://en.wikipedia.org/wiki/Turing\_machine
> https://en.wikipedia.org/wiki/Quantum\_computing

# Answer
> 1 votes
Well, yes, you were almost there : https://en.wikipedia.org/wiki/Quantum\_Turing\_machine

---
Tags: turing-machines, quantum-computing
---


# Question
Title: Graph Isomorphism Problem: decisional vs functional
The Graph Isomorphism Problem is a *classic* in Computer Science.

In its *decision* version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if *there exists* an isomorphism between the two. In its *function* version $(FGI)$, we want to *produce in output* the found isomorphism (if it exists).

It is a (in)famous open problem whether $DGI$ is either in $P$, is $NP$-complete or belongs to the $NP$-intermediate class.

My question is: what do we know about its function version? Is it (polynomially) equivalent to its decision version? Clearly, $DGI \preceq\_P FGI$. What about the other direction?

Thank you.

# Answer
> 3 votes
Yes $FGI \preceq\_P DGI$ also holds. Assume you have a black box $B$ that solves $DGI$ in polynomial time. You can easily solve $FGI$ in deterministic polynomial time with polynomial many calls to $B$.

First let $K\_n$ be a clique on $n$ vertices. Let us define the function `addClique(G, v, n)` that adds to a graph $G$ a copy of $K\_n$, and makes one of its vertices adjacent to $v$ in $G$. It returns a set $S$ of the vertices of the clique. We define `remove(G, S)` that removes a set of $n$ vertices $S$ from a graph $G$. Clearly such functions can be implemented in polynomial time in the size of $G$ and $n$.

Given two graphs $G\_1, G\_2$. Fix an ordering $v\_1, \dots v\_n$ of the vertices of $G\_1$, and $w\_1, \dots w\_n$ for $G\_2$. The algorithm goes as follows:

```
iso[n] = [0,.., 0]
If not B(G1, G2):
   Return false
For each vertex vi, i in [n]:
   addClique(G1, vi, n+i)
   For each vertex uj, j in [n]:
      if iso[j] != 0:
         continue
      iso[j] = i
      S = addClique(G2, uj, n+i)
      if B(G1, G2):
         break
      iso[j] = 0
      remove(G2, S)

```

We claim that if an isomorphism exists, then this algorithm finds one, where $u\_j$ is assigned to $v\_{iso\[j\]}$. The correctness follows from the fact, that each copy of $K\_n$ in $G\_2$ can only be assigned to a unique well-defined copy of $K\_n$ in $G\_1$. The polynomial bound follows from the fact that we add at most $n$ cliques of size at most $2n$ to each of the graphs.

Try to prove these claims as a homework!

---
Tags: complexity-theory, graphs, reductions, decision-problem
---


# Question
Title: Using Data Compression on the output of Data Compression
**Context:**

*Lossless Data compression* (source coding) algorithms heavily rely on repetitive pattern (redundancy)

**Questions**

Is there a data compression method/algorithm that uses another *data compression* on the compressed data obtained so far?
If such a method exists, what are its limits?

# Answer
> 4 votes
When we compress something the output is smaller than input (that is the purpose of compression, otherwise we do not use it or cope with bigger file). This can be achieved by various methods including (but not limited to) matching of substrings (dictionary compression) or frequency of characters (entropy compression, like Huffman encoding) or arithmetic coding (like MTF, Elias etc.).
Some methods like (Bijective) Burrows Wheeler Transform does not compress, just change the order of characters so other methods might benefit from local similarity of characters, so it is used in conjunction with other techniques.

If we try to apply dictionary method or entropy method twice (or more times) there are no benefits at all, we already exploited the redundancy of data. Using methods with chunks of data twice will give us the issue of compressing the packed data and the header (dictionary, frame, characters etc.), so it is harder task than one we started with and the most benefitial would be changing frame size or make it addaptive (but not applying the same method more times).

Encryption is not concerned about file size - it secures data with key so that any person obtaining the file without the key will have very hard time opening it. If the quality of encryption is useable the resulting file has no obvious dependencies or visible redundancy. Encrypted files are not compressible. Now encrypting chunks several times will not add any security and will not compress file.

Please keep in mind that methods like Cezar, Rot13 and xor of key (cyclic) with data are not encryption methods, and even if they were, cyclic shift of characters (mod 256) will not change compression.

About limits - when we compress something then we have to encode header, dictionary etc., so our output file is transformed input plus additional information about it, which is commonly short and not compressible, so every time we put output of compression into input of another one we have a bit more to deal with and some *redundancies* were already used, this is one limit.
The second limit is that we cannot compress anything in the mean sense, taking all possible inputs of given size, compressing and calculating the mean shows that we in fact ended with more data than we started with. At the best (unlikely) case we end up with the same amount of data. This comes from the fact that contraction of data with better result is not unique anymore so we cannot decompress it uniquely to original.

# Answer
> 2 votes
Sometimes the best thing you can do is a little experiment:

```
$ dd if=/dev/zero of=zero.000 bs=1024 count=100
100+0 Datensätze ein
100+0 Datensätze aus
102400 Bytes (102 kB) kopiert, 0,00106735 s, 95,9 MB/s
$ cat zero.000| wc -c
102400
$ cat zero.000 | gzip | wc -c
133
$ cat zero.000 | gzip | gzip | wc -c
58
$ cat zero.000 | gzip | gzip | gzip| wc -c
81

```

So assuming that `gzip` implements a compression algorithm (most people would say it does), we have evidence that at least *sometimes* running a compression algorithm a second time can improve the compression.

Of course the file I've used here is very special (all bytes zero), and it is unlikely that anyone normally would try to compress this file.

# Answer
> 1 votes
Lossless compression algorithms, on average, increase the size of the file.

This is another realisation of the pigeons and the holes problem: there are $2^x$ possible messages of $x$ bits, and storing them all takes $x 2^x$. Now, if we come up with a compression algorithm that reduces one of them in 3 bits, you'll have to pay the price with another message. So, in the ideal case, all the messages will take the same amount of space. In practice, due to bookkeeping and other factors, this is increased.

In practice we aren't concerned with compressing random streams of data: real data has some structure that can be exploited, and we pay the price in "unrealistic messages". The output of a compression algorithm doesn't look anything like a "natural input", and so, it is likely to fall into the "unrealistic messages" basket. This is true even when for more powerful methods: feeding the output of gzip (DEFLATE) to a more powerful compressor, like xz (LZMA), will increase its size, and in some occasions, make it bigger than the original.

After all, if the output of a compression algorithm were likely to have certain kind of compressible patterns, the authors would have added it to the process, perhaps as an optional second pass.

# Answer
> 1 votes
There are a few potential ways to approach this question. One way would be to use a data compression algorithm on the output of another data compression algorithm. This can be done by taking the output of one data compression algorithm and compressing it with a second data compression algorithm.

Another way to compress the output of a data compression algorithm is to use a different type of data compression algorithm. For example, you could use a Huffman code or an arithmetic code on the output of a Run-Length Encoding (RLE) compressor. This approach can often result in smaller file sizes than using the same type of compressor twice.

---
Tags: algorithms, information-theory, data-compression, coding-theory
---


# Question
Title: What are some examples of proofs that are also themselves "useful" programs?
With dependent types, types can be statements that are true or false and constructing a value with that type constitutes a proof of that statement. This proof/value construction is itself a program that can be run (which I think encapsulates the Curry-Howard Equivalence idea), but often these programs are not very "useful". For example, consider the following type statement:

```
(Π ((n Nat))
  (= Nat (sum_of_first_n_nat n) (n*(n+1)/2))
)

```

Which claims that for all natural numbers, some primitive-recursive function `sum_of_first_n_nat` will always give the same answer as that closed-form formula for finding the sum of the first `n` natural numbers. A proof of this would probably use induction and, although *would* likely also yield the actual answer when given a concrete `n` value, would compute it somewhat inefficiently - iterating over all the natural numbers up to `n` instead of using the closed form solution.

Are there any well-known examples of dependent-type proofs that are themselves useful programs? Of the sorts of statements that humans would like to prove when writing programs, what proportion could likely be given "useful" proofs? Is it often possible to make a proof "useful" given sufficient creativity and effort, or is this highly dependent on what the statement is? Is having all proofs be useful a desirable goal when writing a dependently-typed program?

# Answer
Many constructive proofs could be useful. For example, to prove that every set of points in the plane (in general position) have a Delaunay triangulation, you would give the algorithm for producing the Delaunay triangulation, along with a proof that the result of the algorithm satisfies the desired properties. In pseudo-code the type signature of this proof might look like:

```
points-in-general-position -> (triangulation-of-those-points, proof-that-this-is-a-Delaunay-triangulation)

```

So just using the first value in the output pair would give you the desired value. Though another way to phrase this would make the proof 'useless': you could first write the algorithm as one function and then prove a proposition that the result of the algorithm is always a Delaunay triangulation. This separates out the useful computation part from the proof part.

Another example would be proving that a set with some binary operator is a group. If done constructively, that would involve giving an explicit algorithm for the inverse of any element, which may be quite nontrivial.
> 3 votes

# Answer
I guess it largely depends on how you define "useful"?

Here is a proof of a sorting algorithm: https://blog.adacore.com/i-cant-believe-that-i-can-prove-that-it-can-sort
> -2 votes

---
Tags: dependent-types, curry-howard
---


# Question
Title: Universal class $\mathcal{H}_{p, m}$ of hash functions has $p(p-1)$ members
In CLRS it is stated that the class $\mathcal{H}\_{p, m} = \\{ h\_{ab}:\mathbf{Z}\_p \to \mathbf{Z}\_m \mid a \in \mathbf{Z}\_p^\*, b \in \mathbf{Z}\_p\\}$, $h\_{ab}(x) = (ax+b) \mod p \mod m$, $m \< p$ prime has $p(p-1)$ members. However, I don't see why some of these functions couldn't turn out to be the same. I've investigated on my own, and found that keeping $b$ fixed, all $a \in \mathbf{Z}\_p^\*$ do indeed give different functions; I take $b = 0$ and then show that if $h\_{a0}^{-1}(m\mathbf{Z} \cap \mathbf{Z}\_p) = \\{x, 2x, \ldots, rx\\}$ and $h\_{a'0}^{-1}(m\mathbf{Z} \cap \mathbf{Z}\_p) = \\{y, 2y, \ldots, ry\\}$, $r = \lfloor p/m \rfloor$, then since $r \< p/2$ and $\mathbf{Z}\_p = \\{x, 2x, \ldots, rx, (r+1)x, \ldots, px\\}$, writing $cx = y$ we'll have some $d$ with $dcx = dy \notin \\{x, 2x, \ldots, rx\\}$, i.e. sets $\\{x, 2x, \ldots, rx\\}$ and $\\{y, 2y, \ldots, ry\\}$ are different, i.e. $h\_{a'0} \neq h\_{b'0}$. (I apologize for messy shorthand.)

But I have no idea how to extend this to arbitrary $(a, b)$ and $(a', b')$, and somewhat doubt if it's worth it. (Maybe there's a simpler way of looking at this?) Nonetheless I intensely dislike the feeling of having to take such things on faith, and there's maybe something elementary that i'm missing, so I'm asking for help.

# Answer
The claim is false in general. If $p=3$ and $m=2$, there are only 3 such functions, as can be found by enumeration. For instance, $h\_{1,2}(x) = h\_{2,0}(x)$ for all $x$.

It seems very plausible to me that there might exist some constant $c\_0$ such that the claim is true for all $p\>m\>c\_0$. I doubt there's a simple proof. Heuristically, we can expect this to be true. There are $m^p$ functions with the signature $\mathbf{Z}\_p \to \mathbf{Z}\_m$, and $p(p-1)$ choices of $a,b$, so by a birthday paradox style argument, if we heuristically model each function $x \mapsto (ax+b) \bmod p \bmod m$ as a random function with signature $\mathbf{Z}\_p \to \mathbf{Z}\_m$, then the probability of there existing any collision (any pair of such functions that are identical) is exponentially small once $m$ is large enough. In particular, the probability they are all different is (under this assumption) about

$$p \approx \exp\\{-p^2(p-1)^2/(2 \cdot m^p)\\},$$

which when $p \ll m^{p/4}$ is about

$$p \approx 1 - {p^2(p-1)^2 \over 2 \cdot m^p}.$$

This is exponentially close to 1, once $m$ is large enough. This is not a proof, this is just a heuristic, as it treats each function as a random function (uniformly distributed across all possible functions of that signature), which is in reality not correct.

I doubt it matters much whether there are exactly $p(p-1)$ such functions or not.

I do want to validate your reactions of dislike having to take things on faith, and your failure to find find a simple way to prove such a claim.
> 1 votes

---
Tags: discrete-mathematics, hashing, modular-arithmetic
---


# Question
Title: Finding number of combinations of numbers from multiple arrays that add up to a given value
Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum is $ s $. In set theory terms, if I have $ n $ tuples, $ A\_1, A\_2, \ldots A\_n $, I want to find all $ (a\_1, a\_2, \ldots, a\_n) \in \times\_{k=1}^{n} A\_k$ such that $ sum((a\_1, a\_2, \ldots, a\_2)) = s $. I tried to do so by first finding the cartesian product of all the arrays, and then iterating every combination and checking its sum. The problem is that even if I have only $ 10 $ arrays with $ 10 $ elements each, the cartesian product's length would be $ 10000000000 $, which could even be too much for the browser (I'm writing it in the browser with JS) to handle, and I would have to do $ 10000000000 $ iterations, not including iterating every combination. Is there any known and more efficient algorithm for this problem?

# Answer
The problem is NP-hard. As @AspiringMat explains, even to determine whether there exists any solution at all is as hard as the partition problem: given an instance of two-partition with numbers $x\_1,\dots,x\_n$, let the $i$th array contain $0$ and $x\_i$, set $s=(x\_1+\dots+x\_n)/2$, and test whether there exists any solution to your problem. Counting the number of solutions is at least as hard as determining whether there is any solution or not.

As a result, you can't expect any algorithm that will be efficient and work for all possible inputs. Instead, you'll need to consider standard methods for dealing with intractable problems, such as focusing on a particular subset of problem instances (e.g., specify the typical size of $n$, $s$, and the integers in the arrays), or accept an exponential-time algorithm.

You can study algorithms for the subset sum problem. Some of them can be adapted to your problem -- though they might take exponential time.

The problem statement is not clear about whether you want to count how many solutions exist, or to list them all. I am assuming above that you want to count the number of solutions. If you want to list them all, this can take exponential time in the worst case, as there can be exponentially many solutions (consider, e.g., the case where each array contains 0 and 1, and where $s \approx n/2$).
> 1 votes

---
Tags: algorithms, arrays, efficiency, knapsack-problems, subset-sum
---


# Question
Title: Find the language generated by the Context Free Grammar
I am trying to find the language generated by this context-free grammar

```
S → aSb | bbY | Yaa
Y → bY | aY | ε

```

I understand that one way to solve is this to find set of strings that satisfies this grammar, But I don't see a common pattern in those strings.

Some of the strings that belong to this language are

```
     aa,bb
     aaa, bbb, bba, baa,
     abbb, aaab, baaa

```

# Answer
> 1 votes
The generation of strings by this context-free grammar can be split into four stages.

At each stage, we can use some expressions to represent all sentential forms that can be generated so far. As long as you can understand/manipulate them consistently, you are good to go.

1. Apply $S \to aSb$ zero or more times.
We get $S\Rightarrow^\*a^kSb^k$ for $k\ge0$.
2. Apply $S\to bbY$ or $S \to Yaa$ once.
We get $a^kSb^k\Rightarrow a^kbbYb^k$ or $a^kSb^k\Rightarrow a^kYaab^k$.
3. Apply $Y\to bY$ or $Y\to aY$ zero or more times.
We get $a^kbbYb^k\Rightarrow^\*a^kbb(a+b)^\*Yb^k$ or $a^kYaab^k\Rightarrow^\* a^k(a+b)^\*Yaab^k$.
4. Apply $Y\to \varepsilon$.
We get $a^kbb(a+b)^\*b^k$ or $a^k(a+b)^\*aab^k$.

In the end we get $a^kbb(a+b)^\*b^k + a^k(a+b)^\*aab^k$. (This is not a regular expression. I have not defined formally the meaning of such an expression. It is believed that an ordinary reader can interpret it correctly naturally.)

In plain English, a word is generated by this grammar iff its alphabet is $\\{a,b\\}$ and there exist $k\ge0$ such that it

* starts with $k$ $a$'s and ends $k$ $b$'s and,
* ignoring those $2k$ symbols, either starts with $bb$ or ends with $aa$.

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


# Question
Title: Bounded waiting and starvation free in critical section problem
I have 4 questions regarding relation between starvation and bounded waiting.

1.Does starvation-freedom imply deadlock-freedom?

My Answer:

From here,

definition of starvation free is

> **Freedom from Starvation** -:Every thread that attempts to acquire the lock eventually succeeds

> **Freedom from Deadlock** -:for some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.

So, I can state that **starvation-freedom imply deadlock-freedom**

2.Does starvation-freedom imply bounded-waiting?

Approach-:

> Starvation free implies that every thread that will attempt to acquire lock will succeed.

On the other hand

> Bounded wait insures that there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

**Which implies that there must not be any starvation.**

Am i correct? But the explanation is here confuses me.

# Answer
No, starvation-free doesn't imply bounded waiting.

For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long. Then there is no bound on the amount of time it might take to complete its operation.

Here is another example of how it can fail. Starvation-free means that every attempt to acquire the lock *eventually* succeeds -- but that says nothing about how long it might take. Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock. Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.
> 4 votes

# Answer
> so i can state that starvation-freedom imply deadlock-freedom

If you find this statement difficult, you can convert it to its contrapositive statement which is **Deadlock implies starvation**. It is easier to observe this statement is true. Hence starvation freedom implies deadlock freedom is also true.

> For Bounded wait there must not be starvation

This statement is false. See this example:-

```
flag[0]=flag[1]=false;
i=j-1;
while(1){
    flag[i]=true;
    while(flag[j]);
    //  critical section
    flag[i]=false;
    //  remainder section
}

```

At line no. 5 both processes may get stuck forever causing deadlock( and hence starvation also). But bounded waiting will be ensured because maximum number of times process i can enter the critical section before process j is allowed to enter the critical section is zero.
> 0 votes

# Answer
**Refer**: http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

1. Does starvation-freedom imply deadlock-freedom? **Yes**. Since starvation-freedom says a process will eventually enter its CS, all processes will enter their CS. So, no two processes are deadlocked.
2. Does starvation-freedom imply bounded-waiting? **No**. starvation-freedom does not put a bound. So, though each process will enter its CS, one process may get more than bounded turns to enter its CS before another process enters its CS, hence breaking the bounded-waiting requirement
> 0 votes

---
Tags: operating-systems, synchronization, deadlocks, critical-section
---


title: Regular Expression Equality

text:
# Question
Title: Regular Expression Equality
I am wondering about this small question, why aren't these regular expressions equal?

$(a+b)^\* a^\*$ and $(a^\* b)^\* a^\*$

# Answer
A regular expression is defined by a syntax: it means that a regular expression is a sequence of symbols following certain rules.

If two regular expression have different symbols, they are different.

However, it is natural to define a semantic, or interpretation, associated to regular expression. The interpretation is sometimes denoted as $\mathcal{L}(e)$ for a regular expression $e$.

While $(a+b)^\*a^\* \neq (a^\*b)^\*a^\*$ because the sequences of symbols are differents, their interpretations are equal: $\mathcal{L}((a+b)^\*a^\*) = \mathcal{L}((a^\*b)^\*a^\*) = \\{a,b\\}^\*$.

It is common when there are no ambiguity to omit the interpretation symbol $\mathcal{L}$ and to consider a regular expression as a language, but it is an abuse of notation.
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: Why can't we have P=NP but P not contained in NP-hard?
Why isn't it possible to have P=NP, but not all problems in P are in NP-hard? The diagram of the various classes would look something like:

We have P=NP, but not all problems in P lie inside NP-hard. The intersection of P and NP-hard is still NP-complete.

Lander's theorem seemed relevant, but it holds when P != NP while my proposed scenario is for P=NP.

# Answer
NP-hardness is technically defined in terms of Karp reduction, in which the answer to the target problem must be the answer to the source problem, and not in terms of Cook reduction, in which the target problem is used as an oracle. This means that the empty language and the language of all words aren't in NP-hard even if P=NP.

Excluding those trivial cases, every problem in P is polynomial-time reducible to every other problem in P, so if P=NP then every problem in NP is polynomial-time reducible to every problem in P (except those two), i.e., every problem in P (except those two) is NP-hard.
> 1 votes

# Answer
Whether or not P is equal to NP, it is definitely not the case that P is a subset of NP-hard. This is because we know that $\emptyset$ and $\Sigma^\*$ belong to P, but are not NP-hard.
> 2 votes

---
Tags: complexity-theory, np-hard
---


title: DFA and NFA Equivalence Proof

text:
# Question
Title: DFA and NFA Equivalence Proof
I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for example, "For any DFA, there is an equivalent NFA," how different would the NFA -\> DFA proof be to the DFA -\> NFA proof? Or is it basically the same thing?

# Answer
The proof would be trivial: all DFAs are also NFAs.

If you somehow insist in proving that for every DFA there exists an equivalent NFA that is not also a DFA, then it suffices to add a new initial state $q$ along with an $\varepsilon$-transition from $q$ to the old initial state.
> 2 votes

# Answer
Every DFA is an NFA by definition, so you only need to prove that for every NFA there exists an equivalent DFA.
> 2 votes

---
Tags: automata, finite-automata, nondeterminism, proof-assistants, automated-theorem-proving
---


title: Is SAT an existential question?

text:
# Question
Title: Is SAT an existential question?
Some sources state that an algorithm that solves the SAT problem not only needs to decide whether a given existentially-quantified formula is satisfiable or not, but, additionally, in the case where the formula is satisfiable, it does need to provide a satisfying assignment. Is this true or not?

I am bit confused, since I thought the SAT problem would just be an existential question.

# Answer
> 22 votes
The SAT problem is a **decision** problem. It means that an algorithm that solves SAT must answer `true` or `false`, and not necessarily find a satisfying assignment.

However, as many decision problems, there is a **functional** problem associated to SAT, that asks to find a satisfying assignment when there exists one.

There is a polynomial time reduction from the functional problem to the decision problem. Check here to see what it looks like.

# Answer
> 12 votes
If you have variables x1 to xn, and you decide in polynomial time whether the problem can be satisfied or not, then if it can be satisfied, you set x1 = true and check if it can still be satisfied. If not you set x1 = false, which can be satisfied.

Then you set x2 = true, and if that cannot be satisfied you set x2 = false. And so on, and so on. So if SAT could be solved in polynomial time, you could find a solution in polynomial time quite easily. A similar approach could be used for TSP, for example.

---
Tags: satisfiability, decision-problem
---


# Question
Title: The smallest periods of the prefixes of the Fibonacci word
I'll start with some definitions to simplify the rest of the message.

Let's denote $f\_0 = b, \ f\_1 = a, \ f\_n = f\_{n-1} \cdot f\_{n-2}$, where $\cdot$ stands for concatenation of two words. We call $f\_n$ the $n$-th Fibonacci word. Let's also denote $f := \lim\_{n \to \infty} f\_n$ (the Fibonacci word). Let $s\_{k}$ be the subword of $f$ consisting of the first $k$ letters of it. Let $w(k)$ be the $k$-th letter of a word $w$. Let $\mathrm{per}(k)$ stand for the smallest positive number such that $$ \forall i \in \\{ 1, \ldots, k - \mathrm{per}(k) \\}. \ s\_{k}(i) = s\_{k}(i + \mathrm{per}(k)) $$ In other words, $\mathrm{per}(k)$ is the smallest period in the word $s\_{k}$.

During one of my lectures, my lecturer mentioned an interesting property of the Fibonacci words. If we look at the sequence $(\mathrm{per}(k))\_{k \in \mathbb{Z}\_{+}}$, it looks like this $$ (1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, \ldots) $$ So, one $1$, two $2$s, three $3$s, five $5$s, and so on. It is the non-decreasing sequence consisting of Fibonacci numbers where the number $F\_n$ appears exactly $F\_n$ times.

I've been trying to prove it today, but with little success. I'll be glad for any kind of help – a proof, some hints, remarks, pretty much anything. I'll list what I've managed to show below:

### The smallest period of $f\_k$ is $F\_{k-1}$

I proved it inductively: the basis is obvious – we do it by hand. Then we make the induction step: let's look at $f\_n$ and let $p$ be the smallest period in it. It's obvious $F\_{n-1}$ is a period in that word. We also know that anything smaller than $F\_{n-2}$ cannot be a period because then it would be a period in $f\_{n-1}$ too and we'd get a contradiction. Thus, $p \in \[F\_{n-2}, F\_{n-1}\]$.

To show $p$ cannot be equal to $F\_{n-2}$ it's sufficient to compare the last letters of $f\_{n-1}$ and $f\_{n-2}$ – they're different, so $p \neq F\_{n-2}$. Thus $p \in (F\_{n-2}, F\_{n-1}\]$.

Let's assume $p \in (F\_{n-2}, F\_{n-1})$. Note that $f\_n = f\_{n-3}f\_{n-4}f\_{n-3}f\_{n-2}$. We'll focus on the subword $f\_{n-4}f\_{n-3}f\_{n-2}$. Note that $\lvert f\_{n-4}f\_{n-3} \rvert = \lvert f\_{n-2} \rvert = F\_{n-2}$. It's easy to also show that $f\_{n-4}f\_{n-3}$ is equal to $f\_{n-2}$ except for the last two characters (which are swapped). So the prefix of $f\_{n-4}f\_{n-3}$ of length $F\_{n-2} - 2$ is a prefix of $f\_{n-2}$. Let's denote $w := f\_{n-4}f\_{n-3}f\_{n-2}$. Using that and the periodicity, we have $$ \forall i \in \\{ 1, \ldots, 2F\_{n-2} - p \\}. \ w(i) = w(i + p) $$ and $$ \forall i \in \\{ 1, \ldots, F\_{n-2} - 2 \\}. \ w(i) = w(i + F\_{n-2}) $$ Thus, after denoting $p^{\prime} := p - F\_{n-2}$, $$ \forall i \in \\{ 1, \ldots, F\_{n-2} - p^{\prime} \\}. \ f\_{n-2}(i) = f\_{n-2}(i + p^{\prime}) $$ Note that $p^{\prime} \< F\_{n-1} - F\_{n-2} = F\_{n-3}$ and it's a period in $f\_{n-2}$. We get a contradiction because we assumed (as part of the induction proof) that the smallest period in $f\_{n-2}$ is $F\_{n-3}$. Thus $p = F\_{n-1}$. $\Box$

PS I was reminded in my other post that I should provide the source of what I post on this forum. However, it's impossible for me to refer you to the exact place where you could find this problem as you don't have access to it, but for completeness, this is the course (in Polish) I'm taking and where I came across it.

# Answer
> 2 votes
What we need to prove are

* the smallest period for $s\_1$ is 1, which is trivially true.
* the smallest period for $s\_i$ is $F\_{k-1}$ for all $F\_k-1\le i\le F\_{k+1}-2$, where $k\ge3$.

---

Let $k\ge3$.

You have proved that the smallest period of $f\_k=s\_{F\_k}$ is $F\_{k-1}$.

* The smallest period of any string cannot be smaller than that of a prefix of itself.
* $f\_{k+1}=f\_{k-1}f\_{k-2}f\_{k-1}$. Since the suffix $f\_{k-2}f\_{k-1}$ is the same as the prefix $f\_{k-1}f\_{k-2}$ except the last two characters, $|f\_{k-1}|$ is a period of $f\_{k+1}$ without last two characters. That is, $F\_{k-1}$ is a period of $s\_{F\_{k+1}-2}$. Hence for any $i\le F\_{k+1}-2$, the smallest period of $s\_i$ is at most $F\_{k-1}$.

So, the smallest period for $s\_i$ is $F\_{k-1}$ for all $F\_k\le i\le F\_{k+1}-2$, where $k\ge3$.

Looking closely, we can see that you have also proved the smallest period of $s\_{F\_k-1}$ is $F\_{k-1}$. $\quad\Box$

---
Tags: combinatorics, strings, substrings, word-combinatorics
---


# Question
Title: Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular
Let $L$ a language over $X = \\{a\\}$ defined as follow :

$$L = \\{ a^{n!} \ | \ n \geq 0 \\}$$

I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I found nothing. If it's a duplicate, I apologize and I'll be glad if you provide me the link of the duplicated question.

I'll show here what I have done, using the pumping lemma.

---

Suppose that $L$ is regular, let $n \in \mathbb{N}^\*$ and $\omega = a^{n!}$. We have $\omega \in L$ and $|\omega| \geq n$. Thus, there exist $x, y, z \in X$ so as :

1. $a^{n!} = xyz$
2. $y \neq \epsilon$
3. $|xy| \leq n$
4. $xy^kz \in L, \quad \forall k \geq 0$

Because of fact 3, $xy = a^k$ and $y = a^j$ with $k \leq n$ and $1 \leq j \leq n$. Thus :

$$a^{n!} = a^{k - j}.a^{j}.a^{n! - k}$$

By fact 4, we must have $a^{k - j}.a^{n! - k} = a^{n! - j} \in L$.

In addition, because $1 \leq j \leq n$, the following is true :

$$n! - n \leq n! - j \lneq n!$$

The final result that I need is that $(n - 1)! \lneq n! - n$. Using this I can deduce :

$$(n - 1)! \lneq n! - j \lneq n!$$

Showing that $n! - j$ can't be the factorial of an integer, giving the contradiction $a^{n! - j} \notin L$. I have tried to prove the final result, but I didn't succeed. It is not true for the first values of $n$, I have tried to consider multiple cases but went for nothing.

So I ask for your advice, maybe I am going wrong and didn't applied the pumping lemma with a word that leads to contradiction.

# Answer
> 1 votes
The easiest way is probably to use the pumping lemma on the complement language $\overline{L} = \\{ a^m : m \neq n! \\}$. Suppose that $L$ were regular. Than $\overline{L}$ would be regular. According to the pumping lemma, there is a pumping length $p$ such that every word $w$ of length at least $p$ in $\overline{L}$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in \overline{L}$ for all $i \geq 0$. Take $w = a^{p\cdot p!} \in \overline{L}$ (without loss of generality, $p \> 1$). Suppose that the decomposition is $w=xyz$, where $y=a^t$. Since $t \leq p$, it follows that $t \mid p!$. But then $xy^{1+p!/t}z = a^{p\cdot p! + p!} = a^{(p+1)!} \notin \overline{L}$.

# Answer
> 0 votes
It is a little confusing that you seem to have used $k$ in two different ways. First in the pumping lemma $xy^kz$, then to fix the length of $xy$.

Rather than trying to prove that deleting $y$ from the string $\omega$ (pumping with $k=0$) will give a string outside the language, perhaps it is easier to add a copy of $y$ (pumping with $k=2$).

$n!+j \le n!+n \< n!(n+1)$

# Answer
> 0 votes
i can't comment as i haven't yet touched the benchmark of 50 reputations.

I would like to make your work a bit clearer.You have used 3 variables although even 2 are sufficient .

a^n! let n=m ,

now consider this, |w|=|xz|+i|y|

also , m! has two parts k! = |xz| and j = i.|y|

now we know j\<=m , considering m is not \< 3 (smaller than 3)

m!-j=k! (it is needed to make sure xz exists )

now , the same thing ,

it is impossible for it to exist,

as n!-j \>= n!-n \> (n-1)! (how did it happen ? see below)

n!-n = n(n-1)!-n = n((n-1)!-1) \> (n-1)!

therefore it's not regular .

alternative way to check identify RL is : (credits to Seemona A for this short algo )

1. 1.If given language is finite =\> Regular
2. If language is infinite: Language over one symbol : Forms AP =\> Regular ; Doesn't form AP =\> Not Regular ;; Language over more than one symbol : No dependency =\> Regular; Dependency =\> Not Regular;;

another logic is L(G)+{a^n! , n\>=0} has set of elements which are not periodic in nature . a grammar on single variable is CFG if it is RegG

And a grammar is RegG iff there is a periodic nature in the set of elements of its language.

similarly if we try for CFL(context free) , we can substitute (p+r) and still the logic will be same as the string to be pumped are v= a^p and y= a^r . Logic will remain the same

https://qr.ae/pvVy55 , user named "Seemona A" has nicely concluded in short (it's a "quora" site link , a general QnA networking site).

https://john.cs.olemiss.edu/~hcc/csci311/notes/ (here you can also find it in regular expression section...... Ole Miss is University of Mississippi )

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Derivation of fraction of time when system has k requests
I was going through *Distributed Systems* by *Maarten van Steen & Andrew S. Tanenbaum*. While going through size scalability of systems, I came across this in a note.

I want to know the derivation of this formula. Also, for $\left ( 1 -\frac{\lambda }{\mu} \right )$ to be greater than zero, $\lambda$ should be less than $\mu$. That means system rate of processing requests is faster than request arrival rate, then how come requests would accumulate at any moment? Even if the system starts processing after the first request arrives and meanwhile second request is already being buffered, the system would finish processing the first request before the second request completes arrival. So no request would remain in buffer then.

# Answer
> 1 votes
It took some time but I finally found how to derive the above equation. This thing requires the knowledge of continuous Markov chains. I learned about them from these two videos which was enough to understand the concept.

Now the derivation is here on Wikipedia. Basically, our system is an M/M/1 queue and can be modeled as in the following pic.

Each number represents the number of processes in the system. The rate matrix is written as follows.

$$ Q = \begin{pmatrix} -\lambda & \lambda & & & & \\ \mu & -(\mu+\lambda) & \lambda & & & \\ & \mu & -(\mu+\lambda) & \lambda & & \\ & & \mu & -(\mu+\lambda) & \lambda & \\ & & & & \ddots & \end{pmatrix} $$ In steady state *($Q \pi = 0$, where $\pi$ is just the probability distribution $P\_{0}, P\_{1}, P\_{2}, \ldots$)*, the equations are $$ \begin{eqnarray\*} \mu P\_{1} &=& \lambda P\_{0} \\ \lambda P\_{0} + \mu P\_{2} &=& (\lambda + \mu) P\_{1} \\ \lambda P\_{n-1} + \mu P\_{n+1} &=& (\lambda + \mu) P\_{n} \end{eqnarray\*} $$ which gives $$ P\_{n} = \frac{\lambda}{\mu} P\_{n-1},\quad\text{$n=1,2,...$} $$ and the fact that system is going to be in any one of the following states at any moment of time leads to $$ P\_{0} + P\_{1} + P\_{2} + \ldots = 1 $$ So, finally we have $$ P\_{n} = \rho^{n}(1-\rho) $$ where $\rho = \cfrac{\lambda}{\mu}$ in steady state.

# Answer
> 1 votes
I have to admit that this is pretty unintuitive. I calculated many equations today, not reaching any formula close to what it says in the book. However, I managed to get my hands on the book and a few other resources, and with a little digging, I found something that might help you.

Let's look at the equation from a statistics point of view. Let's say that the *mean* rate of request arrival is $\lambda$ and the *mean* process calculation rate is $\mu$. Now you can argue that the probability that you find a certain process in the system itself is $\frac{\lambda}{\mu}$.
Hence, the probability of finding $k$ processes in the system is equal to $$ \Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ But at any given time, there are packages arriving in the system and packages going out of the system. So at the interval that we are interested in viewing the system, no new packages should be found in the system. The probability of that equals $(1-\frac{\lambda}{\mu})$. Putting everything together we get the formula: $$ p\_k = \Bigl(1-\frac{\lambda}{\mu}\Bigr)\Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ This is actually equal to the probability of finding exactly $k$ packages in the system.

*I'll keep digging and update the answer if anything new comes up*.

---
Tags: distributed-systems
---


# Question
Title: Probabilistic methods for undecidable problem
An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic approaches (in the following sense below) that solve such problems.

**By a probabilistic approach, I mean a nondetermistic algorithm such that for each input it outputs in finite time and the answer is correct with probability strictly larger than $50\\%$.** In other words, it is similar to PP but I do not require polynomial time (shall I call it "FiniteP", or it has a name already in complexity theory?). Please do not confuse this with a nondetermistic algorithm that performs probabilistically, but still tries to find a definite answer before halting.

# Answer
So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we demand that the probability of getting the correct answer is greater than 0.5.

First let us observe that because $2^\omega$ is compact, we can move from "For every sequence of coin tosses there is a finite time $t$ where $M$ halts" to "There is a finite time $t$ such that $M$ halts by time $t$ regardless of the coin outcome". This in turn means that for each input to $M$, there are only finitely many (no more than $2^t$) many computation pathes that are possible.

A deterministic machine $N$ can simulate what $M$ would do for each of the finitely many coin results. As more than half of these return the correct answer, a simple majority vote suffices for $N$ to figure it out.

So your class FiniteP consists of exactly the decidable problems.
> 19 votes

# Answer
What do you mean by randomness on *nondeterministic* TM? I think such a NTM with correct probability $\geq 2/3$ should be in PH by Sipser-Lautemann, and with probability 50% it's like something related with #P and NP (maybe $\sf \\#P^{NP}$?). I guess it cannot solve undecidable problems since nondeterminism and randomness are both some weakened version of counting, which is still "in the control of decidability". (i.e., you can use some DTM to simulate their behavior, though the time complexity maybe super huge like super-super-exponential. But it's still a DTM with finite amount of time anyway. It's a valid decider.)
> 2 votes

# Answer
Yes, and it includes the Halting Problem, but it's not very useful.

The solution to the Halting problem is known in the particular case of the program that ends immediately. Actually there are arbitrarily many programs that are known to halt; for example all programs with no looping instructions.

So suppose we write the following program: "If the input program obviously halts according to one or more quick tests, return True. If not, return a coin flip." The coin flip gets 50% of the non trivial cases (which are the vast majority), and the reasoned test gets 100% of of the trivial cases. By simple arithmetic, the routine as a whole will "solve" the halting problem strictly more successfully than 50%. Such a construction works for any problem for which there are any decidable special cases.

The reason that this is not very useful is that the randomness doesn't actually add any information, and so it doesn't stack informatively. When we talk about probabilistic algorithms we either expect that independent runs of the routine give independent answers which are each more reliable than not. The notion is that if you have a mere 51% successful independent random guesser run ten thousand times, the majority guess will be right with 97% probability. However, if you have a 51% successful random guesser that just sticks to its first guess, after 10,000 attempts you're still at 51%! Independence is critical. In particular, you need independence in your \>50% chance of success. In this construction, only bit that gets better than mere guessing is deterministic and reproducible, while the random bit is completely disconnected from reality. That means that although we can get something to a 50%+ε for all problems with some decidable special cases, we can't leverage that fact to get arbitrarily high.
> 2 votes

# Answer
There are a few different probabilistic methods that can be used to try and solve undecidable problems. One such method is called Markov chains, which are a type of stochastic process. Essentially, a Markov chain is a mathematical model that describes the evolution of some system over time, using probabilities to calculate the most likely next state for the system.

Another probabilistic method that can be used to solve undecidable problems is Bayesian inference. Bayesian inference is a technique for updating beliefs in the light of new information. It allows us to combine our existing knowledge with new information in order to make better decisions.
> -2 votes

---
Tags: complexity-theory, undecidability, nondeterminism, probabilistic-algorithms
---


# Question
Title: Is this version of Subset Product Problem NPComplete?
Subset Product Problem is $NP-Complete$. Given a promise that the product contains exactly 1 occurrences of each of its prime factor is the problem still $NP-Complete$?

Seems to be the case but couldn't find any references. Can someone confirm?

# Answer
Yes, by reduction from exact cover.
> 1 votes

---
Tags: complexity-theory
---