# Question
Title: How can I compress data that represents a number's change over time?
I have a value that increases by unknown increments at unknown times. Given a time, I need to check how much it has increased between that time and now.

I could simply store every time/increase pair whenever the value is increased, but this would be too much data to reasonably store.

```
For example:

DATA:
Value = 0 @ 0:00
Value = 2 @ 0:04
Value = 7 @ 0:05
Value = 52 @ 0:07 (Current time)

RESULT:
1 Second: 52
3 Seconds:  2 + 7 + 52 = 61

```

I am not sure what I am trying to do is even possible. But, is there a way I can store the increments such that I can keep the file size reasonably small, and still find a decent approximation of the increase in the value? It does not need to be exact - a margin of error less than 5% would be acceptable.

# Answer
In the case of storage and querying from the storage i.e. if you can first get all time:value pairs, you can use curve fitting (regression) to get the polynomial function v=f(t), where v = value and t = time which will not be accurate, may even be outside 5% error margin; but would the get the work done in a very low file size and acceptable(?) margin of error.
> 1 votes

---
Tags: data-compression
---


title: NTM's and the halting problem

text:
# Question
Title: NTM's and the halting problem
It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a DTM/input string and state whether that DTM will halt.

Is this proven, or is this an assumption under the same banner as the Church-Turing thesis?

If it is proven, does anyone have any citations for this in the literature?

# Answer
A nondeterministic Turing machine can be simulated using a deterministic Turing machine in exponential time (can be shown as a simple exercise). Furthermore, NDTM is a generalization of DTM. So, the computability powers of NDTMs and DTM are equal, in sense of decidability. So, the Halting problem is not decidable by a NDTM. However, their time complexity is different.
> 1 votes

---
Tags: algorithms, computability, halting-problem, nondeterminism
---


title: Are there any languages without tokens?

text:
# Question
Title: Are there any languages without tokens?
I know a lot of computer languages and they all use tokens. E.g. in very early BASIC you could say `LET answer = 42`, which is composed of seven tokens, `LET`, `answer`, `=`, `42`, and three space tokens.

It seems that every character must be part of some token, including comments, which can be considered free-form tokens after the initial identifier.

Are there any languages completely or partially without tokens? Is it even possible for such a language to exist? What would it look like?

# Answer
I agree with the commenters that your question is either ill-defined or nonsensical. It all hinges on what you mean by "tokens", and what it would mean to "not have tokens."

If you mean multi-character sequences that are "chunked" together into larger words, consider Brainfuck — or actually most esolangs, including my favorite, Befunge — where every "command" is a single character. However, on the other hand, many Brainfuck interpreters actually treat `[-]` as a single "chunk" meaning "set the current tape cell to zero", so in that sense maybe you'd call `[-]` a "token".

On the other hand, if you consider single characters to be "tokens", then maybe we need to go the other direction, and find programming languages in which everything kind of flows together without divisions. The first thing that pops to mind is Inform 7 (yes, that's Inform 7 source code!), where meaning is conveyed through English prose. Obviously Inform 7 has a parser that deals in *words*, but those words don't directly correspond to anything like `LET` in Basic; it's more complicated than that.

Or, consider Piet, an esolang in which programs are expressed as two-dimensional pixel paintings. Does a pixel count as a "token"? Does a rectangle of pixels count as a "token"?

In the same vein — of trying to break away from the strictures of linear *words* and into more free-flowing worlds — consider noit o' mnain worb, a nondeterministic cellular automaton. It uses ASCII characters to represent cells in the automaton; but do those characters each count as a "token", or are the relevant building blocks of worb programs more like "corridors" and "gates"?

For that matter, consider Wireworld, a better-known cellular automaton. Does Wireworld count as a "language"? and if so, does "it" "have" "tokens"?

For that matter, consider the "language" in which ENIAC was programmed. It certainly didn't have "tokens"! But if you were to write down the plugboard configuration for a given "program", I suppose that you'd pick some way of writing it down that involved ASCII and a grammar of tokens. I don't guess you'd communicate the plugboard configuration with a pen-and-ink drawing. (But maybe you would! Who knows!)

For *that* matter, what would you say about plain old x86 machine code? That's a "computer language" if ever there was one... but it doesn't have "tokens", does it? All it has is a stream of bytes, one after the other, which are chunked together to form *instructions.* Or does an instruction (such as `B82A0000` or `C3`) count as a "token"? Does it matter if the same set of bytes (or some of them, at least) could be reinterpreted by another part of the program as a piece of data, a jump address, et cetera?

Basically, you need to define what you mean by "language" and "token"; and once you do that, I think you'll find that your question answers itself.
> 3 votes

---
Tags: history, language-design
---


# Question
Title: Is Goedel's 1st theorem not algorithmically derivable?
First let me explain what I mean by algorithmically derivable. An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer scientists are able to create new proofs without prior knowledge of the proofs.

Our proof deriver enumerates all possible axiomatic systems, and with each system enumerates all possible proofs. It checks each proof to see if it proves Goedel's 1st theorem. This algorithm will necessarily derive all finite proofs eventually.

Goedel's 1st theorem states no sufficiently powerful axiomatic system can be complete and consistent at the same time. The deriver is complete, since it will eventually be able to prove all true statements and disprove all false statements. This means the deriver is inconsistent, so it cannot know whether a set of axioms used to prove Goedel's 1st are consistent.

Therefore, an algorithmic deriver is unable to derive the proof for Goedel's 1st theorem.

Does this proof succeed in showing Goedel's 1st theorem is not algorithmically derivable?

# Answer
> 1 votes
> The deriver is complete, since it will eventually be able to prove all true statements and disprove all false statements. This means the deriver is inconsistent, so it cannot know whether a set of axioms used to prove Goedel's 1st are consistent.

To start with, your deriver is actually not an axiomatic system to which Goedel's theorem would apply.

But assuming I understood your description correctly, it'll simply "prove" all sentences for two different reasons: 1) for each sentence there is a system where it's an axiom and so provable; 2) systems it enumerates will include inconsistent systems in which every sentence is provable. So the deriver is trivially inconsistent and tells you nothing about Goedel's theorem.

Now, instead of your deriver consider one which enumerates all proofs in $PA$ until it finds a proof of Goedel's first theorem and then stops. This seems to satisfy your requirements ("seems" because you don't define "prior knowledge").

# Answer
> 8 votes
Your reasoning is incorrect.

It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the set of true statements in arithmetic, which is a consequence of Tarski's theorem on truth, itself a consequence of Gödel's theorem.

However, your algorithm does enumerate all *provable* statements, including the incompleteness theorem itself.

In fact, here's a much simpler algorithm:

1. Print a formal proof of the incompleteness theorem.
2. Halt.

So you need a much subtler argument to prove that computers can't do what humans can do in terms of proofs. Certainly you would need a better notion of what "prior knowledge" of a proof means. Indeed, many people today believe that there are no tasks which are fundamentally impossible for computers but possible for humans, and I know of no unassailable argument for that position.

# Answer
> 2 votes
> Our proof deriver enumerates all possible axiomatic systems

But the set of possible axiomatic systems also include the inconsistent systems. On the other hand, the consistent axiomatic systems are not computationally enumerable, hence you cannot enumerate them.

But cody's point is probably even more relevant, since the algorithm can just write down an existing proof. That existing proof will be relative to some formal system like Coq's calculus of construction, but that should be OK.

---
Tags: proof-assistants, check-my-answer, incompleteness
---


# Question
Title: Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?
I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive.

the algo depends on finding a new weight function (w') that is positive for all edges and keeps the correctness of the shortest paths relations.

It does so by calculating h(s), h(d) values to be added to the w original value.

My question is, why not just find the smallest w in the graph and add it to all edges ? this will satisfy both conditions and will require less calculation.

# Answer
Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.)

For example, suppose the lowest-cost edge has weight $-2$ and there are two paths from $a$ to $b$: a single edge of weight $3$ and a path with two edges, each of weight $1$. The two-edge path has the lowest weight. However, if you add $2$ to every edge, the one-edge path has weight $5$ but the two-edge path now has weight $6$, so you get the wrong answer.
> 25 votes

# Answer
Increasing every edge weight by the same amount does not necessarily increase every path by the same amount of distance. Rather, the increase to the paths are often disproportional which depends on how many edges the path has.
> 0 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Prove that palindromes are not regular language without using pumping lemma
I came across this question. Palindromes are not regular: It is easy to prove it using pumping lemma. The problem is I want an explicit proof without pumping lemma. I came up with a solution. It goes like this. Let us assume a language L which is palindrome so L can be expressed as x.xR where xR is reverse of x. If x is a regular language then xR will be too and hence the palindrome will be regular. What if x is not a regular language. Lets say x is 1^n0^n. It is not possible to draw a DFA for this as this string needs memory to keep the count of 1s so that it can add exact number of 0s. Since DFA doesn't have memory so it wont be possible to make a DFA for this, but xR = 0^n1^n and L=x.xR that is 1^n0^n.0^n1^n is still palindrome but not a regular language. So we can say palindromes are not regular. I remember from my undergrad class to prove some language is not regular it is sufficient to give one negative example. Will this approach work?

# Answer
You can use the Myhill–Nerode criterion.

Suppose that $A$ is a DFA accepting your language. Let $q\_n$ be the state which the DFA reaches upon reading the word $0^n1$. As the DFA has finitely many states, we must have $q\_n = q\_m$ for some $n \neq m$. On the one hand, when at state $q\_n$, upon reading $0^n$ the DFA must reach an accepting state, since $0^n 1 0^n$ is a palindrome. On the other hand, when at state $q\_m$, upon reading $0^n$ the DFA must reach a non-accepting state, since $0^m 1 0^n$ is not a palindrome. We have reached a contradiction since $q\_n = q\_m$.
> 3 votes

# Answer
You can also use Kolmogorov Complexity.

Very informally:

* suppose that there is a DFA $A$ for palindromes $L\_A = \\{ w w^r \mid w \in \\{0,1\\}^+ \\}$
* pick a long enough uncompressible string $x$ ( $|x| \gg |A|$ )
* run $A$ on input $x^r x$ and suppose that it is in state $q\_i$ after scanning the first half part of the input (i.e. after reading $x^r$)
* then you can build a Turing machine $M$ that on input

$$\langle A, i, |x| \rangle$$

