# Question
Title: Proof of correctness of A star search algorithm
I've been looking for the proof of correctness for the A star (A\*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A\* algorithm. I'm looking for a proof that if the heuristic is admissible, A\* will always give an optimal path.

Please help me understand.

To clarify, I want a proof that the path found by A\* is correct (i.e., is the cheapest/shortest path to the destination), not a proof that the A\* algorithm is optimal (i.e., that any other algorithm that uses the same heuristic will expand at least as many nodes as A\*). Also, I'm looking for a proof that only uses the assumption that the heuristic is admissible (without assuming that the heuristic is monotonic or consistent). I've looked in CLRS and haven't found any such proof.

# Answer
> 7 votes
Check the original paper which talks about its correctness -

Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.

See especially Section II and Theorem 1.

---
Tags: algorithms, graphs, search-algorithms, correctness-proof
---


# Question
Title: Why is particular token missing in LALR lookahead set?
I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:

```
S' ::= S
S ::= L = R | R
L ::= * R | id
R ::= L

```

The items associated with state 0 given in the Automaton View are as follows:

```
S ::= ⋅S, EOF
S ::= ⋅L = R, EOF
S ::= ⋅R, EOF
L ::= ⋅* R, {=, EOF}
L ::= ⋅id, {=, EOF}
R ::= ⋅L, EOF

```

Shouldn't the last item's lookahead set be {=, EOF}? This item could be derived from `S ::= ⋅R` (in which case the lookahead set is {EOF}) or from `L ::= ⋅* R` (in which case the lookahead set is {=, EOF}).

# Answer
In state 0, `R ::= ⋅L` can only be generated by `S ::= ⋅R`. In `L ::= ⋅* R`, the dot precedes `*`, not `R`, so no further items are generated by it.

The dragon book uses this grammar as an example of the inadequacy of SLR, and the correct computation of the lookahead in this case is an instance; the SLR algorithm bases lookahead decisions on the FOLLOW set rather than actual lookahead possibilities in the state, which will eventually lead to a shift/reduce conflict on lookahead symbol `=`.
> 1 votes

---
Tags: parsers
---


# Question
Title: Help in understanding how to apply nonlinear function in hashing
Can somebody help in brainstorming how to apply the map as a hashing function? I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques is the modulo hash function Why is it best to use a prime number as a mod in a hashing function? A modulo chaotic function that comes to my mind is the Dyadic map $\theta = 2 \theta mod 1$. Not getting into the details of collision resolution and other technicalities, it shall be of immense help if the application of chaos map is shown in generating hash codes. Chaos based cryptography link to paper shows that the equation on page 3 $S^t = (u^t + 2S^{t-1} + t) mod 256$ is the hashing function for cryptography. $t$ are the number of sub-blocks of the message (plaintext) and $u\_0$ is the decimal value of the first block of the message. Please help! Thank you

# Answer
Cryptographers have studied various schemes for using chaos theory to try to construct cryptographic primitives (hash functions, encryption algorithms, etc.). None of them have been successful. Chaos simply does not seem useful for designing cryptographic algorithms.

First, many of the chaos-based schemes have been broken. They didn't have as much nonlinearity as the designers anticiapted.

Second, the chaos-based schemes are slower than the state of the art. You need to iterate many times to get reasonable mixing/nonlinearity. By the time you do that, you end up with something quite slow. In comparison, we know of alternative schemes for hashing and encryption that are very fast and appear to be very secure. So, chaos-based schemes are simply not competitive.

In my opinion, chaotic maps do not appear to be a promising angle for hashing or other cryptographic algorithms.
> 1 votes

---
Tags: mathematical-foundations, hashing
---


# Question
Title: Does every procedure have a structural equivalent?
Suppose I have a basic mathematical function like:

$ f(x) = x^2 + 2$

implemented in typed pseudo-code as:

```
int f(x) {
  return x*x + 2;
}

```

If we were to break out this procedure into a step-by-step sequence of actions, we have the following:

```
f: procedure(int x) returns int:
  set int(temp)         as multiply(x, x);
  set int(temp2)        as add(x, int(2));
  set int(return-value) as temp2;
  return;

```

However, say we have an equivalent "function" that is not a procedure but is equivalent in functionality (as in, it describes the same mutations, just differently--by structure):

```
f: function(int x) returns int:
  define(return-value
    add(
      2
      multiply(
        x
        x
      )
    )
  )

```

This is essentially a mathematical expression written as a tree of operators and operands, Lisp-style.

It is very clear that the two are equivalent and describe the same mathematical expression: one by procedure, and the other, by structure/definition.

*But why is it possible to know the two are equivalent?* This mapping between procedure and functional is not always very clear. For even this pair of constructs, they are not equivalent simple "because they are." There must exist some sort of algorithm or procedure to describe how to map a procedure to a function (and, hopefully, not simply enumerating all of the possible values of output from a procedure and comparing it to a function).

---

Now, suppose we have a procedure as such:

```
g: procedure(Vector<{int red, int blue, int green}> screen,
             Vector<{int red, int blue, int green}> buffer) returns void:
  for-each {int, int, int} pixel, screen-pixel in buffer, screen:
    copy screen-pixel into pixel;
  return;

```

**Is there a system in which a structural/functional equivalent for $g$ can exist?**

**Generally; for a set of procedures, does there exist a system in which each procedure has a functional/structural equivalent?**

---

Semantics-wise, we usually know what a string of actions/instructions coupled with a set of data will do. For example, `for-each` will usually loop over a set of data performing some sort of sequences of instructions for each element in a set. However, the actual implementation of `for-each` can often differ, which means that proving that several implementations are equivalent in functionality can be non-trivial unless there is a universal way of mapping several procedures to their functional/structural form that all exist in a common system.

Generalized, if every procedure has a structural equivalent that share a common system for description, it may be possible to compare each procedure by value and then prove each are equivalent to a single function or not. This is the justification for why I am asking this question.

# Answer
Every procedure has a *functional* equivalent, but not a *structural* equivalent, going by contextual definitions of *functional* and *structural* equivalent based on your question.

That every procedure has a functional equivalent is part of the general result that all “reasonable” methods of defining computation result in the same definition of what is computable. This is the Turing thesis.

A model that is close to your definition of procedures is the RAM machine. It's also possible to define a model based more closely on imperative programming with variable names. Two models based on function calls are µ-recursive functions and the lambda calculus. Both of these models require more than the ability to call a function.

With µ-recursive functions, there is a way to iterate calls to a function (the primitive recursion operator) and a way to call functions recursively until a condition is reached (the minimisation operator). Think of the primitive recursion operator as for loops and of the minimisation operator as while loops (building a general while loop requires more than the minimisation operator because that operator extracts only a specific part of the functionality).

With the lambda calculus, functions can be defined and applied to other functions. This unbridled functionality allows building recursive functions and thus arbitrary computations.

