## Top new questions this week:

### What exactly is computation?

I know what computation is in some vague sense (i.e. it's the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of computation, computing, calculate, and ...

terminology computability

### Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...

reference-request automata optimization finite-automata transducers

### Standard definition of Turing machine

I have followed two famous book on "Automata and Formal Language Theory": Micheal Sipser's book Jeffrey Ullman and John Hopcroft's book in both books, tuple level definition of Turing machine ...

terminology turing-machines

### A metaphor for recursive enumerability

In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said "I ...

computability didactics

### Is weighted XOR-SAT NP-hard?

Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form ...

optimization np-hard satisfiability integer-programming xor

### Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking ...

algorithms search-algorithms

### How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

I'm trying to map a 12 digit number into a fixed width file. For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric ...

databases encoding-scheme base-conversion

## Greatest hits from previous weeks:

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le ... linear-programming integer-programming  asked by D.W. 12 votes  answered by D.W. 17 votes ### What determines the "speed" of a programming language? Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? ... programming-languages compilers  asked by Rodrigo Araújo Valente 22 votes  answered by babou 14 votes ## Can you answer these? ### What are the strongest known type systems for which inference is decidable? It's well known that Hindley-Milner type inference (the simply-typed$\lambda\$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...

undecidability type-theory type-inference dependent-types

### For a given certain situation how to prove that the system will never get into the state of Deadlock

The situation is as follows 'm' process shares 'n' resources of same type. The maximum need of each process does not exceed 'n' and the sum all their maximum needs is always less than m+n. In ...