generates all strings $\\{0,1\\}^{|x|}$ and for each one "continues" the simulation of $A$ starting from $q\_i$ until it finds the (unique) string accepted by $A$ which is exactly $x$.

But $|M| = |A| + \log i + \log |x| + c \< |x|$ for a long enough $x$, in other words there is a program $M$ that is smaller than $|x|$ that generates the uncompressible string $x$; which is a contradiction.
> 1 votes

---
Tags: formal-languages, finite-automata
---


# Question
Title: Basic approximation algorithms understanding
**Question:**

Suppose we have 2 algorithms $Alg1$ and $Alg2$ for the same minimization problem. We know that $Alg1$ is a $2$-approximation algorithm and $Alg2$ a $4$-approximation algorithm.

Is the following statement true?

There must be an input $I$ such that $Alg2(I) \geq 2 \cdot Alg1(I)$.

**My answer:**

I think the statement is false:

In order to prove that the statement is false it is sufficient to find one case where $Alg1$ is a $2$-approximation and $Alg2$ is a 4 approximation and that there is no input which satisfies the inequality from the statement.

Does my approach make sense? Is there some other approach or thought process which proves statements of this type true/false that I'm missing?

Note:

$Alg$ is a $\rho$-approximation algorithm for a minimization problem $\iff$ $\forall I.(OPT(I) \leq Alg(I) \leq \rho \cdot OPT(I))$ where $\rho \> 1$ and $OPT(I)$ denotes the optimal solution to the minimization problem for the input $I$.

# Answer
According to your definition (which is the standard definition), an algorithm solving a certain minimization problem is an $\alpha$-approximation algorithm for any $\alpha \geq 1$.

Consider a minimization problem solvable in polynomial time, for example minimum cut. Let Alg1 and Alg2 be algorithms solving this problem exactly. Alg1 is a 2-approximation algorithm and Alg2 is a 4-approximation algorithm, yet there is no input on which Alg2 performs worse than Alg1.
> 1 votes

---
Tags: algorithms, proof-techniques, approximation
---


# Question
Title: Can lambda-calculus be used for knowledge representation?
Natural language semantics (in computational linguistics) uses lambda terms for expressing the semantics of natural language sentences. There is vast literature about combinatorial categorial grammars and lambda semantics of natural language, e.g. tutorial about framework http://yoavartzi.com/tutorial/

The question is - if lambda calculus can be used to represent the meaning of the natural language text, then **can we use lambda calculus for the universal representation of knowledge? Why there are so few results in this direction?** Or maybe there are efforts to bridge the meaning as expressed in lambda calculus with some of the common knowledge representation approaches?

Maybe (extended) Curry-Howard isomorphism between lambda calculus and logical/deductive systems can be used to translate the semantics in terms of lambda calculus into knowledge in terms of logical expressions, e.g., maybe translation to description logics and action logics is possible?

# Answer
> 5 votes
The λ-calculus was invented to be a logic and foundation of mathematics (1-4). The most well-known logic to use λ-calculus for formulae (as opposed to proofs in the Curry-Howard approach) is HOL (= Higher-Order Logic). The most well-developed implementation of HOL is Isabelle/HOL (5). To the extent that you believe logic can represent knowledge, you can use HOL to do that, hence λ-calculus.

There is a third approach to using λ-calculus as logic: higher-order Prolog (aka λProlog) (6), which -- like Prolog -- is based proof search, but in HOL.

The relationship between the three approaches (HOL, Curry-Howard and λProlog) is not well-understood.

---

<sub> 1. A. Church, A Formulation of the Simple Theory of Types. </sub>

<sub> 2. P. B. Andrews, Churchs Type Theory. </sub>

<sub> 3. F. Cardone, J. R. Hindley, History of Lambda-calculus and Combinatory Logic. </sub>

<sub> 4. J. B. Rosser, Highlights of the history of the lambda-calculus. </sub>

<sub> 5. T. Nipkow L. C. Paulson, M. Wenzel, A Proof Assistant for Higher-Order Logic. </sub>

<sub> 6. D. Miller, G. Nadathur, P. Pfenning, A. Scedrov, Uniform Proofs As A Foundation For Logic Programming. </sub>

---
Tags: lambda-calculus, knowledge-representation, curry-howard, computational-linguistics
---


# Question
Title: Linear/affine lifetimes without subtyping
Are there any type systems similar to rust that don't depend on subtyping ? Can we express that one value must be consumed or dropped before another? For instance if I had an array of huge values on the heap and I would like to operate on a single item using a reference to it, the compiler would need to be sure I had finished with the reference before I could mutate or drop the parent array.

# Answer
> 5 votes
Linear and affine typing systems have been developed in the context of linear logic and process calculi. Most developments of such types do not use subtyping. The system in (1) is pioneering for its use of linearity, as are (2, 3) which introduced session types which are heavily based on linearity. See also the CSTheory Stackexchange thread Determinism and pi-calculus for some other (related) typing systems that make heavy use of linearity and affinity. While all this work is for process calculi, note that sequential behaviour is a well-behaved special case of concurrency and affinity in Rust is closely related (the same) as affinity in process theory.

1. N. Kobayashi, B. C. Pierce, D. N. Turner, Linearity and the Pi-Calculus.
2. K. Takeuchi, K. Honda, M. Kubo, An Interaction-based Language and its Typing System.
3. K. Honda, V. T. Vasconcelos, M. Kubo, Language Primitives and Type Disciplines for Structured Communication-based Programming.

---
Tags: type-theory, type-checking
---


# Question
Title: Proving that a language given by a CFG is not regular
Consider the language defined by the following grammar: $$ \begin{align\*} &S \rightarrow E \\ &S \rightarrow \epsilon \\ &E \rightarrow E+E \\ &E \rightarrow E-E \\ &E \rightarrow \mathsf{STRING} \mid \mathsf{LOCTRAN}(E , \mathsf{DIGITS}) \end{align\*} $$ How can I prove that this language is not regular using the pumping lemma? I don't know which string to use.

# Answer
A basic example that is context-free but nonregular is the language $\\{ a^nb^n \mid n\ge 0\\}$.

Here this structure is hidden inside the language. You can find it using the recursive productions

$$E \rightarrow \mathsf{STRING} \mid \mathsf{LOCTRAN}(E , \mathsf{DIGITS})$$
> 1 votes

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


title: Why is $A \leq_T \bar{A}$?

text:
# Question
Title: Why is $A \leq_T \bar{A}$?
I know there's some easy proof for this, but why is $A \leq\_T \bar{A}$ ? ... Suppose that $\bar{A}$ is c.e. and could loop, does this mean that the oracle $TM$ $M^{\bar{A}}$ could also loop?

But shouldn't $\leq\_T$ mean that $M^{\bar{A}}$ be decidable?

# Answer
A language $A$ Turing-reduces to $\overline{A}$ since a Turing machine with an $\overline{A}$-oracle can compute $A$. On input $x$, it determines whether $x \in \overline{A}$ using the oracle, and then outputs the reverse answer.
> 2 votes

# Answer
Your misunderstanding is in the definition of an oracle. An oracle is a hypothetical device that answers the question "Is string $x$ in language $L$?" in a single computational step. It doesn't matter whether or not an actual Turing machine could answer that question; the oracle is *defined* to answer it, and answer it immediately.

Whether or not such a device can exist in the physical universe is irrelevant to the question of reducibility. It's relevant to the question of whether the reduction is practically usable, but that's a separate issue.
> 2 votes

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


title: Longest increasing subsequence on pairs

text:
# Question
Title: Longest increasing subsequence on pairs
Given a sequence of pairs $(a\_1, b\_1), (a\_2, b\_2), ..., (a\_n, b\_n)$ such that $a\_1 \le a\_2 \le ... \le a\_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence problem for $b$'s. Now suppose the length of the longest increasing subsequence is $X$.

If we now sort the initial sequence by the second component and solve the LIS problem for $a$'s, is the length of this sequence also equal to $X$?

Intuitively I think this is true, but I don't know if it really is.

# Answer
When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i\_1,\ldots,i\_\ell$ such that $$ a\_{i\_1} \< \cdots \< a\_{i\_\ell} \\ b\_{i\_1} \< \cdots \< b\_{i\_\ell} $$ This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.
> 1 votes

---
Tags: algorithms, subsequences
---


# Question
Title: Language of Turing machines that never visit some given state
Can someone help me to determine and prove if the following language is decidable or not?

I tried to think on some reductions but I can't figure it out...

$$A=\\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\\}$$

my try:

I built mapping reduce $E\_{TM}\le\_{m} B$:

$\<M\>\rightarrow \<M\>$

so I need to prove: $$\<M\>\in E\_{TM}\iff \<M\>\in B$$

First direction:

$\<M\>\in E\_{TM}\rightarrow L(M)=\emptyset \rightarrow M \text{ never visits } q\_{accept} \rightarrow \<M\>\in B $

The problem is in the second direction. How can I promiss that if the language is empty $M$ visits all the states?

Thanks!

# Answer
I will assume that you're using $E\_{TM}$ to mean the language $HALT=\\{\langle M\rangle|\text{$M$ does not halt}\\}$ and $B=A=\\{\langle M\rangle|\text{$M$ is $TM$ and there is a state $q$ in $M$ that $M$ never visits}\\}$. Also, you should state what your mapping is because if it is just the identity (which it seems to be here) then this won't work. This is because we can have a turing machine that halts right away but also happens to have an extra state that it never reaches, so it is not the case that $B\subset E\_{TM}$.

Instead, it may help to think about this more informally. If have the ability to tell whether or not a turing machine visits all of its states, how might we use this superpower to decide the halting problem? The simplest, most direct approach is to see if we can answer the question of whether $M$ visits a *specific* state $q\in Q$ using knowledge of $B$. Then we can reduce to the halting problem by simply asking if a given TM $M$ visits any of its accepting states.

To do this, let's see what "subsets" of $M$ are still in $B$. By this I mean that we will choose a subset $P\subset Q$ and then on any transition that goes from a state in $P$ to one in $Q\setminus P$ we will instead reroute it to a halting state. Let's call the new machine with the new accepting state along with $P$ as its states as $N\_P$.