All of these models of computation can be proved to be equivalent. I'll refer you to a textbook for a formal proof; I'll just give the intuition here. Given an imperative program, put all of its variables in a single structure. Where functions use local variables, make a chained list of structures. This way you end up with a single variable in your program. In functional programming, this is known as the *world state*. Now you can pass this single variable as an argument to all function calls and have the functions returned the modified world state. Express all loops and conditional statements using `while`, and change `while (condition) do_stuff()` to a recursive call to `do_stuff` that minimizes the number of iterations (that's where the primitive recursion and minimisation operators get combined). You no longer need any assignment operator! You've converted your imperative program to a recursive functional program.

This transformation lets you convert an imperative program into a functional one. However, it doesn't really help if what you wanted was to know whether your programs are equivalent, because there are many different ways to implement a particular mathematical function in *any* framework. It's a general result that functional equivalence (determining whether two programs compute the same result) is undecidable: there is no algorithms that given two programs always says (correctly) “yes, they're equivalent” or “no, they aren't equivalent”. This is a special case of Rice's theorem, which informally speaking says that any decidable property of algorithms that depends only on what the algorithm computes (i.e. the mathematical function that it implements) and not on how it computes it is either the property “true for all algorithms” or “false for all algorithms”. This theorem holds for any Turing-equivalent model of computation (because if there was a way to decide a property for programs written in one model, it could be transposed to any model simply by translating the programs).
> 4 votes

# Answer
> But why is it possible to know the two are equivalent?

In general, it is not. As soon as you use a Turing-complete language, deciding equivalence is undecidable; that's a direct consequence of Rice's Theorem.

> Is there a system in which a structural/functional equivalent for g can exist?
>
> Generally; for a set of procedures, does there exist a system in which each procedure has a functional/structural equivalent?

If every Turing-complete language, every program has *infinitely many* equivalents. That is a basic property of admissible numberings, a different way of formalizing Turing-completeness.

---

The answers differ, of course, if you consider less powerful models. I have yet to encounter a model of computation that has *exactly* one "program" per function it can represent; you an always add dead states or useless statements.
> 0 votes

---
Tags: computability, programming-languages, decision-problem
---


# Question
Title: Is there a point to an all-encompassing programming language?
There are many programming languages in use throughout the world today, including languages that specialize in database manipulation, functionality, object-orientation, concurrency, etc. Would there be any point in making a language that could do all these things very well, or is it best to keep these languages separate to some degree?

The reason I ask is because I had been interested in building a very basic compiler. As I became more familiar with the concepts behind compilers and the hurdles and obstacles to overcome, I realized that I should probably come up with a language that had some sort of goal. I spoke with a friend about a language that could "do it all", and he said that there was simply no point. I am still confused as to why he might claim this.

# Answer
> 8 votes
You can make a language that does all these things. The problem is that it won't be able to do all these things well, because they're contradictory. For example, database manipulation is fundamentally about changing the state of the system, so it's directly opposed to purely functional programming¹. So is fault tolerance, where a program that's running code that's mathematically proven to terminate might actually fail to terminate because the machine crashes. Object orientation with the hiding of implementation-specific details is opposed to structural polymorphism where a function might inspect the state of its arguments and expects to know about all the ways in which an object can be built. Having static type guarantees is opposed to dynamic type analysis. A language can't provide safe memory accesses *and* precise memory management in all cases. And so on.

The best you can expect is a “kitchen sink” language that includes all the features that the designers thought of. The thing is, to effectively use some of the features, the programmer needs to restrict themselves to a subset of the language that copes with those features. Of the languages commonly used in industry, C++ is the most kitchen-sinky, and that makes it hard to use because you can never be sure what features a piece of code uses and what assumptions you can make on that piece of code. For example, the type of a Haskell function makes it apparent whether it has a side effect; the type of a Rust function makes its memory management behavior apparent; with C++, you have to look at the documentation and hope that it tells you what you need.

With a kitchen sink language, you really have multiple languages in one, without the benefit of a clear barrier between the languages. Multiple languages that are each good at their job works better.

¹ <sub> If you put the database state in a monad, like Haskell does, you're no longer doing purely functional programming. You're doing imperative programming with a type system that models the impurity. </sub>

# Answer
> 3 votes
The problem is that the requirements of various programing language specializations work against each other.

For example, for systems programming (think operating systems and drivers), you want a language that's close to the metal, with predictable and high performance and you're willing to trade a lot of convenience to achieve that goal.

On the other hand, for application programming, convenience is pretty much the most important thing, and performance is secondary.

Sometimes it's possible to do both.

For example, consider `unsafe` in C#: under normal circumstances, C# doesn't have pointers, but you can use them if you need to, in specifically marked `unsafe` areas.

Another example is the concept of zero cost abstractions in C++: abstractions usually have some performance cost, but in C++, some of them are very carefully designed in such a way that they do not.

But in such cases, it's almost always a compromise. Like in the two examples above: `unsafe` means that C# is not truly safe, only "mostly safe" language. And zero cost abstractions might be less convenient than other abstractions.

And I haven't even started considering that different people like different language features (for example static vs. dynamic typing).

I think designing and implementing an all-encompassing language might be possible, but it would take a lot of time and effort and learning from what worked and what didn't in previous languages. If a single person were to create it themselves, it would probably take a lifetime.

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


# Question
Title: How is a program executed at the CPU level?
I know this is a very common question. But I have a different angle in my mind. I will just try to articulate it here.

From what I know, every instruction that a CPU executes, is in machine language and all CPU can do is do some arithmetic operations thanks to ALU and to its transistors (if we go at hardware level).

However this is easier to type than to comprehend it. So if all CPU does is adding, subtracting, etc., then how is a program, say a JAVA program saying print Hello World, executed with these arithmetic operations?

I mean how is this program converted into something that is just an addition for the CPU?

P.S. If this question is not applicable for this website then I apologise.

-----Part TWO-----

Okay. Thanks to all for answering this fast and with this enthusiasm. I thought its better to modify my question a bit than to go and comment to all answers and ask them again.

So here it is.

First, all have answered specifically w.r.t example of Hello World. This is my fault. I should have kept this generic. Hello world example brings in question of output devices and how its processing is not just limited to the CPU, which is rightfully brought up in your answers.

Also many of you brought to my notice that CPU does more than just addition. I agree with that. I just didn't write that and assumed it all the way. From what I understand, this is the process:

1. read the instruction from memory (using data and address buses and program counter stuff)

2. store data in register inside CPU
    3. Now ALU does arithmetic operations, of course after decoding the instruction, or take a jump if its an if like instruction
    4. And then communicating with other resources if needed like with output device and so on. Processes beyond this are trivial for now.

So in step3 where CPU decodes an instruction and decides to do an arithmetic operation(here we are assuming that there is no other operation to be done like jump the current instruction..since arithmetic operations are mostly done..so we will stick to that) This is where my visualization ends. How an instruction from my program is just an arithmetic operation for CPU. It does that arithmetic operation and that instruction serves its purpose.

I hope I made myself clear this time.

P.S. I am taking a big assumption here that ALU is just not restricted to actual arithmetic operation we do in our programs, rather it executes all instructions ,which are now in binary form, by adding or subtracting e.t.c them to yield result that they are meant to yield. If I am wrong here than answers below correctly answer my question.

# Answer
You can try taking a simple program and compiling it to native machine code. (Java normally compiles to JVM code, but Andrew Tennenbaum has a book where he describes how to design a CPU that runs that natively, so it will do.) On GCC, for example, you give the compiler the `-S` switch.

This will tell you that anything tricky, like I/O, is implemented by calling the operating system. While you could download the source to the Linux kernel and do the same to it, what's going on under the hood is: everything is manipulating the state of the computer's memory, for example the list of running processes, or else talking to hardware by using special memory addresses that control it or using special CPU instructions like `in` and `out` on the x86. Generally, though, only special programs called device drivers will talk to particular hardware, and the OS will send requests to use hardware to the right driver.

Specifically, if you print, "hello, world!" your compiler will turn that into a set of instructions that loads the string into a particular location (for example, loading the address of the string in memory to the `%rdi` register) and calling a library function with the `call` instruction. This library function might find the length of the string with a loop, then call the system call `write()` to write that number of bytes from the string to file descriptor number 1, which is standard output. At that point, the OS looks up what that process' file number 1 is and decide what writing to it means. If writes to standard output get printed on your screen, there will be some process like copying the bytes to a buffer, which is then read by your terminal program, which tells the windowing system which letters to put where in what font. The windowing system decides exactly what that should look like, and tells a device driver to put the pixels on the screen, which it does by changing video memory.
> 7 votes

# Answer
Your CPU in itself is dumb, as you figured out. But there is a microcosm of hardware chips around it. You have an instruction that lets you set one line of the CPU to high-level which is wired to another chip. That hardware chip monitors the line and says:"Hey, if this line is high, then I do something with some other lines."

To make this easier, these lines are grouped together. Some are used to address devices, some are used to transfer data for those addresses and others again are just "Dude, there is something important going on in my chip" lines.

In the end, your CPU merely tells some other chip to pretty please modify the signal to the monitor so it looks like "Hello World".

Google the drawing of a 7-segment-display. It has wires, which will make a segment light up if you apply voltage to it. If you connect now one output line of your CPU with one line of the 7-segment display, the display lights up. It's not the CPU that causes the LED to light, it just applies voltage to lines, but some other hardware stuff might do nifty things due to it.

If your CPU now sets all the lines for the H to high, the 7-segment will display H, although H is not a number that a CPU would add or subtract from.

Now, if all layers agree what is necessary to make the 7-segment-display H (set 5 specific lines to high), the Java compiler can make code to make it display H. This is of course rather inconvenient - so the layers start to abstract. The lowest layer will start by:"Yo, there are like 26 letters, let's assign numbers to each letter - how about we give the letter 'H' the number '72'? Then you can just tell me "Display letter 72", instead of "Set line 309 high, set line 310 high, set line 498 high, set line 549 high, set line 3 high". And so each layer starts to abstract information, how to achieve certain results, so you don't need to care about them.

So yes, it sums up to a huuuuge mapping of numbers or bits, the CPU can actually process, to meanings that everyone in the chain agreed upon.
> 5 votes

# Answer
In college as part of a CS degree program, I studied an extended example of *register transfer language* defining a CPU. I was inspired to take a different take on it and write a simulator that accepts such notation as a definition, and published that in *Embedded Systems Programming* (March 1989 issue) as a way to answer the same kind of question you asked, allowing people to build their intuitive understandings of such things.

In class, we went on to distill that resister-transfer notation into actual logic gates on the registers! It writes itself: look at everything that has register 'A' as the destination, and code A= (case1) or (case2)... and that gets expressed as sum-of-products or product-of-sums normallized form.

Only at the end of the course did I learn that this was a real CPU: the PDP-8 if I recall correctly.

Today you could feed the gate diagram into a programmable logic array chip.

That's the gist of it: a register is set with the result of AND and OR gates leading back to other registers. One of the values to include is the opcode value.

So imagine: A := (opcode==17 & X+Y)|(opcode==18 & X+Z)|...

Modern cpus are more complicated, with pipelines and busses, but individual subunits like an single ALU work that way.
> 3 votes

# Answer
You're considering the CPU here, but there is another component involved when running 'Hello World': the display!

For the CPU, a value in memory is just a number represented as a given number of bits (0's and 1's).

How it turns into letters on the screen is another story: the display also has memory. This memory (graphic memory) is mapped to 'pixels' on the screen. Each pixel is encoded with a value: if it's a very basic monochrome display, the value is just intensity, for color displays the value is a combination of Red Green and Blue (RGB) which can be encoded in many different ways.

So, when the CPU 'write' a given value into the display memory, the pixels light up. To actually write letters, one needs to light up many pixels. Typically a computer will have a character set (actually several) defined in its operating system. (making abstraction of the 'fonts' themselves, that maps to a definition of what each letter should looks like on the screen)

So, as the code is compiled, it includes all sorts of things that come from the OS libraries, including these font/char set etc.. which allow the CPU to know what to write where in the graphics memory. (It's quite complex but that's the general idea: the compiler includes a lot more code than what's in your 'hello world' code alone, through imported libraries)

In the end, there has been a whole lot of things happening as you suspect, but you didn't have to write all that code.
> 2 votes

# Answer
Here's a formal approach to your question from the field of theoretical computer science.

Basically, we can define a mapping between the computation model of a CPU and a turing machine. There exist theoretical proofs that the set of all imaginable turing machine programs (and therefore all imaginable programs executable on a CPU) is countable infinite. This means that we can identify every program with an unique natural number, *including the program that would extend natural numbers to turing machines*.

As you already know that almost anything CPUs do is computations on natural numbers in binary representation, you can reason that CPUs can carry out every imaginable program.

Note: This is overly simplified, but, in my opinion, gives a nice intuition.
> 1 votes

# Answer
CPUs work like this:

* fetch current instruction, increment "current instruction" pointer.
* decode it (e.g. find out what is this instruction telling the CPU to do)
* execute it (do what the instruction says) - the current instruction pointer may be modified if the instruction is something like a "jump".
* Repeat forever

Modern CPUs are more complex and try to heavily overlap and even predict parts of that process (e.g. start executing while 10 other instructions are decoding while the CPU is fetching far ahead of the "current instruction" pointer to keep "pipelines" full), but the essential process is really the same.

There are many types of instructions, an example of most of them is:

* "Move" instructions. These can copy X to another X, where X is memory (RAM), a register, or an address in I/O space if the CPU supports such a notion.
* Stack manipulation instructions, including pop into register, push register on stack, etc. These are a special case of "move" instructions that use and update a "stack pointer" register.
* Instructions that perform math operations, either between two registers or memory and a register. These instructions automatically affect a flags register. One such flag is the "zero" flag which is set if the result is zero, another is the "negative" flag which is set if the most significant bit of the result is set. There may be others depending on the CPU.
* A special case of math operations are comparison instructions, which is the same as a subtraction, but the result is not kept. Flags are still affected.
* There are branch instructions that jump to a memory address IF specific flags are set. Remember the "zero" flag mentioned above? It also doubles as the "if equal" flag, so you see instructions like `BEQ` on many CPUs which actually branches if the "zero" flag is set.
* Instructions that perform logical operations (AND, OR, NOT), shift bits, and test bits. They may affect flags like math instructions depending on the CPU.
* Instructions that jump unconditionally.
* Instructions that jump and save the return address on the stack (a "call"), and other instructions that pop an address off the stack (a "return").
* Special instructions like those that halt the CPU, identify the CPU, or call interrupt handlers.
* "No Operation" - almost all CPUs have a "no-op" instruction that just consumes cycles and moves on.

This is really just an example, there are CPUs with less types of instructions and CPUs with more.

The point is to illustrate that there are many types of instructions besides math instructions in a CPU. Everything in a higher-level language is broken down to the types of operations above and only some of those will be math or ALU-type instructions.
> 1 votes

# Answer
What may help is to shift your thinking away from "doing arithmetic." If you're really trying to dig at what computers are doing under the hood to print "Hello World" its best to think one level lower. The computer's "state" can be described as a set of bits, stored by transistor switches which are either on or off (or capacitors which are either charged or uncharged). The computer manipulates those bits according to rules. The ways the computer is permitted to manipulate those bits are written onto the CPU in the form of transistors which do the work of changing bits from 0 to 1, or 1 to 0.

When an ALU "does arithmetic," what that really means is that it changed the state of the computer in a way that is consistent with our rules of arithmetic. All it did was change some bits. It's the *meaning* behind the software that explains why we should think of it as addition or subtractions. The CPU doesn't "know" what it's doing. It just changes from state to state, and that's all (at least until Skynet takes over).

When you think of it that way, more complicated instructions like a "jump" instruction are no different. All it does is change some bits. In this case it happens to change the bits that we know *mean* the location of the next instruction to execute. The CPU doesn't "know" this, but we do. So we use the instruction which changes those bits to "jump" from place to place in our code.

IO is really no different either, it's just changing bits. The only *minor* difference is that those bits are connected to transistors which eventually lead to lighting up characters on your screen. If I may harken back a few decades to when "Hello World" was actually simple, there was a memory space where, if you wrote bits to it corresponding to the ASCII characters for "Hello World," those characters would be rendered directly to the screen. Nowdays it's a bit more complicated, because we have graphics cards and operating systems that mess with it, but the basic idea is the same. You have a set of transistors which are either on or off, which are linked to circuitry to display a pixel on the screen. We set the right ones, and it looks like "Hello World" appears on the screen.

The confusion is simply a matter of syntax vs semantics. The behavior of a "half added" or a "full added" in an ALU is syntax. It defines what bits will come out when you put bits in. The semantics of it is the concept of the ability to do addition. You and I are aware that the ALU can "do addition," but to really understand what happens underneath, you have to remember that an ALU only manipulates the bits and bytes of the syntax.
> 1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: How to Trace Path in Proof that Regular Languages are Closed Under Reversal
I'm self studying automata theory and I need help with proving that regular languages are closed under reversal.

I have a basic proof, but am unsure about last statement in my proof. Is this sufficient? Could you help me explain why it works? Is it rigorous enough?

Problem: For any string $w=w\_1w\_2\cdots w\_n$, the reverse of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order, $w\_n\cdots w\_2w\_1$. For any language $A$, let $A^\mathcal{R} = \\{w^\mathcal{R} | w \in A \\}$. Show that if $A$ is regular, so is $A^\mathcal{R}$.

Proof: Let $N = (Q, \Sigma, \delta, q\_0, F)$ be an DFA recognizing $A$. We construct an NFA $M = (Q', \Sigma, \delta', q\_0', F')$. Let $Q' = \mathcal{P}(Q) \cup \\{q'\_0\\}$. For this NFA, $q'\_0$ is a new start state. Let $F' = \\{q\_0\\}$, the start state of $N$.

Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma\_\epsilon$, \begin{equation\*} \delta'(q,a) = \begin{cases} F & q = q'\_0, a = \epsilon\\ q'\_0 & q = q'\_0, a \neq \epsilon\\ \\{ x | x \in Q\ and\ \delta(x,a) = q \\}&q \neq q'\_0 \end{cases} \end{equation\*}

For any $w \in \Sigma^\*$, there is a path from $q\_0$ to $q\_{acc} \in F$ in $N$ if there is a path following $w^\mathcal{R}$ from $q'\_0$ to $q\_0$. Therefore, $w^\mathcal{R} \in A^\mathcal{R}$ iff $w \in A$.

# Answer
Whether a proof is sufficiently detailed is in part a question of taste. Your last statement is very general and with little detail. A more detailed argumentation could be like this:

* Let the path from $q\_0$ to $q\_{acc}$ go through the sequence of states $q\_0 -\> q\_1 -\> ... -\> q\_{n-2} -\> q\_{n-1} -\> q\_{acc}$.
* Transition $q\_{n-1} -\> q\_{acc}$ reads the letter $w\[n\]$ (w has length n) which is equal to $w^R\[1\]$. According to the third clause in the definition of $\delta'$ there is a transition $\delta'(q\_{acc},w\[1\]) = q\_{n-1}$ which can start a path for $w^R$ in M.
* Now you can continue by induction or by simply stating that the same is true for every transition in the path for $w$. At any rate, since your construction is on the level of transitions, your argumentation should go down to the level of transitions somewhere and not stop at the level of paths.
> 1 votes

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


title: Sum of 3 integers with full adder

text:
# Question
Title: Sum of 3 integers with full adder
1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image below).I mean C1 comes from the frist block and I dont provide it. And this mean I can only choose the first bit of C0. So it does not add 3 integers, right?