Now, we start off by looking asking if $N\_P\in B$ for $P$ being the set containing just the starting state. If this TM is in $B$ then we know $M$ never visits any state other than its initial state. If it is not in $B$ then we continue by adding a new state to $P$ and asking if the new TM is in $B$, continuing until we get to a TM which is in $B$. The $P$ we end on will have to be the set of states the TM visits, and all other states are unvisited. Thus, we can tell whether a $M$ visits a certain state $Q$ by simply checking if $q$ is in the final version of $P$.
> 1 votes

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


# Question
Title: What is the problem with this Busy Wait solution for two threads?
We have two processes. One process produces F and the other process consumes F

Initialization:

```
Consuming = false
Produced = false
F = EMPTY

```

The first thread (we can think of it as some kind of producer):

```
P1:
loop_for_ever:
    Produce(F)
    Consuming = true
    Produced = true
    while(Consuming) {Busy Wait)

```

And here is P2:

```
P2:
loop_for_ever:
    while(NOT Produced) {Busy Wait}
    Consume(F)
    Produced = false
    Consuming = false

```

One problem with this solution is after P1 has produced F, there is no way for P2 to consume F until P1 unlocks the *Produced* variable. Any other problems with this solution with regards to mutual exclusion? Is there a scenario in which P1 and P2 try to produce and consume F at the same time?

**EDIT:**

After reading **fade2black**'s answer, I think I first need to address another more basic question. So let's add these extra conditions.

Extra conditions:

1- No mutex or semaphore based solution (only busy wait).

2- The threads have no remainder section (in that case this approach would obviously not work). Basically, what I am trying to do is to take a sequential algorithm (such as the one **@fade2black** has given) and distribute it among two threads. I could have blindly used an algorithm such as Dekker's (with turn given to P1 at the beginning). So I think first I need to find an answer for this question : "Is there any point to try and use a concurrent algorithm for this problem"? (when there is only one consumer and one producer and there is only one shared space between the two).

# Answer
**A simpler solution to the original problem**

Using Python style notation, here is the simplified and more correct solution.

Initialization:

```
consuming = False
init(F) //if needed

```

Code for P1:

```
while True:
    while consuming:
        pass
    produce(F)  //updates F
    consuming= True

```

Code for P2:

```
while True:
        while not consuming:
            pass
        consume(F)
        consuming= False

```

This is an improvement over the code posted in question. It only uses one variable and the busy wait is located before the body of the code for each thread (the code in the question could lead to trouble if P2 thread has other sections and they somehow manipulate the variables).

**A note about fade2black's answer:**

This original code is in fact concurrent. But it is not parallel.

As this source (p. 166) states:

> A system is parallel if it can perform more than one task simultaneously. In contrast, a concurrent system supports more than one task by allowing all the tasks to make progress. Thus, it is possible to have concurrency without parallelism.
> 0 votes

# Answer
Your approach works fine providing assignment operations are atomic. But **I cannot see any concurrency** in your approach. $P\_2$ always waits until $P\_1$ produces and reaches the upper limit, for example until it completely fills the buffer. Then it triggers $P\_2$ to consume and waits until $P\_2$ consumes all items, for example empties the buffer. So the algorithm can be rewritten as

```
doStuff()
  loop-forever
    produce(F) # N items
    consume(F) # N items
  end
end

```

In fact the consumer(s) consumes as soon as the producer(s) produces items. In this case you would have to use synchronizations techniques such as mutexes.

Also (from here)

> The producer–consumer problem, particularly in the case of a single producer and single consumer, strongly relates to implementing a FIFO or a channel.

So there is no point to try and use a concurrent algorithm for this problem. But if your model is multi producer/consumer model then your approach may lead to the race condition.
> 2 votes

---
Tags: concurrency, mutual-exclusion, critical-section
---


title: Logic Gates in circuits

text:
# Question
Title: Logic Gates in circuits
We can make all the gates using nand or nor gates. My teacher told us that nand gates are cheap too, then why do we need other gates at all?

# Answer
They logically exist, you can not un-invent them. Even if no one ever made one, they would still exist in your mind.

If is easier to say “open door if I want to go through door or you want to go through door” than to say “open door if I don't want to go through door nand you don't want to go through door”

# An alternate question — Why do we build devices with just one gate? i.e. `nand` or `nor`?

We do this because it makes the electronics simpler, if all the devices are the some, as we only have to implement one type of gate. This is about simplicity of the device, not of the logic (as this could be a bit more complex). This logical complexity could push the size up, but the symmetry of all gates being the same pushes the size down. Also a lot of the logical complexity can cancel out.

# A similar question — Why do we have multiply in maths. When we can do everything with addition?

* Why do we have addition when we can just use increment: 3+4 = 3+1+1+1+1
* Why do we have multiplication when we can use addition: 3×4 = 3+3+3+3
* Why do we have exponentiation when we can use multiplication 3⁴ = 3×3×3×3

If you were to continue to look inside the computer, then you will see that it is,some what, like this:

* transistors → `nand` or `or`
* `nand` or `nor` → all logic gates
* logic gates → addition
* logic gates → flip flops
* flip flops → shift registers → multiply by 2
* multiply by 2 & addition → multiplication
*

# Why do we have steel, when you can just have iron, carbon, cobalt … ?
> 1 votes

# Answer
Representing the logic is just cheaper on a physical chip. AND / OR gates take more components to build. Using a few NAND gates does the same job, in a smaller, cheaper footprint electronically.

Check this out: https://electronics.stackexchange.com/questions/20850/why-are-nand-gates-cheap
> 0 votes

---
Tags: digital-circuits
---


# Question
Title: Rice's Theorem for Total Computable Functions
Fix a Gödel numbering, and write $\phi\_n$ for the function coded by $n$. Rice's theorem states that if $P$ is the set of partial computable functions, and $A \subseteq P$, then the decision problem

> Given $n$, does $\phi\_n \in A$?

is decidable if and only if $A = \emptyset$ or $A = F$; that is, if the decision problem always has the same answer.

Now consider the set $T$ of *total* computable functions instead. Clearly, the problem

> Given $n$ with $\phi\_n \in T$, does $\phi\_n \in A$?

is no longer decidable if and only if $A \in \\{\emptyset,T\\}$. In fact, for recursive set $M\subseteq \mathbb N^k$, the problem is also decidable for $$ A\_M = \\{\phi\_n \in T \mid (\phi\_n(0),\ldots,\phi\_n(k-1)) \in M\\}. $$ So is it true that the problem is decidable if and only if $A$ is of the form $A\_M$ as above? If not, can we give a different restriction on the form of $A$ that does give us a theorem?

# Answer
**Almost**

The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values can be unbounded, so $k$ can depend on $n$). In fact, the wikipedia page for Rice's theorem has a section on this:

> ...the analogue says that if one can effectively determine for every recursive set whether it has a certain property, then only finitely many integers determine whether a recursive set has the property.

More precisely, a property is r.e. iff there is a r.e. set $T\_1$ with the prefix property (i.e.- no string in $T\_1$ is a prefix of another) such that $\phi\_n$ has the property iff there is some $k$ such that the sequence $\phi\_n(0), ..., \phi\_n(k-1)$ is in $T\_1$ (we can make sense of a sequence being in a set of natural numbers by encoding this as $p\_1^{\phi\_n(0)}\cdot p\_2^{\phi\_n(0)}\cdot ...\cdot p\_{k}^{\phi\_n(k-1)}$ where $p\_i$ is the $i$th prime). A property would be recursive iff it is r.e. and co-r.e.

This pretty much says that we can get no more information out of the index $n$ than the function $\phi\_n$ itself, because any computable property must be computable only using calls to the function $\phi\_n$. This may sound trivial, but it is no means obvious since a priori the input $n$ might have some extra non-syntactic information computably nestled into it.

Rice's theorem essentially states that no extra non-syntactic information about partial recursive functions can be computably nestled into their Godel encodings. As it turns out this is also equivalent to the above characterization, so the same thing holds for total functions as well. I suppose one could make this statement even stronger by generalizing to even more general classes of functions, but I do not know if this is true.
> 4 votes

---
Tags: computability, rice-theorem
---


title: Solving recurence relations

text:
# Question
Title: Solving recurence relations
$T(n) = \begin{cases} 2: & n=0\\ 5: & n=1 \\ 2T(n-2) - T(n-1): &n \geq 2 \end{cases}$

I have found a few examples including https://math.stackexchange.com/questions/1316301/if-tn-tn-1-2tn-2 But I am still lost about how to solve this one.

# Answer
Here's a general technique on linear recurrences that's useful to know. Observe that:

$$ \begin{bmatrix} T(n) \\ T(n+1) \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 2 & -1 \end{bmatrix}^{n} \begin{bmatrix} 2 \\ 5 \end{bmatrix}$$

If we can perform an eigendecomposition of $M$:

$$M = Q \Lambda Q^{-1}$$

where $\Lambda$ is a diagonal matrix, then:

$$M^n = Q \Lambda^n Q^{-1}$$

Raising a diagonal matrix to a power is trivial. This gives you a closed form for $M^n$.

In your case:

$$\begin{bmatrix} 0 & 1 \\ 2 & -1 \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} -2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\ \frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3} \end{bmatrix}$$

So:

$$ \begin{bmatrix} T(n) \\ T(n+1) \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} -2 & 0 \\ 0 & 1 \end{bmatrix}^n \begin{bmatrix} \frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\ \frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3} \end{bmatrix} \begin{bmatrix} 2 \\ 5 \end{bmatrix}$$

Multiplying the matrices together, taking the top row, and simplifying gives:

$$T(n) = 3 - (-2)^n$$

It's a lot of work (if you don't have a computer algebra system handy), but it always gives an answer if the system is linear and diagonalisable.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Infinite Boolean circuits as a model of computation
Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a Turing machine that can output, for some input length N, the correct Boolean circuit for that N.

However, I wonder if it is instead possible, if not a bit abstract, to instead look at finite Boolean circuits that "converge" to some well-defined infinite circuit in the large limit of N, which can handle any input size of arbitrarily large but finite length, and get an equivalent model of computation.

My intuition is that this is often the case, because it is quite common for Boolean circuits to be able to handle not only their own input size, but all smaller input sizes as well. For example, an adder that works on inputs of N bits can handle inputs of length \< N by zero-padding the highest undefined bits; this is equivalent to setting the undefined bits to zero by default. So we can easily imagine this series of circuits converging to something like ripple adder extending infinitely to the left, and for which we consider only those inputs with finitely many nonzero bits.