2)Is it possible to get the sum of k n-bit integers with full adder circuit?

Thanks in advance!

# Answer
> 1 votes
It seems you have almost invented the carry-save adder.

You can use independent full adders for several layer, each time reducing 3 wires of equal weight to 1 wire of that weight and 1 for the next higher weight. Of course if there are 6 wires of the same weight, you can reduce them to 2 of the same weight and 2 of the next higher weight, and so on.

But the result of doing a bunch of that is not the sum, but two partial sums, one coming from all the S outputs of the last layer and one coming from all the C outputs. They still have to be added normally. You can use a ripple-carry adder or something faster/bigger there like a Kogge-Stone adder (which you'd only need once, compared to n-1 times if you just added up everything the obvious way).

# Answer
> 0 votes
1) That is correct. Even if you *could* mux the carry bits to be set to the bits of a third input, your adder would produce incorrect results. The carry is necessary to compute the addition of the two inputs, `A` and `B`. Try doing addition the elementary school way and ignore the numbers you carry over (or even better, set the carried over numbers to a third operand's digits). It wouldn't make sense.

2) Of course. This is also mentioned by @kennytm

The simplest way is to replicate and cascade the adder you have shown in your question such that the sum of one adder is one input operand of the next. The other operand is the next n-bit input.

To add `k` `n-bit` numbers, you would require `k-1` two (`n-bit`) input adders. The input of the `m`th adder would be the sum from the `m-1`th adder and the `m+1`th number, for all `m` except `m=1`.

# Answer
> 0 votes
To add three n bit numbers, there is a simple method.

Take n one-bit full adders. Each full adder takes one bit of each of the three numbers as input, and generates a sum and a carry.

You create one n+1 number by shifting all the carrys one position to the left and filling with a zero, and one n+1 number by taking all the sums and adding a zero bit. Now you just have two n+1 bit adders to add.

Full-adder 0: x0, y0, z0 -\> s0, c0

Full-adder 1: x1, y1, z1 -\> s1, c1

Full-adder n-1: x(n-1), y(n-1), z(n-1) -\> s(n-1), c(n-1)

Now add (0, s(n-1), s(n-2), ..., s2, s1, s0) and (c(n-1), c(n-2), ..., c1, c0, 0).

You use the same principle to add k numbers quickly: For every 3 n-bit numbers, you use a line of full adders to create two n+1 bit numbers. For example, given k = 10 numbers, you use three lines of full numbers to reduce this to 7 numbers (by turning three times 3 numbers into three times 2 numbers), then reduce 7 to 5, 5 to 4, 4 to 3, and 3 to 2. And then comes your n-bit adder.

The same principle can be used at a massive scale to build a 64 x 64 bit multiplier: You multiply a 64 bit number by 1 bit using 64 AND gates. Now you have 64 64-bit numbers to add. A massive number of full adders converts 21 sums of 3 numbers into 42 numbers and so on.

---
Tags: circuits, boolean-algebra, integers
---


# Question
Title: Can regular languages be Turing complete?
I was reading about Iota and Jot and found this section confusing:

> Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-branching. As a result, Iota is strictly context-free, but Jot is a regular language.

My understanding is that both Iota and Jot are Turing complete. But apparently, one is context-free, and the other is regular! Surely regular languages can't be Turing complete?

# Answer
> 48 votes
In short, the answer is yes.

But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing):