What I am really trying to understand is the simplest way to extend the notion of Boolean circuit to get something that is Turing-complete. For example, we can give a finite state machine an infinite queue and make it Turing complete. By looking at infinite Boolean circuits that can handle arbitrarily large input with finite support, can we likewise obtain Turing-completeness, with an analogue of the halting problem, etc? If not, how could we do it?

# Answer
> 2 votes
Your idea is equivalent in power to non-uniform circuits. Thus, it doesn't formalize the concept you want it to formalize. You were hoping that your notion of an infinite circuit would capture the power of uniform circuits / Turing machines, but it doesn't -- like non-uniform circuits, it is "too powerful" (more powerful than any uniform model). Thus an infinite circuit is essentially still a non-uniform model of computation, even if it doesn't look like it on the surface.

Consider the following infinite circuit $C$: if the $i$th bit of the input is 1 and the $i+1$st bit is 0, then the $i$th output bit is $c\_i$, otherwise that output bit is 0. Here $c\_i$ is a constant that is 1 if the $i$th Turing machine (in some canonical enumeration of all Turing machines) halts, or 0 otherwise.

This circuit is an infinite circuit, in your sense. You can think of it as a sequence of circuits $C\_1,C\_2,\dots$, where $C\_N$ is the circuit that takes $N$ bits of input and produces $N$ bits of output, obtained by zero-padding its input and feeding that to $C$. Thus that sequence of circuits "converges" to $C$.

However, $C$ has the following peculiar property: given $C$, you can solve the halting problem. In particular, if you feed in $i$ in unary as input to $C$, then the output will indicate whether the $i$th Turing machine halts or not. Thus, infinite circuits can solve undecidable problems. Like non-uniform circuits, infinite circuits are in some sense "too powerful" -- they're not realistic.

So your construction doesn't really eliminate any of the issues with the non-uniform circuit model. It just recreates them, in a slightly different guise.

---

A separate challenge with your infinite circuit idea is that it is not clear how to handle circuits that produce a single bit of output. Normally, in circuit complexity, we study circuits that take $N$ bits of input and produce a single bit of output. It's not clear how such a sequence of circuits can "converge" to a single infinite circuit (what is its single output bit, and how is it computed?).

---
Tags: computation-models, circuits, boolean-algebra, turing-completeness
---


# Question
Title: Algorithm to calculate average weight from every pair of nodes
I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph.

For example, for the following graph:

The results is calculated like this:

1 -\> 2 = 3;

1 -\> 3 = 7;

1 -\> 4 = 5;

2 -\> 3 = 4;

2 -\> 4 = 2;

3 -\> 4 = 7;

**Average** = 3+7+5+4+2+7 / 6;

**NOTE**: I'm visualizing the problem as a Graph, I might be wrong. The following **constraints** apply to this problem:

There is exactly one path between any two nodes, but all nodes are connected to every other node.

So we can assume that in the example, there will not be a path from 1 -\> 4 directly

I'm looking for a recommendation of an algorithm that I can study in order to solve this type of problems. Not the actual solution.

# Answer
> 0 votes
One possible approach is Floyd-Warshall algorithm. This algorithm computes shortest paths between each pair of nodes. Since there is only one path between each pair of nodes, the shortest path will correspond to the weight of path between each pair of nodes. After computing all shortest paths you sum them and divide by the total number of paths (which is trivial given the number of nodes). This algorithm works in $O(|V|^3)$ time.

Also note that your graph is a tree. You may take a time to think over better algorithm which would work faster.

---
Tags: time-complexity, weighted-graphs
---


title: What is structural complexity theory?

text:
# Question
Title: What is structural complexity theory?
I am new to complexity theory and want to know what is structural complexity theory? what are problems theorists try to solve in this field and what is its future? From the wikipedia:

> The structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms

I did not get the last line "rather than computational complexity of individual problems and algorithms " I mean in complexity theory we focus on complexity classes not on problems.

Thanks in advance

# Answer
> 14 votes
Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are:

> Is $\mathsf{P} \neq \mathsf{NP}$?
>
> Is $\mathsf{P} = \mathsf{BPP}$?

In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity classes. For example, people came up with oracles relative to which $\mathsf{P} = \mathsf{NP}$, and other oracles relative to which $\mathsf{P} \neq \mathsf{NP}$. This type of activity seems less popular now. *Diagonalization* is another common proof technique that used to be more popular in the past, but is somewhat less popular today.