* A set of strings. "Context-free language" means "a set of strings which can be recognized using a context-free grammar".
* A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which the Turing machine can be specified".

Note that you can talk about "the C++ language" from two completely unrelated viewpoints, using the two unrelated meanings of the word "language":

* C++ as a set of strings which are legal according to the C++ grammar
* C++ as a way of specifying programs.

The traits of "the C++ language" from these two viewpoints are unrelated.

More examples to help you separate these concepts:

* The expression "\[a-z\]+@\[a-z\].\[a-z\]" describes a set of strings recognizable by finite automata, i.e. a regular language. However, it's just that - a set of strings: is not a way of specifying programs (unless you ascribe a way to interpret each such string as a program), so it does not make sense to talk about whether or not it is Turing-complete.
* The language of flowcharts is a way of specifying programs; depending on the particular flavor of flowcharts, it may or may not be Turing-complete. However, flowcharts aren't strings, so it makes absolutely no sense to talk about flowcharts in the sense "language as a set of strings".

# Answer
> 11 votes
While the set of legal programs in Jot is regular, Jot itself is Turing-complete. That means that each computable function can be expressed in Jot. We can even come up with a language in which all binary strings are legal, but the language itself is Turing complete (exercise). You're confusing syntax and semantics.

By the way, context-free languages are also (probably) not NP-complete, since they have a polynomial time parsing algorithm.

# Answer
> 9 votes
Syntax alone (as encoded in syntax trees) of modern programming languages is far from everything they do. In fact, the *formal* languages defined by the set of all programs in a given language that compile without error are rarely even context-free.

Static and dynamic semantics factor into the equation. They are invisible in the syntax tree but determine if a piece of code is actually a program and what it computes. Bottom-line, the context-free resp. regular formal language which is defined by "syntax" gives an *overapproximation* of the programming language.

Now to answer your question: yes, it's possible. Consider, for instance, any Gödel numbering of Turing machines; you get the "programming language" of all natural numbers, each representing a TM. Granted, it's not a nice language to program in, but it's certainly a Turing-complete language which is regular -- trivial, even.

# Answer
> 5 votes
1. A programming language is *Turing-complete* if it is expressive enough to specify every function computable by Turing machines. Here we are discussing *the power of languages specified **in** the programming languages*. E.g. it is not difficult to write an interpreter for Turing machines in Python, so Python is a Turing-complete programming language.
2. *The syntax of a programming language*, i.e. the set of strings corresponding to valid programs in the programming language, is itself a language. E.g. consider the set of all possible Python programs. The syntax of a programming language can be *context-sensitive*, *context-free*, *regular*, etc. We are interested in the difficulty of checking that a given string is a valid program in the programming language (this is done by compilers/interpreters). When we say the syntax of a programming language is context-free it means that there is a context-free grammar for its syntax and implies that there is push-down automata for checking the validity of programs,

Note that the simplicity of the syntax of a programming language does not imply a restriction on the computational power of the programs specified in that programming languages.

# Answer
> 2 votes
The answer is yes. You see, as the accepted answer states, a grammar is independent of its meaning. In Chomsky's own words:

> I think we are forced to conclude that a grammar is autonomous and independent of meaning...
>
> Chomsky, Syntactic Structures (1956)

If a grammar can produce sufficient sentences to describe all things that can be computed then we can arbitrarily assign computational meaning to its sentences - one for each thing that can be computed.

As for a real concrete example, the popular language `whitespace` has a regular grammar and perhaps even `x86 assembly languages` (needs verification).

---
Tags: regular-languages, programming-languages, turing-completeness
---