Another common pursuit is proving conditional results. For example, Buhrman, Chang and Fortnow show that if $\mathsf{coNP} \subseteq \mathsf{NP/1}$ then the polynomial hierarchy collapses. Since it is conjectured that the polynomial hierarchy is strict (doesn't collapse), it follows that probably $\mathsf{coNP} \not\subseteq \mathsf{NP/1}$.

What are some similar results that are not considered structural complexity theory? Here are some examples:

* Results in circuit complexity. For example, $\mathsf{AC^0} \neq \mathsf{P}$ is not classical structural complexity theory.
* Results about specific problems, for example NP-completeness of specific problems.

Other results could in principle be considered structural complexity theory, but because the techniques used are so different than classical results in structural complexity theory, they are not usually thought of as structural complexity theory. Conspicuous examples include:

* $\mathsf{IP} = \mathsf{PSPACE}$, which uses algebraization. This is a borderline example.
* The PCP theorem, which uses ideas from coding theory.

---

The above is just my own opinion. Other people might have very different opinions. Structural complexity theory is not a codified area of research.

# Answer
> 4 votes
For example, a problem may be shown to be NP-Complete. Yet this is not what aimed in structural complexity theory, because it does not tell anything new about the structure of complexity classes.

---
Tags: complexity-theory, reference-request
---


# Question
Title: Mutation considered harmful, but is there a safe set
Functional programming does not have mutation. Mutation is usually harmful, however mutation is sometimes beneficial. e.g. Creating a \[random number\] generator.

In the same way that `goto` is considered harmful, but now we have structured languages that give us access to a safe set of `goto` patterns. Is there a safe set of mutation patterns? Is there currently any research into language features that implement them?

# Answer
*Ask not how to get rid of the evil mutable state, but rather how to tame it by provding structured and predictable ways of using it.*

Just because `goto` is harmful you wouldn't remove all flow control from a language, right? You'd rather think of ways of using control flow in a structured way, and then you would invent the `while` loops.

There is not single best solution on how to structure and control mutable state, but there are some good ones. For example, you can have the programmer describe quite explicitly which part of the program can do what and who "owns" stateful parts of memory. The compiler will then check for compliance. An example of this sort of thing is Rust.

There is a more general phenomenon which encompasses mutable state, namely *computational effects*. Mutable state is tricky to get right, but so is concurrency, I/O can be tricky depending on what you do, etc. These are all computational effects, and we can ask whether there are general and structured ways of dealing with them.

The most popular general way of controlling computational effects is to use monads. These are programming language constructs that allow you to express presence of certain computational effects (could be mutable state) with typing information. This way the programmer will be able to see that a certain piece of code may cause effects, and the compiler will complain if things don't fit.

Another method that has caught some interest lately is algebraic effects and handlers. It's less general than monads, but it also organizes your code in a way that is often a bit more flexible than monads (The people of the Internet want to know this too.) Briefly, handlers are a generalization of the familiar exception handlers that allow you to intercept any computational effect and do something with it. I like to explain their usefulness with the slogan $$\frac{\mathtt{handlers}}{\mathtt{callcc}} = \frac{\mathtt{while}}{\mathtt{goto}}. $$ That is, just like `while` is the structured way to do `goto`, handlers are the structured way to do non-local flow control in a functional setting (`callcc` has been called "the `goto` of functional programming").
> 5 votes

# Answer
"Mutation considered harmful" is a pretty strong statement that many people would disagree with.

Among the group that dislikes mutation there are at least two reasons for immutability:

1. Immutable data is automatically thread-safe
2. Immutable data makes it easier to reason about the software.

If you want to guarantee thread safety in the presence of mutation, you could use a type system that tracks ownership and forbids mutating the same data from different threads simultaneously. Rust is a language that does this. Another option is Software Transactional Memory, that can be implemented in a number of languages.

The second objection to mutability is a lot fuzzier. People generally agree that you shouldn't share mutable state among too many parts of your software. This is inherently a software design problem that has no general solution.
> 0 votes

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


title: Storing nodes in state space search

text:
# Question
Title: Storing nodes in state space search
I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, but I'm not sure what information I should store in the nodes of the tree.

Assume that I have a matrix to represent the game board. Should each node in the tree contain the entire board? For example, in the case of 19x19 Go, would each node consist a matrix of size 19x19 (the problem I'm trying to solve is a 1 player game, and not Go or chess or anything like that, however)? If this is the case, even with pruning, it sounds to me like this would take up an insane amount of space. For example, at depth 1, a state space of the game of Go would have 19\*19 nodes each containing a 19\*19 matrix (correct me if I'm wrong here). At the same time, I can't find a better option.

What is the general approach to storing these kinds of states?

Any help is greatly appreciated. Please let me know if the question is in any way unclear.

# Answer
> 2 votes
The common answer to "What to store?" is "As much as you need and nothing more."

You can instead store a reference to the previous state and the move(s) you made on the previous state to get to the current state.

This is more compact that a full copy of the state in each node but less convenient to work with because you'd need to reconstruct the state by following all the moves made since the last known full state node.

The next option is to throw away parts of the graph that you aren't looking at at the moment and instead recreate it later when needed.

Both of these options trade space for time.

---
Tags: graphs, trees, artificial-intelligence, graph-traversal
---


# Question
Title: Code size of Instruction set Architecture
For the following assume that values A, B, C, D, E, and F reside in memory. Also assume that instruction operation codes are represented in 8 bits, memory addresses are 64 bits, and register addresses are 6 bits, and data values are 32-bit integers (4 bytes each).

Output

Here are some calculation results

I don't understand Code size part, was not able to find it online too. Can someone explain how Code size part there is calculated? Thanks

# Answer
> 0 votes
Simply add up the number of bits per operation, register address, and memory address. I don't know why they mention data value, it doesn't really have any bearing on the calculation

---

In the stack code, there are three operations done on four memory addresses.

`Stack size = 8 * operations + 64 * addresses = 8*4 + 64*3 = 224`

In the accumulator code, there are three operations done on three memory addresses.

`Accumulator size = 8 * operations + 64 * addresses + = 8*3 + 64*3 = 216`

In the register-memory code, there are four register address accesses and three memory accesses

`Register-memory size = 8 * operations + 64 * addresses + 6 * registers = 8*3 + 64*3 + 6*4 = 240`

In the register-store code, there are six register address accesses and three memory accesses

`Register-store size = 8 * operations + 64 * addresses + 6 * registers = 8*4 + 64*3 + 6*6 = 260`

---
Tags: computer-architecture
---


# Question
Title: Minimum number of cuts to divide a rectangle
We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates.

We want a list of the minimum number of lines defined by a pair of points (x,y) that cut up the big rectangle into the small ones.

---

For example for this case:

The minimum number of cuts would be 7, and they are represented in the following picture.

Any idea to achieve this? (The rectangles are not always touching the borders.)

# Answer
> 0 votes
Each edge of an inner rectangle that (that isn't on the exterior of the big rectangle) is a line segment. Your problem now becomes: given a collection of line segments, find the minimum number of lines to cover all of the line segments (and nothing more).

This problem can be solved as follows. For each line segment, extend the line as far as you can in both directions, until it no longer is touching any line segment. Add that line to your collection of lines. Repeat until you've covered all of the line segments. In other words, merge two line segments if they are touching and go in the same direction (since in that case they can be merged into a single line that covers both). Repeat until you can't merge anything any longer.

---
Tags: algorithms, minimum-cuts
---


# Question
Title: How to prove that this defined language is regular?
Suppose that $L$ is a regular language and $0\<\alpha\<1$ and $\alpha \in Q$. Define $L\_\alpha$ as

$$L\_\alpha = \\{\omega \in \Sigma^\* \mid \exists \omega\_1 \in \Sigma^\* .\omega\omega\_1 \in L,\frac{|\omega|}{|\omega\omega\_1|}=\alpha\\}$$

How do I prove that $L\_\alpha$ is regular?

Here is my attempt. If we assume that $D$ is the automaton that recognize $L$ with $Q=\\{q\_0,...,q\_n\\}$, if $\delta(q\_0,\omega\omega\_1)\in F$ and $\delta(q\_0,\omega)=q\_i$ we can define $D\_1$ such that $\delta\_1(q\_0,\omega)=r\_{i-1}$ (for $r\_i \in F\_1)$, but the problem is I can't define $\delta\_1(q\_0,a) $for $a\in \Sigma$.

# Answer
> 1 votes
Try proving it for $\alpha = 1/2$ first. Construct a non-deterministic automaton that recognizes $L\_\alpha$. Before you start reading in the string $w$, guess something about where you will be in the future. What would you like to guess? What would help you?

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


title: How come identity encodes absurdity

text:
# Question
Title: How come identity encodes absurdity
From P5 in this paper: https://hal.inria.fr/hal-01094195/file/CIC.pdf

> Using this purely functional part, it is possible to encode many int eresting notions. For instance ∀ C : Prop , C is a logical proposition (a term of type Prop ) which encodes absurdity ( ⊥ ) : there is no closed term of type ∀ C : Prop , C (so no proof of ⊥ without hypothesis) and also from a proof t of ∀ C : Prop , C one can build a proof t C of an arbitrary proposition C so the natural deduction rule for eliminating ⊥ is derivable in the logic.

where

$$ \forall C: Prop, C $$

looks entirely identity function to me, which can definitely be inhabited by a closed term. Why the author said it encodes absurdity?

If I were to encode absurdity, I would do

$$ \exists P: Prop, P \to \forall Q:Prop, Q $$

That is, there exists a proposition which derives everything. From category theoretic perspective, it's precisely how the initial object is defined, which can encode absurdity with no doubt.

Did I misread it in a terrible wrong way that the author was actually right? How about my encoding, does it make sense to you?

# Answer
> 6 votes
> looks entirely identity function to me, which can definitely be inhabited by a closed term

A proof of $\forall C : Prop, C$ is a function from an arbitrary proposition to its proof. Since a proposition isn't a proof, an identity function is not a function from propositions to proofs.

The identity function (or rather, a function returning the identity function on proofs of $C$) corresponds instead to the proof of $\forall C : Prop, C \to C$. That's even the example on the beginning of page 3!

---
Tags: programming-languages, logic, proof-assistants
---


# Question
Title: What does instantiating existential variables with out of scope variable imply?
I have following unfinished proof of a lemma:

```
Goal forall (P : Type -> Prop) (Q : Prop),
  ((forall x, (P x)) -> Q) -> (exists x, P x -> Q).
Proof.
  intros.
  eapply ex_intro. intros. apply H. intros. eapply H0.

```

The problem is the last `eapply` failed, with the message

```
Error:
In environment
P : Type -> Prop
Q : Prop
H : (forall x : Type, P x) -> Q
H0 : P ?x
x : Type
Unable to unify "?x" with "x" (cannot instantiate "?x" because "x" is not in
its scope: available
arguments are "P" "Q" "H").

```

The proof steps themselves look very phishy already. The proof constructs an existential variables to sit in place of $x$ in the second half, and then tries to instantiate it using the $x$ obtained as premise after applying the hypothesis `(forall x, (P x)) -> Q`. The proof steps look cyclic proof to me.

What in general does this message imply? What types of logical mistake does this message indicate here?

---

There is a recent github issue from Coq actually indicates that instantiating evars outside of scope CAN prove falsehood, except that it's blocked by QED.

https://github.com/coq/coq/issues/8215

# Answer
> 9 votes
When you do an existential introduction, you are saying there is some term $t$, which is represented by the unification variable `?x`, such that $P(t)\to Q$. You then try to apply $P(t)$ to $H : (\forall x.P(x)) \to Q$. It tries to generalize `P ?x`, because if it can show that $P(c)$ for a fresh constant $c$ (represented by `x` in the Coq output), then $\forall x.P(x)$ would follow. It attempts to unify that fresh constant, `x`, with the unification variable `?x`, but this is disallowed. From a logical perspective, `?x` represents a term $t$ and that term is, by definition freshness, distinct from the fresh $c$ (i.e. `x`) which is just to say $c$ wasn't in scope when we introduced $t$, so $t$ can't have depended on it.

As a simpler scenario, we can't prove $\exists x.\forall y.x = y$ by using existential introduction with $y$. $y$ isn't in scope at that point.

---
Tags: logic, coq
---


# Question
Title: Cardinality of ordered n-grams and subsets of those n-grams from a given set
Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams. To be clear, the subsets MUST retain order as they appear in the original set.

1. The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is **6**.
2. The total cardinality of all subsets for those n-grams is **sum(1,1,1,2,2,3)=10**

So, given set T, what are the formulae for #1 and #2?

# Answer
Let $|T| = n$. Then

1. the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.
2. The total cardinality of all subsets for those $n$-grams is $$\sum\_{k=1}^nk(n-k+1) = (n+1)\sum\_{k=1}^nk - \sum\_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

1. $\frac{3\times 4}{2} = 6$
2. $\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10 $
> 3 votes

---
Tags: combinatorics
---


title: How to read regular expressions?

text:
# Question
Title: How to read regular expressions?
Consider the following regular expressions

```
letter = a + b + c + d

LETTER = A + B + C + D
digit = 4+5+6+7+9
R1 = (LETTER + digit + !) • (letter • digit)∗• (letter + digit)
R2 = (LETTER + digit + ?) • (letter + digit)∗• (LETTER + digit)
R3 = (digit + ? + !) • (letter∗• digit∗)∗• (LETTER + letter)
R4 = (digit • letter + ? + !) • (letter∗• digit∗) • (LETTER)

```

I'm not sure what some of the characters mean ('+' , '•' , '\*')?

Do I read regex backwards when check if a string is an element of L(R1)?

```
FOR EXAMPLE: !5aA ELEMENT/NOT ELEMENT L(R1)

R1 = (LETTER + digit + !) • (letter • digit)∗• (letter + digit)

!5aA is an element of L(R1) I would think, but that's just a guess.

```

If someone can point me in the right direction to read a regex like this it would be greatly appreciated.

EDIT: So after considering Yuval answer this starts to make a whole lot of sense to me so thank you. It seems like the correct language for the string !5aA is L(R3) AND/OR L(R4) not sure which exactly yet, maybe its both. I like to think the + as OR's (not multiples) the • as a concatenation (or no concatenations) and * as all combinations. Treating • as multiplication using the commutative property holds true, makes sense for the order of the chars.

# Answer
> 1 votes
The symbols you quote have the following meaning:

* $+$ means *or*: $L(r\_1 + r\_2) = L(r\_1) \cup L(r\_2)$.
* $\cdot$ means *concatenation*: $L(r\_1 \cdot r\_2) = \\{ xy : x \in L(r\_1), y \in L(r\_2) \\}$.
* $^\*$ means *iteration*: $L(r^\*) = \\{ \epsilon \\} \cup L(r) \cup L(r \cdot r) \cup L(r \cdot r \cdot r) \cup \cdots$.

(Here $\epsilon$ is the empty word, sometimes denoted $\lambda$.)

Now let us consider your example: $$ R\_1 = (\mathsf{LETTER} + \mathsf{digit} + \mathsf{!}) \cdot (\mathsf{letter} \cdot \mathsf{digit})^\* \cdot (\mathsf{letter} + \mathsf{digit}). $$ All words in $L(R\_1)$ end in a lowercase letter $a,b,c,d$ or in a digit $4,5,6,7,9$. The word $!5aA$ ends in neither, so doesn't belong to $L(R\_1)$.

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


title: Truth value of a proposition

text:
# Question
Title: Truth value of a proposition
I'm trying to write a function in Python that takes it argument as a Python list and returns a boolean value based on the truth vale of the proposition $E(x) \to \exists y \text{ s.t. } x=2y$, where here the proposition $E(x)$ means 'x is even'.

```
print(check_prop([-2,-1,0,1,2,3])) gives an output true

print(check_prop([-2,-1,0,1,3,4])) gives an output false

```

I don't quite understand how the truth value is true in the first case and false in the second.

# Answer
> 0 votes
The predicate whose truth value you're trying to check states the following:

> For every even number $x$ in the list, $x/2$ is also in the list.

This holds in the first case: the even numbers are $-2,0,2$, and indeed $-1,0,1$ are in the list, but not in the second case, since $4$ is in the list but $2$ isn't.

---
Tags: python
---


# Question
Title: How to handle the repeat until convergence condition in time complexity and summarize the time complexity?
I am a novice in complexity calculation. I need to calculate the overall time complexity.

My attempt is given below:

Here, N = number of data points (`N>300`), C = Number of clusters (`2<C<30`)

1. For line 3 to 10, time complexity, `TC1 = O(NC)`
2. For line 11 to 12, time complexity, `TC2 = O(C)`
3. For line 18 to 22, time complexity, `TC3 = O(N*N)`
4. For line 24 to 26, time complexity, `TC4 = (how to handle the repeat until convergence- the highlighted section?) (Here, I think` TC4 = O(N\*N)`)`
5. For line 16 to 29, the overall time complexity, `TC5 = C(TC3+ TC4) = O(N*N*C)// not sure about it due to the lacking confidence in the value of TC4.`
6. For line 31 to 35, time complexity, `TC6 = O(N*C*C)`
7. For line 38 to 40, time complexity, `TC7 = O(NC)`

So, finally, the overall time complexity `TC = TC1 + TC2 + TC5 + TC6 + TC7 = O(NC) + O(C) + O(N*N*C) + O(N*C*C) + O(NC) = O(?)` //How can I summarize this time complexity using Big-O.

> My Questions are:
>
> a) How to handle the highlighted portion when calculating the time complexity?
>
> b) How to summarize the overall time complexity?