# Question
Title: Is there a way to determine if a collection is a palindrome within a time bound?
I'm learning about data structures, and there's a problem where, given a collection of words $X = (x\_1, x\_2, \dots, x\_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm looking for an algorithm that runs in $O(c n)$ time, where $c$ is the maximum length of any word in $X$.

A collection is a palindrome if all the characters in $X$ can be rearranged into a palindrome. For example, $X =$ (nun, ap, pa) is a palindrome (since apnunpa is) and (run, urn, appa) is a palindrome (since apurnnrupa is). The characters can be re-ordered, even within a word. The alphabet is also limited and finite.

I read about palindrome trees, but the question can be answered with a basic data structure. Any ideas on how to design an algorithm with worst-case running time $O(n)$?

---

Original Question:

##

My main question is what implementation would be best for find if a collection is a palindrome. The best one I found to remain within the time constraints would be a binary heap. What I don't get is how I can check if the characters can form a palindrome or not. My normal implementation would be to form combinations of all then check if its a palindrome, which is O(n!). Any ideas on what method works?

# Answer
If n is the number of words, it's impossible. It would mean that any roblem with just two words could be solved in constant time. But you could have two words of arbitrary equal length, and the time to confirm that one is the other reversed is unlimited if the length of the words is unlimited.

PS. Your edit changed this from a rather interesting problem to one that is really boring and trivial. You take an array with 26 counters, one for each letter, initialised to all zeroes. You go through the letters, and for each letter you increase the corresponding counter. When you are done, you check that there is at most one odd counter.

When you ask a question, it's only polite to take your time to state the question properly. Your original question has nothing whatsoever to do with the edited one.

And if you haven't figured it out: In a palindrome, the first and last letter, the second and second to last letter, and so on, are equal. Which means you have even numbers of each letter. There may be *one* letter in the middle (like in oxo) that doesn't have a match, or there may be none (like in otto). Which means at most one letter has an odd count. So to figure if a palindrome can be formed, just count the letters.
> 2 votes

---
Tags: data-structures, time-complexity
---


# Question
Title: Would removing the branch delay slots change the instructions set architecture?
I am trying to study for an exam and I noticed a lot of the questions follow the idea of "Changing the ISA". From my understanding the ISA dictates the structure and format of instructions, so changing instructions or the format (32 to 64 bit) would change the ISA. However I ran into a question which I am not sure how to answer.

"If we remove the branch delay slots, will the ISA be changed?"

My guess would be no, because we're not changing any instructions (right?), but I would like to get an answer from someone more knowledgeable.

# Answer
> 10 votes
The instructions set architecture (ISA) is the *contract* between the hardware designer and the software designer. Anything that changes the contract, changes the ISA.

The question you have to answer is: given every possible program written with this particular ISA, do any of them have different behavior (give a different answer) if we remove the branch delay slots.

# Answer
> 1 votes
Branch delay slots (in those processor in the past that had them) meant that if one instruction did something that set condition flags, and the very next instruction in the branch delay slot did branch depending on condition flags, then it was guaranteed that the branch was taken or not taken according to the state of the conditions flags *before* the previous instruction.

Take the branch delay slot away, and now the branch is taken or not taken according to the state of the condition flags *after* the previous instruction.

The behaviour of identical code would be entirely different, therefore it's an ISA change.

---
Tags: computer-architecture, cpu
---


# Question
Title: Are neural networks a type of reinforcement learning or are they different?
Can neural networks be considered a form of reinforcement learning or is there some essential difference between the two?

By the same token could we consider neural networks a sub-class of genetic algorithms?

According to my current understanding the taxonomy is kind of like this:

```
   Reinforcement Learning
      Evolutionary Algorithms
         Genetic Algorithms
            Neural Networks

```

Is this right?

# Answer
## What is a neural network?

Neural networks are algorithms for function approximation. I like to call them a construction kit for functions. Their basic building block is a neuron, commonly visualized like this:

You can see the $n$ inputs $x\_1, \dots, x\_n$ ($x\_0$ is typically constant 1), each multiplied with a weight $w\_i \in \mathbb{R}$. This gets summed up and an activation function $\varphi$ (e.g. sigmoid $\varphi(x) = \frac{1}{1+e^{-x}}$) gets applied. So a neuron is a function

$$f(x\_0, \dots, x\_n) = \varphi(\sum\_{i=0}^n x\_i w\_i)$$

The learning is just adjusting the weights $w\_i$ automatically to something that makes sense in your context.

Now we can have arbitrary numbers of inputs $x\_i$, but to have an arbitrary number of outputs we need more than one neuron. To get our model much more flexible, we stack them to a so called multilayer Perceptron (MLP):

So you can see, the output of one neuron (perceptron) can be the input of another! With backpropagation (a good implementation of gradient descent for this type of model) you can automatically adjust the weights.

## What is reinforcement learning?

In machine learning you can distinguish 5 types of problems:

* **Regression**: Predicting a continuous variable
    + You have a photo of a person and you want to tell how old the person is (e.g. howhot.io)
* **Classification**: Predicting a variable with finite possible values
    + MNIST: You get a 28px x 28px image. You know it is either 0, or 1, or 2, ..., or 9. So a digit. You have to say which one.
    + ImageNet: You get a bigger image. You have to decide which one of a 1000 classes it is (dog, cat, car, house, ...). You can be sure it is one (and exactly one) of those.
    + http://write-math.com: Classify a handwritten symbol into about 380 classes
    + https://howhot.io/: Classify gender
* **Clustering**: Grouping data
    + You have a lot of portrait images (or crops of images). You know there is exactly one persons face on it. You don't know how many people there are in total. Now you would like to group it so that each group is one person.
    + Species: You properties of animals and you want to group them. So you want a hierarchical clustering which puts closely related animals (dogs, cats; fly, moscito) closer together than not related ones (dogs, flys)
* **Collaborative Filtering**: Filling gaps
    + Netflix: You have a lot of movies, a lot of ratings. However, not every person rated every movie. In fact, probably no person did. But you want to fill the gaps so that you can tell the users which movies they should watch because they will probably like it.
    + Amazon: pretty much the same as with Netflix, but for all kinds of products
* **Reinforcement learning** (RL): Learning with environment
    + Self-driving cars
    + Playing games (e.g. Backgammon, Go, Atari (video))

What makes RL very different from the others is that you typically don't have a lot of data to start with, but you can generate a lot of data by playing. You have to deal with the problem that you have to make decisions, but it is not clear what is good (delayed reward). For example, it might take several moves until you know in Go if a move was smart.

## What is different between neural networks and RL?

Neural networks are algorithms, RL is a problem type. You can approach RL with neural networks.

## What is the relationship between neural networks and genetic algorithms?

Search for "the five tribes of machine learning", e.g. the image on http://www.welchlabs.com/blog/2016/2/16/whats-next-for-welch-labs
> 10 votes

# Answer
I would suggest a different categorization. Note that it is hard to put those terms into a strict hierarchy. But there are the three large concepts that your terms can be categorized into:

## Problem

A mathematical formalization can defines an objective object, also known as loss, error or cost function. The goal is to minimize or maximize the objective which can be done by defining a *model* and applying an *optimization algorithm*. Examples:

* Markov decision processes are the problems studied in the field of reinforcement learning.
* Supervised learning where the model output should be close to an existing target or label. Subcategories are classification or regression where the output is a probability distribution or a scalar value, respectively.
* Unsupervised learning is a class of problem settings where no labels are available. One problem in this class is to reconstruct data examples from small representations.
* If you want, supervised learning can be seen as a special form of reinforcement learning with the environment being fully observable, sequences of length one, and the cost function as the reward. Both are problem settings.

## Optimization

An algorithm at tweaks parameters of a model in order to minimize or maximize some objective function. The model we know about the model, the more effective algorithm we can use. Examples:

* Some simple models can be solved analytically. For example, one can calculate the optimal parameters of a linear regression model by performing inverting a matrix.
* Some problem settings and models are fully derivable. For example, neural networks can be trained for classification problems by computing the derivatives using the chain rule and applying gradient descent.
* When the problem setting is completely unknown, one can only guess parameters of the model and see if they work better or worse. Evolutionary algorithms are a class of algorithms that aim to do this efficiently.

## Model

Models approximate functions and have parameters that can be adjusted. Usually, a model is optimized using an algorithm to better fit observations, or training data. Coming up with powerful models usually is not the problem. Optimizing (training) the models is. Examples:

* Neural network
* Generalized linear model
* Support vector machine
* Stochastic policy
> 1 votes

---
Tags: algorithms, machine-learning
---


title: Small hard 3-SAT instances

text:
# Question
Title: Small hard 3-SAT instances
I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4.

However, I would like to know if there is a similar result in the case for the number of clauses is small. For example, for \< 20 clauses?

For example, if you had 8 clauses and you took a clause/variable ratio of 4, then you would have 2 variables, but this would be quite trivial to solve.

Do there exist heuristics for generating difficult small instances, or is it a simple matter of testing to see what works?

# Answer
If the number of clauses is very small, then there's no clause/variable ratio that makes 3-SAT hard. 3-SAT with \< 20 clauses is easy. It's asymptotically easy (technically, the running time is $O(1)$) and easy in practice (using off-the-shelf SAT solvers).

One way to derive hard instances is based upon cryptography, where you convert the problem "find a value $x$ whose SHA256 hash starts with 128 zeros" to SAT, or "find a 128-bit AES key $k$ that encrypts a fixed 128-bit string to another fixed 128-bit string". However, these are still going to have thousands of variables and tens of thousands of clauses, at minimum.
> 2 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


# Question
Title: It is necessary to minimize the functional
Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height of $0$, and the lower right the height $1$. For each road we know how many people go in each direction on this road. In this case, if the road leads from the intersection $i$ to the intersection $j$ and the height difference $h = h\_j - h\_i$, the inconvenience of moving every person on this road is equal to $\max(h, 0)$. For all intersections except two angle are allowed to choose any height. It is necessary to minimize the total inconvenience. In the end, it is necessary to obtain only a total inconvenience, the individual heights are not needed.

I think all heights will lie in the set $\\{0, 1\\}$. It is clear that you can honestly cycle through all the bitmaps and choose the best. But you need to find more efficient algorithm. One of my ideas was to put all the intersections in the upper left part of the height equals $0$, and the right lower part of the height equal to $1$. Here would be required to find the optimal boundary. I came up with a way of solving by finding maximum flow of minimum cost in $O(N^8)$. Can it be better?

Example:

P. S. Sorry for my bad English.

# Answer
> 1 votes
This problem is exactly the problem of finding the minimum $(s,t)$ cut in a directed graph, where $s$ is the upper-left corner and $t$ is the lower-right corner. All the vertices on the $s$ side of the cut will be assigned height 0; all the vertices on the $t$ side of the cut will be assigned height 1; and the capacity of the cut is equal to the sum of the counts on the edges that cross the cut in the $s\to t$ direction. You want to minimize this sum, so you want to find the minimum $(s,t)$ cut. There are many standard algorithms for doing that, based on finding a maximum flow and then applying the min-cut max-flow theorem.

---
Tags: optimization, network-flow, max-flow
---


# Question
Title: Bin packing with given bin sizes, not necessarily same
I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP Hard, considering that bin packing is NP hard?

# Answer
Yes, it's still **NP**-hard, because the input could specify that the bins actually are the same size, which is the standard **NP**-hard version.

A general rule of thumb is that allowing the input to be more general can't make the problem any easier, as long as the new setting includes the original hard case as a special case.
> 2 votes

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


# Question
Title: Amortised analysis of a simple loop and 3 operations
I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.

Operation `OP(S,X[i])` has complexity `O(log|S|)` and operations `push` and `pop` has constant complexity `O(1)`.

```
S <- Emptystack
for i=1 to n do
    while (S!=0) and OP(S,X[i]) do
        pop(S)
    od
    push(S,X[i])
od

```

I would like to proove it using potential function. It would be simple if there were just `pop(S)` and `push(s)`:

Pot.function represents number of items in stack

> C^ PUSH = 1 + |S|+1 - |S| = 2
>
> C^ POP = 1 + |S|-1 - |S| = 0

So the complexity would be linear `(O(2n)) = O(n)`. But I don't know how to compute amortized complexity of `OP`.

# Answer
We can divide the running time into several parts:

* Pushes.
* Pops.
* The first OP performed at every round.
* Subsequent OPs performed at every round.

Note that every OP costs $O(\log n)$, that there are at most $n$ pops, and that each "subsequent OP" follows a pop. We conclude that the total running time of pushes and pops is $O(n)$, the total running time of first OPs is $O(n\log n)$ (since there are $n$ rounds), and the total running time of subsequent OPs is $O(n\log n)$ (since there are at most $n$ pops). In total, the running time is $O(n\log n)$.

If you want to use the potential method, try to use a potential of the form $|S| + \log(|S|!)$.
> 2 votes

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


# Question
Title: Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'?
I'm defining 'Hard AI' as a human-equivalent intelligent machine, or beyond that. Contrast with 'Soft AI' the type of software that runs on your email filter for example.

I've been chewing on this problem for a little while now, and would like some feedback on my logic. This is the only place I could think to put it, so please feel free to move/remove if this is not appropriate.

My argument hinges on the definition of 'human-equivalent intelligence' as 'capable of solving any given instance of the Halting Problem'. This is something no machine can ever do - while they may be able to solve for sub-sets of the Halting Problem, they can never accept an arbitrary instance of it (ie, specific inputs I for a specific program P) and produce an answer.

Humans, however, do this all the time! The entire profession of programming revolves around fixing incarnations of the Halting Problem that pop up in one's own codebase. There are problem-tracking instances full of real-world examples of the Halting Problem - "Subsystem Z stops responding after receiving A with B options", etc. These examples are fixed by humans, and the problem goes away. Sometimes instructions are written for the machine to verify that the problem hasn't returned, taking advantage of the recognizability of solutions to the Halting Problem.

Since any 'Hard AI' would need to be just as capable as humans in any intellectual pursuit, and we KNOW that a machine that solves the Halting Problem cannot exist, we must conclude that there can never be human-intelligent machines.

# Answer
You're understanding of "solve all instances of the Halting Problem" is flawed. All instances means ALL instances. Every single one, ever.

For example, no human knows if a Turing Machine verifying the Collatz Conjecture will halt. Bam, right there, your premise that humans can solve "all" incarnations of the Halting problem is flawed.

There is no reason to think that a sufficiently good AI wouldn't be able to solve the same, or more, instances of the Halting Problem that humans can.

The undecidability of the Halting problem means that there is no algorithm which solves the halting problem. That means there is no algorithm Humans can use, and no algorithm machines can use. The proof doesn't rely on what the algorithm runs on.

Another way to look at it is that the halting problem, and other undecidable problems, essentially boil down to searching an infinite space. The inability of humans to time travel and examine an infinite number of instances doesn't negate our intelligence, so there's no reason it would for machines either.
> 7 votes

# Answer
Here's a thought experiment: the mathematical framework with which we usually work is called ZFC, and it has 9 axioms. Given a program $M$ and input $x$, a Turing Machine could iterate over all proofs of two steps, then all proofs of three steps, and so forth, until it finds a proof of whether $M$ halts on $x$. If there exists a proof, then this Turing Machine will find it. As you point out, this is different from the statement, '*if $M$ halts, then this machine will prove it,*' because the halting problem is undecidable.

For your AI premise, let's suppose that for some $M,x$, there is no proof, but there is a human who says that $M$ never halts on $x$. Good for him, but now what? If he is right, nobody can verify that he is right by running the machine until it halts, and we cannot find a proof, either. This person could not satisfactorily explain his reasoning to others because to do so would be to prove it formally, which we assumed was not possible (in ZFC). What if two humans conjecture differently? Nobody could distinguish between a human who was always right about such machines, and one who was always wrong. This is important, because humans do not have this skill innately, it must be learned. But how do we learn if there are no examples? And if there are examples, why can't a computer be programmed to learn in the same way?

In summary, there cannot be a human who both (a) gets the halting problem right on undecidable instances *and* (b) can give a satisfactorily detailed explanation of why he is right.

This is a contrived attempt at a proof, but there is a better way: if humans can answer the halting problem, then (by simple reduction) they can also tell in how many steps they will halt. For a simple introduction to just how mind-numbingly small our knowledge to this extend is, see the wikipedia page for Busy Beaver. Currently, we do not even know how for long the longest-running 3-state 3-symbol Turing Machine runs.

The instance you mention of 'subsystem Z stops responding with input X' isn't always a clever solution by humans. Usually, programmers empirically see how long a program should take before it resumes responding and set a simple timer. So not only is it not a proof, it may produce false positives! My computer sometimes does this when starting Kerbal Space Program, for example, because that program loads a gigabyte of data from disk before it starts. Some programs can be proved to halt, and most programs written in a sufficiently high-level programming language have very simple proofs because they mostly just iterate over finite data structures, do an operation a given number of times or do other things that obviously halt, because those are the kinds of programs that programmers usually write.
> 4 votes

---
Tags: artificial-intelligence, halting-problem
---


# Question
Title: Universal quantification in description logic
I'm struggling to understand the universal quantification operator in description logic. Here is an example of the problem:

given the DL concept

$\forall R.A $ *(where $A$ is an atomic concept and $R$ is an atomic role)*

and an interpretation $\mathcal{I}$ such that $\Delta^\mathcal{I} = \\{a\\}$ and $R^\mathcal{I} = \emptyset$ and $A^\mathcal{I}$ is empty or not , is it true that $(\forall R.A)^\mathcal{I} = \\{a\\}$?

More generally speaking, is it always the case that if $R^\mathcal{I}$ is empty then $(\forall R.A)^\mathcal{I} = \Delta^\mathcal{I}$? Is it a vacuous truth?

# Answer
In Description Logic quantification restrictions define new concepts. The semantics of $\forall R.A$ defined so that $x\in (\forall R.A)^{\mathcal I}$ if and only if for each $y\in\Delta^{\mathcal I}$ where $(x,y)\in R^{\mathcal I}$ we have $y\in A^{\mathcal I}$.

With this definition one can check that your understanding is correct: for an empty role $R$ $\top \sqsubseteq \forall R.\bot$ (*all things are related to no other thing through $R$*). I dare say that few practical ontologies ever use empty roles as constructors.
> 3 votes

---
Tags: logic
---


# Question
Title: Oracle Relations Between Complexity Classes
I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally misunderstanding something (or more than one thing).

For example, I understand that for an oracle separation to hold in the unrelativized case it must hold for all possible oracles (which is why we cannot answer P=NP? this way). However, is it not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle? For instance, by choosing a higher level of the arithmetic hierarchy to use as the oracle?

i.e. given two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma\_{n}^{0}$, is it not always the case that $A^{\Sigma\_{n+1}^{0}} = B^{\Sigma\_{n+1}^{0}}$, given that the arithmetic hierarchy doesn't collapse? If not, why?

# Answer
You seem to understand the concept even though you described it wrong.    Unless exactly one of {A,B} is uniform, an oracle separation of A from B either means  \[showing that there is an oracle O such that  AO ≠ BO \] ,  or means \[exhibitings an oracle O such that  AO ≠ BO \].

Yes, it is "not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle".  In particular, most hierarchy theorems relativize.  However, it *is* the case "that for any two complexity classes we can always construct" a class-oracle "such that they are equivalent in relation to that" class-oracle.  (For example, this one always does that.)  The triangle levels do not have complete sets with respect to syntactic subclasses of , and each other non-computable level is not low for itself.

Given "two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma\_{n}^{0}$," it is indeed "not always the case that $A^{\Sigma\_{n+1}^{0}} = B^{\Sigma\_{n+1}^{0}}$," even though "the arithmetic hierarchy doesn't collapse".  See two sentences before this sentence.
> 4 votes

# Answer
You are right, but I think you have a misunderstanding about what is meant by an oracle separation result. There are two common kinds of oracle separation results that I've seen in complexity theory. I'll illustrate them by talking about comparing the two complexity classes $P$ and $NP$, but the same applies to any other pair of complexity classes.

1. A weaker result is to prove there exists an oracle $A$ such that $P^A=NP^A$ and there exists an oracle $B$ such that $P^B \ne NP^B$.
2. A stronger result is to prove that, for a randomly chosen oracle $A$, we have $P^A \ne NP^A$ with high probability or for almost all $A$. (More precisely, the set $\\{A : P^A \ne NP^A\\}$ has measure 1.)

Both results imply that certain kinds of proof techniques are not going to work. In particular, *relativizing proofs* won't be strong enough to prove $P \ne NP$.

There are also other kinds of separation results. But none of these try to prove that $P^A \ne NP^A$ holds for *all* oracles $A$ (indeed, as you suggest, that isn't true).
> 3 votes

---
Tags: complexity-theory, turing-machines, oracle-machines
---


title: About the MNIST data-set

text:
# Question
Title: About the MNIST data-set
Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional space? Of course I don't expect the data will be exactly on some low dimensional manifold; there will be some noise.

# Answer
The short answer is: I don't know.

## Visualizations

There's been lots of work on visualizing the MNIST data set, in 2 dimensions, and even in 3 dimensions.

For instance, here's an embedding into 2D space using a neighbor embedding visualization technique (a highly nonlinear embedding):

Credit: Zhirong Yang, Jaakko Peltonen, and Samuel Kaski. See their page on MNIST visualization.

However, the NE embedding is not linear. It doesn't try to be a linear map from the image space ($\mathbb{R}^{768}$) to the plot ($\mathbb{R}^2$). Rather, it tries to preserve the topology: it tries to make images that are nearby (e.g., in L2 metric) be near each other in the visualization.

---

See also this blog article for exploration of different ways of embedding MNIST into two or three dimensions, including both linear embeddings (e.g., PCA) and nonlinear embeddings.

Here's another visualization of doing PCA to 2 dimensions on MNIST:

Credit: taken from this nice blog post

One thing that is clear from those visualizations is that if you do PCA onto two or three dimensions, the result is not linearly separable. It's not even close to linearly separable.

Even if you look at just two different digits and apply 2-dimensional PCA to project linearly onto the two principal components, the result is again not even close to linearly separable:

Credit: the same blog post

So at least 2 dimensions don't seem to be enough to distinguish 4's from 9's.

In contrast, PCA onto 2 dimensions *does* give you something that's pretty close to linearly separable: it's enough to distinguish some other pairs of digits pretty well with a linear classifier, but not perfectly -- to get best accuracy, you need more than a linear classifier and more than 2 dimensions.

Read the rest of that blog post to see what happens when you try to do a locally linear embedding to project all MNIST digits onto 2 dimensions. You'll see that, while there are some commonalities, the result doesn't look good enough to get high accuracy.

## A note of caution

We need to be careful about what you mean by "lay on a manifold". Of course, if you consider all the ways to write a 7 (say), those 7's will all lie on *some* manifold in $\mathbb{R}^{768}$. I doubt that manifold is going to be a linear subspace (i.e., a hyperplane).

If you allow arbitrarily nonlinear manifolds, it's not clear that it is useful or meaningful to ask what is the dimension of this manifold. For instance, consider a mapping that maps each digit to $\mathbb{R}$ (1 dimension), e.g., all 0 digits get mapped to 0, all 1 digits get mapped to 1, all 2 digits get mapped to 2, and so on. This is clearly possible in principle, but the mapping is extremely nonlinear. Would you consider this evidence that the digits lie on a 1-dimensional manifold? Probably not. This highlights the challenge in making our intuition more precise.

So you need to make sure you are asking the right question.

## Measuring dimensionality by learning

One way to think about this is to look for an embedding $f:\mathbb{R}^{768} \to \mathbb{R}^d$ into some lower-dimensional space ($d$-dimensional space), with the two properties that:

1. The embedding $f$ is "nice" in some fashion -- it need not be linear, but hopefully it is continuous or locally linear or something like that.
2. Enough information is preserved that we can still classify which digit it is, based on the result of the embedding. In other words, given an image $x$ of an image, we should be able to tell which image it is given only $f(x)$: the result $f(x)$ of the embedding should be enough for a classifier to tell which digit it is, with about as high accuracy as would be possible given the original image.

People *have* studied this. For instance, people have built *autoencoders*, which are basically a way to use a deep neural network to build an embedding $f$ such that you can still reconstruct the image with reasonable accuracy. You can train an autoencoder on the MNIST digits to build an embedding $f$ that maps to a lower-dimensional space, then train a classifier that tries to label the digits based on the result of the embedding. The following paper looks at one approach to that, on the MNIST data set:

Wei Wang, Yan Huang, Yizhou Wang, Liang Wang. Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction. IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp.490--497.

They build autoencoders that map to a 30-dimensional data space, and where a simple classifier achieve an error rate of 4-5%. For MNIST, 4-5% error rate is very high: the state of the art is an error rate of 0.5% or so, when training a classifier on the original images. So this means that, as far as we know, if you try to map down to 30 dimensions, a lot of information is still preserved, but a significant amount is lost: you lose enough information that the classifier's error rate increases by an order of magnitude.

In short, 30 dimensions doesn't seem to be enough, at least for an embedding built in this way.

The other caveat is that the embeddings built in this way use a multi-linear neural network, and thus might still be fairly nonlinear. If you demand a particularly "smooth"/"nice" embedding, this result might not be relevant.
> 2 votes

---
Tags: reference-request, machine-learning, data-mining, data-sets
---


# Question
Title: Knapsack: there is a polynomial solution in bit terms?
I'm reading about Knapsack problem. The approaches to solve that I found:

* Branch and bound
* Brute force
* Dynamic programming
* Memory functions
* Greedy

All solutions have exponential time in terms of bits. There is a solution (maybe an approximation algorithm) that solve Knapsack problem with polynomial time in bit terms?

# Answer
Your question is answered in the Wikipedia article on the knapsack problem: https://en.wikipedia.org/wiki/Knapsack\_problem#Computational\_complexity, https://en.wikipedia.org/wiki/Knapsack\_problem#Approximation\_algorithms.
> 0 votes

---
Tags: time-complexity, np-complete, knapsack-problems
---


# Question
Title: Preservation of context-free languages under prefix and suffix elimination
Let $\Sigma=\\{0,1\\}$ be our alphabet. Let $L$ be some context-free language, which is known to start and end with 0's, meaning that every word $x$ in $L$ has a form $x=0y0$. Let $M$ be a language obtained from $L$ by deleting one starting and one ending $0$, $L=0 \cdot M \cdot 0$.

My question:

Is $M$ still context-free? It seems yes, however I can't prove it. I have tried to construct a push down automaton for $M$ from that of $L$. However, starting $0$ seems to give possibly infinite amount of configurations. So I don't know what to do.

If this question appeared somewhere, I would be grateful if you could provide a reference or a link. Thanks.

# Answer
> 1 votes
I answer for the case that an arbitrary number of leading or trailing $0$ can be deleted. This supposes that your $L=0M0$ is wrong; it would mean that all words in $L$ start and end with $0$. Since the rest of your question does ot seem to imply this and since that case would be rather trivial, I ignore this equation and answer what I understand from the rest of the question.

You are right. There is no bound on the number of 0 in the beginning, and each one of them can put something on the stack. Thus there is an infinite number of possible stack configurations that can be reached after reading them.

My idea is this: essentially we replace the transitions that read $0$ by ones that read the empty string $\lambda$. The problems are now that $0$ inside $M$ must still be read and that the $\lambda$-transitions could be executed inside $M$, too.

Therefore we make three copies of the sets of states and transitions. In the first one we replace input $0$s by $\lambda$ in all transitions. All transitions reading an input different from $0$ lead to the corresponding state in the second copy of the state set.

The second set works like the original PDA reading the word from $M$. For every transition that reads $0$ we add a copy that leads to the corresponding state in the third set; these amount to guesses that the current $0$ starts a final block of only $0$.

The third set works much like the first (reading $\lambda$ instead of $0$), only for inputs other than $0$ it rejects.

For the $L=0M0$ case you can adapt this contruction as follows: all the new $\lambda$-transitions from the first set lead immediately to states of the second set. In this way only one leading $0$ is simulated. For the termination: go to a special final state after simulating the read of one $0$.

---
Tags: context-free
---


# Question
Title: Maximum set of equalities, subject to some inequalities
I have $n$ variables $x\_1,\dots,x\_n$. I'm given a set $E$ of equalities (each of the form $x\_i=x\_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x\_i \ne x\_j$ for some $i,j$). I want to find a maximum-size subset $E' \subseteq E$ such that $E'$ is compatible with $I$, i.e., such that there is an assignment to the $n$ variables that satisfies every inequality in $I$ and every equality in $E'$.

Is there an efficient algorithm for this?

I can see that the greedy algorithm (try adding equalities to $E'$ as long as doesn't imply the negation of some inequality) doesn't yield an optimal solution. I have no idea what other approaches to try.

---

Equivalently, the problem can be formulated in graph-theoretic terms. I'm given an undirected graph $G=(V,E)$ and a set $I \subseteq V \times V$. I want to find a maximum-cardinality subset $E' \subseteq E$ of edges, such that when I decompose the graph $G'=(V,E')$ into connected components, $v,w$ are in different connected components for all $(v,w) \in I$.

# Answer
Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.

> Given a graph $G = (V, E)$ and a set of pairs $(s\_i, t\_i) \in I$ find a set of edges $E' \subseteq E$ such that there is no path $s\_i \leadsto t\_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.

Since each inequality is unweighted you need to find a minimum size multi-cut.

This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s\_i, t\_i)$ cut.
> 3 votes

---
Tags: algorithms, graphs, constraint-programming, connected
---


# Question
Title: How to Generate Control flow graph from a Petri net model?
My research is mainly focused on generating test sequences automatically using Colored Petri net.CFG provides techniques for generating test sequences. But some papers says that, test sequence generation methods based on a control flow graph sometimes suffers from a feasibility problem (i.e. some paths in a CFG may not be feasible).So I need a technique to draw a Control flow graph from the Colored Petri net model, in a way that, when I will select paths from the control-flow graph it will contain only the feasible paths.Then I will generate test sequences from the CFG. Can anyone help me finding any technique please or give me any suggession??

# Answer
> 4 votes
Since you are interested in generating test sequences automatically using colored Petri nets, note that it's not clear that you need reduction to control flow graphs (and dealing with all the related issues). Some techniques were presented, that use various different methods to generate test sequences from Petri nets. Some examples include:

H. Watanabe and T. Kudoh, "Test suite generation methods for concurrent systems based on coloured Petri nets," Software Engineering Conference, 1995. Proceedings., 1995 Asia Pacific, Brisbane, Qld., 1995, pp. 242-251.

J. Desel, A. Oberweis, T. Zimmer and G. Zimmermann, "Validation of information system models: Petri nets and test case generation," Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., Orlando, FL, 1997, pp. 3401-3406 vol.4.