Please help.

# Answer
> 2 votes
First of all, *repeat until convergence* isn't quite a well-defined command. Typically, such instructions are implemented by checking the "progress" of some performance measure, stopping once progress drops below a certain threshold.

In order to estimate the running time ("big O") of such an algorithm, all you need to do is to estimate the number of iterations until convergence. The running time of a simple "*repeat until convergence*" loop is simply the running time of the loop body times the number of iterations. This is a good upper bound if each loop iteration takes roughly the same time. In more complicated cases, in which the iterations have greatly varying running times, you can use a more accurate measure, namely the total running time of the loop body (across all iterations).

This is the *theory*. How do you apply it in your particular case? In the loop highlighted in yellow, the loop body has unvarying running time, so you need to figure out how many iterations it takes the loop to converge, and then you multiply that by the time it takes to run a single iteration. Estimating the number of iterations until convergence is beyond the scope of this answer.

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, performance
---


# Question
Title: Verifying if a greedy solution is optimal for a specific instance (Set cover)
Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution.

Is there an *efficient* way of verifying if, for that particular instance, the given solution is optimal?

# Answer
Let me formalize your problem, in two different ways:

> GREEDY-SET-COVER: Given a Set Cover instance, does the greedy algorithm always produce a set cover of minimal size?
>
> GREEDY-SET-COVER2: Given a Set Cover instance, does the greedy algorithm always produce a set cover of non-minimal size?

The two problems might seem complementary, but in fact it is *not* the case: if at some step of the algorithm there are several sets covering the same number of uncovered elements, the greedy algorithm must make a choice. In GREEDY-SET-COVER, we are asking whether *all* such choices lead to an optimal solution. The complement of GREEDY-SET-COVER2 asks whether *some* such choice leads to an optimal solution.

I will show that GREEDY-SET-COVER is $\mathsf{coNP}$-complete, and that GREEDY-SET-COVER2 is $\mathsf{NP}$-hard (but not necessarily in $\mathsf{NP}$). In fact, the same reduction will work for both.

Let me start by showing that GREEDY-SET-COVER is in $\mathsf{coNP}$. Given an instance of GREEDY-SET-COVER, all we need to do in order to show that it is a No instance is to give a transcript of the greedy algorithm together with a set cover which is smaller than what the greedy algorithm output. Unfortunately the same kind of witness doesn't work for GREEDY-SET-COVER2, since we would have to list *all* possible runs of the greedy algorithm.

In order to show that GREEDY-SET-COVER is $\mathsf{coNP}$-hard, we reduce from SAT. Let $\varphi$ be an instance of SAT with variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$. We first check whether there is an assignment to some variable which satisfies at least $m-1$ clauses. If it satisfies all clauses, the instance is satisfiable. Otherwise, the instance is satisfiable unless the remaining clause consists of this variable with opposite polarity. In both cases, we output an appropriate fixed instance of GREEDY-SET-COVER.

Suppose now that every assignment to a variable satisfies at most $m-2$ clauses. We will construct a Set Cover instance over the universe $\\{x\_1,\ldots,x\_n,C\_1,\ldots,C\_m\\}$ having the following sets:

* For each variable $x\_i$ and each truth value $\tau$, there is a set $X\_{i,\tau}$ which contains all clauses satisfied by this assignment to $\tau$, as well as the element $x\_i$.
* The set $Y = \\{C\_1,\ldots,C\_m\\}$.

If the SAT instance is satisfiable, there is a set cover of size $n$, consisting of the sets $X\_{1,\tau(1)},\ldots,X\_{n,\tau(n)}$, where $\tau$ is a satisfying assignment. Otherwise, the optimal set covers have size $n+1$. The greedy algorithm first takes the set $Y$ (since all other sets contain at most $(m-2)+1 = m-1$ elements), and then takes one set each from every pair $X\_{i,T},X\_{i,F}$, in total producing a set cover of size $n+1$. This set cover has minimal size if and only if the SAT instance is unsatisfiable.

The exact same reduction works for GREEDY-SET-COVER2, since *every* run of the greedy algorithm must start with the set $Y$, and eventually produces a set cover of size $n+1$.
> 1 votes

---
Tags: algorithms, optimization, greedy-algorithms, set-cover
---


# Question
Title: Hash table: When is it suitable to use modulo power of 2?
I am implementing a hash table that may need to grow and shrink as the number of stored keys varies. I have a hashcode function that uniformly hashes keys to positive 32-bit integers. The table itself will use a smaller array of approximate size M.

If I wanted to use the hash function to produce a value between 0 and P-1 (if P is close to M), can I use mod P if P is a power of 2?

What about using mod P, where P is a prime?

# Answer
> 2 votes
The exact size of the backing array is not that important only that it can hold enough buckets.

The reason why power of 2 is often used is because this can be implemented as a bitmask instead of a integer divide. Integer divides are pretty slow compared to other operation so they are often avoided by people trying to optimize data structures.

---
Tags: hash-tables
---


# Question
Title: Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear?
I have read in Wikipedia (and other sources) about the limited backtracking algorithm of Even, Itai & Shamir for solving 2-SAT problem in a linear time, but the approach doesn't seem to be linear, there is no demonstration nor algorithm implementation to check it.

Here is the algorithm description from Wikipedia: Even, Itai & Shamir - Limited backtracking.

Has anyone heard about this algorithm? Does anyone have its implementation/demonstration?

PS: I am not searching for an algorithm to solve 2-SAT problem in a linear time since I have read about the Aspvall, Plass & Tarjan approach. I am just interested in the former algorithm.

# Answer
> 7 votes
Below you can find a (non-optimized) python implementation of the algorithm. First, I give some hints explaining why this implementation runs in linear time. These hints assume that you know what is roughly going on, and that you have read the code.

The algorithm runs up to two threads at any given time. Initially only one thread is run. Whenever reaching a decision point (a clause with two unassigned variables), it kills the other thread and "forks" the current thread into two. The current thread is killed if it reaches an unsatisfiable clause, and if both threads are dead then the algorithm returns "unsatisfiable".

The algorithm is careful to maintain the following properties:

* The two threads are run in lockstep, each step running in $O(1)$ (apart from forking).
* Forking takes time $O(t)$, where $t$ is the number of steps since the last fork (or since the start or the algorithm).
* The total running time of all non-killed threads is $O(n+m)$ (where $n$ is the number of variables and $m$ is the number of clauses).

These properties guarantee that the main body of the algorithm runs in time $O(n+m)$. The initialization step also runs in time $O(n+m)$, and so the entire algorithm runs in time $O(n+m)$.

There are two somewhat non-trivial implementation details:

1. **Maintaining the partial assignments for the threads.** Each thread needs to maintain a partial assignment. Upon reaching a decision point, this partial assignment needs to be forked. A naive implementation would take $O(n)$ to copy the partial assignment. The implementation below uses a two-tiered strategy to handle this: there is a reference assignment which is common to both threads, and there is a per-thread addition. The implementation also keeps track on which variables were set during each thread, and uses this to maintain this data structure.
2. **Handling the repercussions of an assignment.** Whenever a variable is assigned, we need to check on all other clauses containing this variable. This is done by precalculating all clauses containing each variable, and keeping a stack of "clauses to check" for each thread. Since a variable could appear in many clauses, we copy one clause to the stack in each iteration. This forces us to keep a state machine (with two states).

The code below accepts two parameters: `n` is the number of variables, and `clauses` is a list of pairs of instances of `Literal`. For example, to check whether the 2CNF $(x\_0 \lor \lnot x\_1) \land (\lnot x\_0 \lor x\_2)$ is satisfiable, run

> `EIS(3, [(Literal(0,True),Literal(1,False)), (Literal(0,False),Literal(2,True))])`

Here is the complete code:

```
class Literal:
    def __init__(self, var, value):
        self.var = var
        self.value = value
    def __repr__(self):
        if self.value:
            return '+x%d' % (self.var,)
        else:
            return '-x%d' % (self.var,)

def EIS(n, clauses):
    """
Solve a 2SAT formula 'clauses' on 'n' variables.
The formula is given as a list of pairs of Literal.
Returns a satisfying assignment or None if formula is unsatisfiable."""
    ## construct for each variable a list of clauses it appears in
    clauses_by_variable = [[] for _ in range(n)]
    for index,clause in enumerate(clauses):
        for literal in clause:
            clauses_by_variable[literal.var].append(index)
    ## initialization
    # reference assignment
    reference_assignment = [None for _ in range(n)]
    # thread variables:
    # thread is alive
    thread_live = [True, False]
    # thread is currently updating the stack (either (var,index) or None)
    thread_stack_update = [None, None]
    # new assignment (as partial assignment)
    thread_assignment = [[None for _ in range(n)] for _ in range(2)]
    # variables assigned in this thread
    thread_assigned_variables = [[] for _ in range(2)]
    # next unhandled clause
    thread_next_clause = [0, 0]
    # stack of clauses to handle
    thread_stack = [[], []]
    ## main loop
    while True:
        # check whether any threads are alive
        if all(not thread_live[thread] for thread in range(2)):
            return None
        # advance all live threads
        for thread in range(2):
            if not thread_live[thread]:
                continue
            # check whether thread is updating the stack
            if thread_stack_update[thread] is not None:
                var, index = thread_stack_update[thread]
                if index < len(clauses_by_variable[var]):
                    thread_stack[thread].append(clauses_by_variable[var][index])
                    thread_stack_update[thread] = var, index+1
                else:
                    thread_stack_update[thread] = None
                continue
            # determine next clause to handle
            if len(thread_stack[thread]) > 0:
                next_clause = thread_stack[thread].pop()
            else:
                next_clause = thread_next_clause[thread]
                thread_next_clause[thread] += 1
            # check whether we have finished handling all clauses
            if next_clause == len(clauses):
                assignment = []
                for var in range(n):
                    value = thread_assignment[thread][var]
                    if value is None:
                        value = reference_assignment[var]
                    if value is None:
                        value = True # arbitrary value
                    assignment.append(value)
                return assignment
            # otherwise, read clause and current assignment to variables
            clause = clauses[next_clause]
            ref_values = [reference_assignment[clause[i].var] for i in range(2)]
            thr_values = [thread_assignment[thread][clause[i].var] for i in range(2)]
            curr_values = [ref_values[i] if thr_values[i] is None else thr_values[i] for i in range(2)]
            # check whether current clause is already satisfied
            if any(clause[i].value == curr_values[i] for i in range(2)):
                continue
            # check whether current clause is unsatisfiable
            if all(clause[i].value != curr_values[i] and curr_values[i] is not None for i in range(2)):
                # kill current thread
                thread_live[thread] = False
                continue
            # check whether there is a forced assignment
            if curr_values[0] is not None:
                forced = clause[1]
            elif curr_values[1] is not None:
                forced = clause[0]
            elif clause[0] == clause[1]: # clause contains two identical literals
                forced = clause[0]
            else:
                forced = None
            # handle forced assignment, if any
            if forced is not None:
                thread_assigned_variables[thread].append(forced.var)
                thread_assignment[thread][forced.var] = forced.value
                thread_stack_update[thread] = (forced.var,0)
                continue
            ## we have reached a decision point
            # update reference assignment
            for var in thread_assigned_variables[thread]:
                reference_assignment[var] = thread_assignment[thread][var]
            # undo assignments in threads
            for thr in range(2):
                for var in thread_assigned_variables[thr]:
                    thread_assignment[thr][var] = None
            # initialize threads
            for thr in range(2):
                thread_live[thr] = True
                thread_assigned_variables[thr] = [clause[0].var]
                thread_assignment[thr][clause[0].var] = [False,True][thr]
                thread_stack[thr] = []
                thread_stack_update[thr] = (clause[0].var,0)
                thread_next_clause[thr] = next_clause

```

---
Tags: algorithms, time-complexity, satisfiability, 2-sat
---


# Question
Title: Proving that a sentence in first-order logic is not valid
By the completeness of FOL, one can show that a sentence $S$ in FOL is valid, i.e. that it holds true in every model, by exhibiting a proof of $S$. Such a proof string is a certificate of the validity of $S$.

To show that $S$ is *not valid*, one can either exhibit a counterexample model in which $S$ doesn't hold, or find a proof that such a model exists, either of which would serve as a certificate.

However, do I understand correctly that while a "certificate of validity" will always exist, that "certificates of invalidity" **do not exist** in the general case?

In other words, that there can exist $S$ which are not tautologies, and for which a counterexample model exists, but for which one cannot actually construct a counterexample, or a proof of its existence?

This is not a question about the ability of FOL to formalize arithmetic (which Godel proved is impossible), but simply whether or not, in a very foundational sense, it is possible to prove counterexamples exist to FOL sentences in general.

# Answer
The completeness theorem states, in an equivalent form:

> If a formula $S$ is *not* valid, then there exists some model $\cal M$ such that $$ {\cal M}\not\models S$$ or, equivalently $${\cal M}\models\neg S $$

This is simply the contraposative of the completeness theorem, as stated on e.g. wikipedia.

This shows that there is always a "certificate of invalidity" as you ask. This is still true if you ask for $\cal M$ to be countable.

However, obviously there is no procedure to **compute** $\cal M$, by a straightforward argument involving undecidability of Robinson's arithmetic.

---

Edit: To answer the question of how one might represent such a counter-model:

Unpacking the proof of the completeness theorem shows that such a certificate can be represented by a Herbrand structure, which are the syntactic terms of the language, possibly augmented with constants and function symbols, and recursively enumerable interpretations for the predicate symbols.

In general however, the interpretation of a formula cannot be decided by such a recursive enumeration (but it can be semi-decided).
> 3 votes

# Answer
Let $\varphi(x)$ be a formula in first-order logic with free variables $x$. If $\varphi(x)$ is not valid, then $\exists x. \neg \varphi(x)$ is valid. Let $\psi$ denote the formula $\exists x. \neg \varphi(x)$. As you stated, if $\psi$ is valid, then there exists a finite proof of $\psi$.

Thus, if $\varphi(x)$ is not valid, then there exists a finite proof that it is not valid: namely, the proof of $\psi$ constitutes such a proof.

Moreover, if $\varphi(x)$ is not valid, then there exists a value of $x$ (say $x\_0$) such that $\varphi(x\_0)$ is false, and in that case there exists a finite proof that $\varphi(x\_0)$ is false (namely, the proof of validity of $\neg \varphi(x\_0)$).

So, the answer to your question is "no; a certificate of invalidity always exists".
> 0 votes

---
Tags: undecidability, proof-techniques, first-order-logic
---


# Question
Title: What is the formal name for an "entry" in an ontology?
I am trying to wrap my head around ontologies and their related counterparts (RDF, OWL, etc.).

My *understanding* is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

If that's true, I'd imagine ontologies lend themselves as perfect candidates for NOSQL graph DBs.

Either way, after all my initial reading, I still haven't found what the formal/official name is for a single "entry" in an ontology. Any ideas? Ditto for what the official names of their attributes and other relationships are. Thanks in advance!

# Answer
> 3 votes
> My *understanding* is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

The more common understanding is that one can *emulate*1 any ontology as a theory in single sorted first order predicate logic. Because such a theory can be seen as an ontology itself, it "really boils down to ... database(s)" if and only if predicate logic boils down to databases. And indeed, there is a close connection, but it won't help you to understand ontologies.

> What is the formal name for an “entry” in an ontology?

Even in your database analogy, you are missing the fact that you also have to specify the database scheme itself in the ontology language. There are different components of an ontology, namely *individuals*, *types/classes*, *attributes*, *interrelationships/relations*, *function terms*, *restrictions*, *rules*, *axioms*, and *events*1. Your "entry" seems to be intended to describe the *attributes* of an *individual*, and the *relations* between *individuals*. This task is done by the *rules*, but note that rules are more powerful than this.

---

1If the ontology contains *events*, then it is unclear how to *emulate* it in predicate logic.

---

Just like vzn, I now have the urge to clean up some of the confusion from the question, independent of whether it will earn me downvotes or not. (People might argue that such explanations based on mathematical logic require too much background knowledge, are too unrelated to ontology, and only lead to confusion. They may be right...) Even if there are practical reasons to prefer RDF or OWL as ontology languages over predicate logic, the simple structure of the later makes it a good tool for explaining some essential components of an ontology language.

A theory in single sorted first order predicate logic consists of axioms and a signature describing the non-logical symbols, i.e. the constants, functions, and predicates (and their arity). The axioms are well formed logical sentences over the given signature (with equality). Let's take set theory as an example. The signature just consists of $S\_{rel}=\\{\in\\}$ and $\operatorname{ar}(\in)=2$, i.e. "$\in$" is a binary predicate. The axioms are logical sentences like $\forall A \\, \forall B \\, ( \forall X \\, (X \in A \iff X \in B) \Rightarrow A = B)$ (Axiom of extensionality).

As an ontology, such a set theory has (at least) the following components:

* a single type/class (sets),
* a single interrelationship/relation (set $A$ is an element of set $B$ written as $A\in B$),
* and a set of axioms/rules

Further attributes and relations can be defined based on these, for example

* $\operatorname{singleton}(A) \iff \exists S \\, (S \in A) \land \forall X \\, \forall Y \\, ((X \in A \land Y \in A)\ \Rightarrow\ X=Y)$
* $A\subset B\ \iff\ \forall X \\, (X \in A\ \Rightarrow X \in B)$

In single sorted first order predicate logic, you could use such attributes (as well as attributes that are part of the signature) to emulate further *types/classes*. One can also define constants (like the empty set $\\{\\}$) and functions (like union $\cup$) based on these. So *individuals* can be emulated as constants and *function terms* as functions.

# Answer
> 1 votes
An entry in an ontology is typically called a 'concept'. It is a common understanding of what something is. Generally concepts are about kinds, although individual things may also be referred to as concepts. A concept is independent of various collections of related concepts (e.g. 'attributes'). Different models may allocate different collections of attributes the concept, being different collections of information ABOUT the concept. A concept together with a information about the concept may be called an entity or entity type, but that should be distinguished from the concept itself.

A concept is typically denoted by one or more identifiers (synonyms) that are unique within a particular context. Thus the same concept can be denoted by different terms in different 'language communities'. For example, the concept that is denoted by technicians in English as 'pump' is denoted by other terms in other languages, but also by synonyms or abbreviations in particular organizations or even user communities of systems. The concept pump is independent of any 'attributes'.

# Answer
> 0 votes
Ontologies are *"a representation of entities, ideas, and events, along with their properties and relations, according to a system of categories."* they are an abstraction that impose a limiting "world view" on reality that may or may not exist (reality is slippery that way). There is not a unique way to represent/ symbolize reality and an ontology will have both inherent objective and subjective aspects. In a sense they are almost like "belief systems" that impose a structure on reality. The concept of psychological framing and chunking and labelling are relevant. These are methods that humans use to make sense of the world and categorize it into *objects*. Hence there is also strong connection with CS oriented modelling.