Xu, Dianxiang. "A tool for automated test code generation from high-level Petri nets." Applications and Theory of Petri Nets. Springer Berlin Heidelberg, 2011. 308-317.

On the other hand, since Petri nets and control flow graphs are not semantically equivalent in general (and capture different type of information), the translation between the two is usually done in some specific domain (and restrictions). (Although usually, control flow graphs can be transformed into equivalent Petri nets.). Some examples and discussions are given in:

De Jong, Gjalt G. "Data flow graphs: system specification with the most unrestricted semantics." Proceedings of the conference on European design automation. IEEE Computer Society Press, 1991.

The Design Of A General Method For Constructing Coupled Scientific Simulations, Matthew J. Sottile

Note that your question seems a bit too general. (Moreover, it also seems as an instance of XY, as noted by D.W.) Without more details, it seems hard to give a concrete and concise answer. Hopefully, given pointers can get you closer to your desired goal.

---
Tags: formal-methods, software-verification, software-testing, petri-nets
---


# Question
Title: Is the punctuation part of the alphabet?
Given a language $L \subseteq \Sigma^\*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "-\>") as a part of the alphabet $\Sigma$ upon the language is built on or not?

# Answer
Yes, for a couple of reasons.

* In *natural language*, punctuation changes the parsing and meaning of sentences. The classic example is "The panda eats shoots and leaves" (describing its diet) has a different meaning than "The panda eats, shoots, and leaves" (describing its violence before it departs). A parser should, in theory, generate different parse trees for these two sentences.
* In formal languages, punctuation doesn't really exist as an entity separate from other symbols. So unless adding and removing punctuation from a word NEVER changes its membership in a language, you want to consider it, since any decision procedures will need to know about this.

For formal languages, we can't ignore that sometimes, what you call punctuation, might change the properties of the language.

For instance, it's easy to accept the set $\\{ w.w^R \mid w \in \Sigma^\* \\}$ with a deterministic pushdown automaton. But remove the $.$ character as a delimiter, and we need non-determinism to guess where the end of the first string is, and where its reversal starts.
> 3 votes

# Answer
Yes. The alphabet is the set of *all* characters that can appear in the strings you're interested in, since a string is defined to be a sequence of characters from the alphabet. If you state that punctuation is not in the alphabet, then "Hi, Gerardo!" is not a string.
> 3 votes

---
Tags: formal-languages, programming-languages
---


title: Martin-Löf randomness characterization

text:
# Question
Title: Martin-Löf randomness characterization
In his 1973 paper On the notion of a random sequence, Levin states (without proving) a characterization of Martin-Löf randomness by writing

> **Theorem 3.** A sequence $\alpha$ is random w.r.t. the distribution $P$ in the Martin-Löf sense if and only if the probability ratio $P(\alpha\_n)/ R(\alpha\_n)$ is bounded below

where $R$ is the universal semicomputable (semi)measure.

I feel a bit confused how this ratio could not be bounded below, being the ratio of two positive quantities it should always be bounded below by $0$.

# Answer
The ratio should be bounded below by a positive constant. Equivalently, its infimum should be positive.
> 1 votes

---
Tags: randomness, kolmogorov-complexity
---


title: Proving $\Omega(cf) = \Omega(f)$

text:
# Question
Title: Proving $\Omega(cf) = \Omega(f)$
I'm trying to prove the following lemma:

$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:

$\Omega(cf(n))$ = $\Omega(f(n))$.

I know that it is obvious but I'm trying to construct a proof that is as complete as possible. My current approach is like this:

This lemma is equivalent to saying that: $f(n) \in \Omega(cf(n))$ iff $cf(n) \in \Omega(f(n))$.

We can also restate that as:

1. If $t(n) \in \Omega(cf(n))$ then $t(n) \in \Omega(f(n))$.
2. If $t(n) \in \Omega(f(n))$ then $t(n) \in \Omega(cf(n))$.

For 1.,

$(\*)$ $\exists d\_1, d\_2 \gt 0, \forall n \gt n\_0, n\_1, \forall n \in N$:

$t(n) \ge d\_1cf(n)$ and $t(n) \ge d\_2f(n)$

Now let's fix $d\_1, d\_2$ and $n\_0, n\_1$ to be any constants that fulfils $(\*)$, such that: $n'=max\\{n\_0, n\_1\\}$ and $d\_1c \ge d\_2$, using this we can say that:

$t(n) \ge d\_1cf(n) \ge d\_2f(n)$ and hence the 1. is satisfied because $t(n) \in \Omega(cf(n)), \Omega(f(n))$. The proof of 2. is mutatis mutandis.

Do I have a mistake in my proof, is there a better/more elegant way to prove this lemma? Shortly how can I improve this?

# Answer
I think you're trying to take too many steps at once. Try to think about it one small step at a time.

Always think about:

* What are the definitions I have available
* What do I know already? What is proven?

## Proving sets equal

Since you have two sets, $\Omega(cf)$ and $\Omega(f)$ and you want to prove them equal, you first need to think about what it means for two sets to be equal:

$$A = B \Longleftrightarrow A \subseteq B \land A \supseteq B$$

This tells you, that you need to show two things:

1. $\Omega(cf) \subseteq \Omega(f)$
2. $\Omega(cf) \supseteq \Omega(f)$

## Proving $A$ to be a subset of $B$

For this, you need to apply the definition of $A \subseteq B$:

$$ A \subseteq B \Longleftrightarrow \forall a \in A:(a \in B)$$

## Nature of our proof

As you can probably see by now, our proof will have the following form:

$$\begin{align\*}"\subseteq":\\ & \text{Let } g \in \Omega(cf):\\ &\Rightarrow \dots\\ &\Rightarrow g \in \Omega(f) \end{align\*} $$

The proof goes the same way for $"\supseteq"$.

## Filling in the dots

Keeping this structure in mind, the path you need to follow is already laid out.

Using this definition for \Omega: $ \Omega(f) = \\{ g |\\, \exists\\, n\_0 \in \mathbb{N}, c \> 0 \forall n \geq n\_0: cf(n) \leq g(n) \\} $

One direction of the proof could look as follows:

$$\begin{align\*}"\subseteq":\\ & \text{Let } g \in \Omega(cf): \\ &\Rightarrow \exists\\, n\_0\in \mathbb{N}, c'\>0: c'cf(n) \leq g(n)\ \ \forall n \geq n\_0 &\text{definition of } \Omega\\ &\Rightarrow \exists\\, d\>0, n\_0\in \mathbb{N}: d f(n) \leq g(n)\ \ \forall n \geq n\_0 &\text{Let } d=c'c\\ &\Rightarrow g \in \Omega(f) &\text{definition of } \Omega \end{align\*} $$
> 2 votes

# Answer
Why do such $d\_1, d\_2$ always exist?

You might not be able to increase $d\_1$ indefinitely in order to fulfil $d\_1c\geq d\_2$ because $t(n) \geq d\_1cf(n)$ might break along the way.
> 1 votes

# Answer
My opinion is that the $=$ sign should be interpreted as $\subset$ in the asymptotic complexity context. Consider the case when we write $n^2=\Omega(n)$. This is mentioned in CLRS's "Introduction to Algorithms", page 49.

Another point is that considering the definition of $\Omega$, it naturally hides constant coefficients inside, so you can show the "equality" easily by stating $c\_2=c\cdot c\_1$, defined as follows:

$\Omega(f)=\\{g|∃n\_0∈N,c\_2\>0∀n≥n0:c\_2f(n)≤g(n)\\}$, $\Omega(cf)=\\{g|∃n\_0∈N,c\_1\>0∀n≥n0:c\_1\cdot cf(n)≤g(n)\\}$.
> -1 votes

---
Tags: asymptotics, proof-techniques, check-my-proof
---


# Question
Title: Removing left-recursion in grammar while maintaining left-association of operator
I have a problem with this exercise:

> Let G be the following ambiguous grammar for the λ-calculus:
>
> `E → v | λv.E | EE | (E)`
>
> where E is the single non-terminal symbol, λv.E represents abstraction w.r.t. the variable v in E, and EE represents application.
>
> 1. Define an **LL(1)** grammar G′ such that L(G′) = L(G) and the ambiguity of G is resolved by imposing the following usual conventions:
>     1. abstraction is right associative;
>     2. application is left associative;
>     3. application has higher priority than abstraction.
> 2. Show the LL(1) parsing table for G′ and the parse tree obtained when parsing the string `λv1. λv2. v1v2v1`.

I eliminated ambiguity setting precedence and association, obtaining this grammar:

```
E -> EF | F
F -> λv.G | G
G -> (E) | v

```

which is not LL(1), since the production `E -> EF` is left recursive. However, eliminating left recursion from that production I obtain:

```
E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

```

that does not comply with requirement 1.2.

I looked for a solution on the Internet, but it seems like it is not possible to eliminate left-recursion preserving left associativity.

However, this exercise appeared on the compilers exam some years ago, so there must be a correct answer.

Thank you for your help.

# Answer
## Compatibility of left associativity and LL(1) parsing

You just hit one of the major inconsistencies in the use of context-free (CF) syntax. People want to choose grammars so that the parse-tree will reflect the intended structure of the sentence, close to its semantics, especially in the case of non associative operators, such as *application*. This was pretty much the original intent of CF grammars in linguistics. But at the same time they are constraining themselves to parsing technology that will tolerate only some types of grammars.

Indeed, if the parse-tree is to reflect the left associativity of an operator, then the grammar is necessarily left-recursive, since the top application node in the parse-tree is necessarily adding the rightmost term of non-parethesized successive applications.. So LL parsing is out of the question. You are right.

There are two ways out of this. One is not to rely on the parser to give the rigth "parse-tree" to be used for later stages of processing (such as reducing the lambda expression, here). This lead to the concept of Abstract Syntax Trees (AST) that can be built from the parse-tree, but with a different structure.

The other solution is to use more general parsing Techniques that will accept any CF grammar, and parse in accordance with it. General CF parsers is a well developed technology (and I do not cease to wonder why LL remains so popular).

I have no idea what could be considered a proper answer to these contradicting requirements.

What I would do is show they are contradicting requirements. Give a first grammar that meets the associativity and priority constraints, then transform the grammar into and LL(1) grammar for the parsing.

The fact that something appeared in a journal or on an exam is not a total garantee that it is correct. And I might be wrong too ... but I did some checking, in addition to my own knowledge of the issue.

## About this specific example

This being said, the first grammar you are suggesting does not seem quite correct. It does not have a way of producing λu.λv.v .

One trick to know is to start with operators (here abstraction or application) with the lowest priority (abstraction). It is the same for arithmetic expressions.
> 14 votes

# Answer
My attempt:

```
E  -> A | λv.E
A  -> FA'
A' -> A | ɛ
F  -> (E) | v

```

This grammar is LL(1) and should respect the required properties.
> 0 votes

---
Tags: context-free, formal-grammars, compilers, parsers
---


# Question
Title: How to generate response variable during machine learning?
I am analyzing data of insurance companies and for some reasons the data that was provided doesn't have any response variable of whether an insurance claim is legit or suspicious.

Are there any ways to generate the required response variable from the data that is available to us. I can think of clustering (hierarchical or K-means) as a means to identify clusters. But I am not sure if the clusters developed are true representation of my unreported response variable.

Also, Let me know of any other methods to generate response variable when there is none.

# Answer
> 4 votes
No. You can't. You need ground truth. You're asking "if I don't know which claims are fraudulent, can an algorithm somehow determine that for me?" The answer of course is no: the algorithm doesn't know anything more than you do about insurance fraud -- if anything, it knows even less.

This is one of the challenges with using machine learning. You typically need a lot of labelled data: data that has been labelled with ground truth (e.g., whether the insurance claim is legit or fraudulent). Supervised learning is data-driven: given some instances where we know the correct answer, it tries to figure out some rules to use to classify other instances where we don't know the answer. For this to work, it needs a training set of instances where we do know the correct answer.

Now there *are* some techniques that can be helpful. You might be able to use active learning to try to figure out claims to manually label, to try to reduce the number of examples you need to label. You might be able to use clustering to cluster the instances, and then hand-label a few instances from each cluster. But ultimately, you'll need some labelled instances to train on and evaluate the accuracy of your method.

See also How to identify labels in unsupervised learning? and Why is automatically labeling data in unsupervised learning hard? and What exactly is the difference between supervised and unsupervised learning? and What would be a decent threshold for classification problem?

# Answer
> 2 votes
> Let me know of any other methods to generate response variable when there is none

Anomaly detection techniques could be what you're looking for (but you don't *"generate response variable when there is none"*).

If you can assume that for the available dataset ($m$ examples, $n$ features):

$$x^{(1)}, \dots x^{(m)} \in \mathbb{R}^{n}$$

the features are gaussian:

$$x\_i \sim N(\mu\_i, \sigma\_i^2)$$

you can compute a *Density Estimation* ($p(x)$):

$$p(x) = \prod\_{j=1}^n p(x\_j; \mu\_j, \sigma\_j^2)$$

where

$$p(x\_j; \mu\_j, \sigma\_j^2) = \frac{1}{\sqrt{2 \pi} \sigma\_j} e^{-\frac{(x - \sigma)^2}{2 \sigma^2}}$$

*(this is the formula for independent features but, in practice, it works quite well even if the features are not independent)*

and classify a claim as being fraudulent when $p(x) \< \epsilon$.

The problem is that you need a good $\epsilon$ (threshold value).

You can split your data in:

* a **training set**. Ideally this shouldn't contain *anomalous* (fraudulent) data points, but if a few of them are present it isn't a big problem.
* a **cross validation set**. This should contain some known anomalous elements.

As you can see this is **not** *unsupervised anomaly detection*: you assume that the available data are legit and you add some examples of anomalous data for the cross validation set (of course you can also examine carefully the data and mark just a few examples).

The key points are:

1. for a random sample of insurance records a good share is probably legit (this is the reason that anomaly detection is frequently used for fraud detection);
2. you just need a **very small number** of examples which are known to be fraudulent (to be placed into the cross training set).

The training set is used to compute $\mu\_i$, $\sigma\_i$ and thus the *density estimation*. The "optimal" value of $\epsilon$ is the value that maximizes some evaluation metrics on the cross validation set. A simple evaluation metric is *F1-score* (data is very skewed and accuracy is not good).

This method can be adapted to non-gaussian features and features that have have some correlation with each other.

For a good introduction and further details take a look at week 7 of Andrew Ng's Machine Learning Class (and to Alex's notes).

---

There are also completely unsupervised anomaly detection techniques (they make the implicit assumption that normal instances are far more frequent than anomalies): k-NN Global Anomaly Score, Local outlier factor... (see Anomaly Detection : A Survey by Varun Chandola, Arindam Banerjee, Vipin Kumar).

Anyway for your kind of problem semi-supervised anomaly detection seems more promising.

---
Tags: machine-learning, data-mining
---


# Question
Title: Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?
I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be changed?

# Answer
It actually depends on the way you implement a k-tape Turing Machine as a single-tape one.

Using the standard implementation, you can prove that the single-tape machine will take quadratically more computation time.
> 0 votes

---
Tags: turing-machines, time-complexity, computation-models, simulation
---