Ontologies are a somewhat more general/ recent theory of the classic, decades-old, well-established version of *objects* in CS. The original concept of objects in CS are dynamic entities that model real world entities. ontologies are largely used as a sort of higher-level abstraction/ representation of objects in systems. Ontologies are roughly "the higher level entities/ properties etc expressed by CS objects of interest to external systems". It's similar or could be regarded as *a customized machine-based language to describe objects & interrelations*. Languages have verbs (representing processes)/ nouns (representing objects). There are many different language possibilities and different languages may describe the same objects. As those who know multiple languages can attest, different languages can describe different ideas, and languages can actually have a reverse-influence on thinking in this way.

From wikipedia:

> What many ontologies have in common in both computer science and in philosophy is the representation of entities, ideas, and events, along with their properties and relations, according to a system of categories. In both fields, there is considerable work on problems of ontological relativity (e.g., Quine and Kripke in philosophy, Sowa and Guarino in computer science),\[4\] and debates concerning whether a normative ontology is viable (e.g., debates over foundationalism in philosophy, and over the Cyc project in AI). Differences between the two are largely matters of focus. Computer scientists are more concerned with establishing fixed, controlled vocabularies, while philosophers are more concerned with first principles, such as whether there are such things as fixed essences or whether entities must be ontologically more primary than processes.

---
Tags: terminology, ontologies
---


# Question
Title: Neural Network | What is the purpose of hidden layers and how many should I use?
I am pretty new to Neural Networks and I have two questions about hidden layers:

1. What is the purpose of hidden layers? I was wondering this because obviously you can get every result you want with just one weight per input, as you're performing a multiplication.

2. How should I choose the number of hidden layers and how many cells should they have?

# Answer
It is actually not true that you can get any result that you want without *any* hidden layers. Consider for example a neural network with one input and one output. The only functions that such a network can be compute is threshold functions – whether the input is at most something or at least something (assuming the output is converted to Boolean).

Roughly speaking, the strength of neural networks *as a computation model* (rather than as a *machine learning* instrument) depends on two resources: *size* and *depth*. Every function can be computed (approximately) using only one hidden layer, but adding more hidden layers can dramatically reduce the size of the network needed to compute the function.

I think it is fair to say that at the moment, choosing the best network architecture involves some experience and some experimentation, since there is no good understanding of why neural networks work. Look up a paper on a similar task, and try similar parameters. There are known methods for estimating whether the network is too large or too small, and probably there are similar rules of thumb regarding depth.
> 2 votes

---
Tags: neural-networks, learning-theory
---


# Question
Title: Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)
I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere.

I have agents *j* and tasks *i*. Each agent can have between 1 and 4 task preferences (each with the cost 0-3), but *must* have only one task assigned by the end.

Each task also has a maximum number of agents that can be assigned to it (depending on the task).

Is there an algorithm out there that will minimise the overall cost, while maximising the amount of agents assigned to each task?

I hope that's clear, never really done this sort of thing before!

# Answer
> 1 votes
This can be reduced to minimum-cost flow, for which there are polynomial-time algorithms.

Build a bipartite graph, with one vertex on the left for each agent, and one vertex on the right for each instance of a task. Tasks are duplicated according to the maximum number of agents they can be assigned to. For example, if task $i$ can be assigned up to 5 agents, then there will be 5 vertices on the right corresponding to task $i$. If agent $i$ has a cost of $c\_{i,j}$ for task $j$, add an edge of cost $c\_{i,j}$ and capacity 1 from the vertex for agent $i$ to each vertex for task $j$.

Also, add a source vertex and an edge of cost 0 and capacity 1 from the source to each left vertex; and add a sink vertex and an edge of cost 0 and capacity 1 from each right vertex to the sink. Now, find the minimum-cost flow that sends at least $n$ units of flow from the source to the sink, where $n$ is the number of agents. That will be the solution to your problem.

There are many algorithms for solving minimum-cost flow problems, and even some off-the-shelf tools. See Wikipedia for some references that will get you started to learn more.

---
Tags: algorithms, assignment-problem
---


# Question
Title: Is there an algorithm that can solve chess within the span of a human lifetime?
According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree:

> A machine... would require over $10^{90}$ years to calculate the first move!

But his paper ends with a section entitled "Another Type of Strategy" and provides vague guidance on other options to solve chess.

Can it be proven whether chess can or cannot be solved with some algorithm (other than brute force) within some defined amount of time (for example, 100 years)?

# Answer
You can't prove that chess can't be solved with less than 100 years time because you don't know what computers will be developed during that time. The only limits on computational speed we know are pretty ridiculous compared to what we can do today.

You might be able to prove that solving chess needs at least X many operations, but I don't know of any such results.
> 2 votes

# Answer
Of course.

Well, maybe not in the span of a human lifetime yet, but there are lots of algorithms that given enough time, they would provide an answer!

Knowing if a problem is solvable or not doesn't depend on the amount of resources or people working on it, it only depends on the problem itself. It is a solvable problem, and it could eventually be solved. It's just that it's such a hard problem that it would take too long, and you would need an enourmous amount of memory. But even if you had only one person, or a team of millions of people, they could eventually find a way to always win the game.
> 0 votes

---
Tags: algorithms, combinatorics, search-algorithms, board-games
---


# Question
Title: Any Non-trivial Logic System Defined with only Equality
### Preface

We can define a system of logic by conjunctions of rules that system must follow. For example, if we wanted to define transitivity of numbers: $$F\_1: \forall a,b,c. a \< b \land b \< c \rightarrow a \< c$$ We could similarly define associativity: $$F\_2: \forall d,e,f. (d + e) + f = d + (e + f)$$ Then we could define a system that follows these rules by the conjunction of all these rules: $$F : F\_1 \land F\_2$$ Then if we wanted to check if a statement is satisfiable, say $S: c + 2 = b \land b = 1 \land c = 0$, we could take the conjunction of $S \land F$ and then calculating their congruences classes to see if any contradictions arise.

### Question

I am curious: Can any valid non-trivial systems of logic be describe **only** using equalities ($=$) and conjunctions ($\land$)?

What I mean by non-trivial is that for the logical system in question, $F$, there exists some statements $S$, only using conjunction and equality for both $F$ and $S$, such that: $$SAT(S \land F) \neq SAT(S)$$ Where $SAT$ evaluates to $\top$ or $\bot$ if the logic is satisfiable or not.

This is to say, the conjunction of $F$ with $S$ changes the satisfiability of $S$. If $S$ were already satisfiable, $F$ may define a system where $S$ is in fact a contradiction.

### Example 1

As an example say: $$S: x = 1 \land x = 0$$ This is satisfiable by $x = 1 = 0$, because we haven't defined what the relation of 1 and 0 are. If we introduce a system of logic: $$F: 1 \neq 0$$ Then take their conjunction: $$1 \neq 0 \land x = 1 \land x = 0$$ This is no longer satisfiable. You can see this is mainly because we introduced an *inequality* from $F$. I am wondering if you could define such an $F$ only using equality and conjunction that changes the satisfiability of an $S$.

### Example 2

I don't *think* this is possible. Let's say, for instance we define a system of logic $I$ that defines a set of integers and the addition operation ($+$), conjunctions of associativity, transitivity, reflexivity, axioms, etc. Let's assume we do this only using equality and conjunctions.

Then we describe a statement: $$S: a = b \land a = b + 1$$

$S$ is perfectly satisfiable on it's own because they would all be in the same congruence class, and because $+$ is not defined we have $a = b = b + 1$. Then introduce $I$: $$I \land S$$ Clearly this *should* not be satisfiable. However, if we have only used equality then there is nothing to let us know that any particular congruence class will have a conflict and thus it is still satisfiable (I think). Thus resulting in a contradiction that we have **not** actually define the logic system of integers. From this, I would conjecture that this is not possible, as you would need some inequality ($\<, \neq, \>$) to refute or at least discover a contradiction.

# Answer
If all you have is equalities and uninterpreted function symbols, then you have an algebraic theory a la universal algebra. A singleton set (or a collection of them in the multi-sorted case) is always a model of an algebraic theory. That is, every algebraic theory is, at least, trivially satisfiable. So if both $S$ and $F$ are required to simply be conjunctions of equations, then $SAT(S)=SAT(F)=SAT(S\land F)=\top$.
> 7 votes

# Answer
Every set of axioms involving only equations and conjunctions is satisfiable by the structure consisting of a single element $\star$, with all constants interpreted as $\star$ and all operations as trivial. This is so because in this structure *all* equations hold.
> 3 votes

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


# Question
Title: Some terminologies in Wirth's book and the satisfying of deterministic algorithm
I am going through Wirth's Textbook on Compiler design . After proceeding though some pages , I realized I have taken for granted my understanding of some of the terminologies that have been used . For example ,the following terms :

the examples mentioned in the lines in the screenshot refer to the following set of equations :

Later on while describing the possibility of the conditions of deterministic algorithms being satisfied it says for an expresion of the following form :

"term\_0 | term\_1"

the terms must not feature any common starting symbols .And then it says this results in the exclusion of left recusrsion . If we consider the left recursive production :

A = A "a" | "b"

then the requirement is violated "b" is also a start symbol of "A" .

How is "b" a start symbol of "A" ? Basically from the definitions given I understood start symbol means the symbol for which an equation is deifined first ?

Why does common start symbol disturb the conditions of deterministic algorithm ?

# Answer
The definition of *start symbol* that you quote has nothing to do with the definition of *start symbol* in the context of deterministic grammars. Here is a correct definition:

> A terminal $a$ is a *start symbol* of a sequential form $\alpha$ if $\alpha \Rightarrow^\* aw$ for some $w \in \Sigma^\*$.

In words, $a$ is a start symbol of $\alpha$ if $\alpha$ generates some word starting in $a$.

In your example, $Aa$ generates the word $ba$, and so it shares a start symbol with $b$.

Why is sharing a start symbol bad? Suppose you are trying to parse $A$, and are encountering $b$. Which production do you choose? $Aa$ or $b$? It is impossible to tell without looking ahead. The deterministic algorithm considered by Wirth has no lookahead, and so this situation is problematic for it.
> 3 votes

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