2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### What is the contribution of lambda calculus to the field of theory of computation?

$\lambda$-calculus has two key roles. It is a simple mathematical foundation of sequential, functional, higher-order computational behaviour. It is a representation of proofs in constructive logic. ...
• 10.3k
Accepted

### Are there any open problems left about DFAs?

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit. Let $u$ and $v$ be two distinct words with $|u|=|v|=n$. What is the size of the ...
• 7,558

### Single author papers against my advisor's will?

As a department chair, I can say you aren't alone. These situations come up all too often. Please do reach out to your department chair, graduate program director or grad student ombudsperson if your ...
• 8,546
Accepted

### What do you do when you cannot make progress on the problem you have been working on?

Is this a common situation that a researchers notices that her idea is not going to work after considerable amount of work? Yes. But as you get more experienced, you're able to "fail fast" - learn ...
• 31.7k

### Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems. However, they come at these problems from different angles and with different toolboxes. These ...
• 18.7k

### Are there any open problems left about DFAs?

Here's a very simple decision problem about DFA's. Given a DFA M, does M accept the base-2 representation of at least one prime number? Currently, we don't even know if this problem is recursively ...
• 6,898

### Are there any open problems left about DFAs?

The Černý conjecture is still open and important. It is about DFAs that have a synchronizing word (a word with the property that two copies of the automaton started in different states always end up ...
• 50.2k

### Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite ...
• 7,643

### What CS blogs should everyone read?

It might come as no surprise, but there is a substantial overlap between cstheory Q&A power-users and the blogosphere. We even had a dedicated blog for a while, with some great posts but it fell ...

### Is it sometimes better to not publish at all?

I was just referred to this question by graduate students that, in my opinion, were far too influenced by the answers. So let me start with two generic advises. To the aspiring scientist: Don't ...
Accepted

### How to find interesting research problems

I strongly disagree with the "find a list of open problems" approach. Usually open problems are quite hard to make progress on, and I'm thoroughly unconvinced that good research is done by tackling ...
• 13.1k

### What do you do when you cannot make progress on the problem you have been working on?

This is very common, and certainly frustrating. Here is my advice: Don't wait until you have a complete result to start writing. Maintain a TeX document with formal descriptions of your problem, ...
• 9,800

### Most memorable CS paper titles

I did a survey on Twitter about this a while back, results here. A few of my favorites: Parametric Polymorphism through Runtime Sealing, or, Theorems for Low, Low Prices! by Jacob Matthews and Amal ...
Accepted

### What are some good introductory books on type theory?

Software Foundations by Benjamin C. Pierce would be a good place to start. It would be a make a good precursor to his Types and Programming Languages. There is also Simon Thompson's Type Theory and ...
• 574
Accepted

### Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or ...
• 3,741
Accepted

### Who introduced nondeterministic computation?

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their ...
Accepted

First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is ...
• 35.6k

### Most memorable CS paper titles

I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny ...

### What is the contribution of lambda calculus to the field of theory of computation?

I think $\lambda$-calculus has contributed in many ways to this field, and still contributes to it. Three examples follow, and this is not exhaustive. Since I am not a specialist in $\lambda$-calculus,...
• 4,400
Accepted

### Is there any book on the philosophical implications of Theoretical Computer Science?

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" https://arxiv.org/abs/1108.1791
• 26.2k

### Single author papers against my advisor's will?

You should switch advisors. Since you are independently writing papers and have a track record, it should be possible to find a fair-minded theory advisor in a different technical area who is willing ...
• 6,650

### Algebra oriented branch of theoretical computer science

There have been recent developments in dependent type theory which relate type systems to homotopy types. This is now a relatively small field, but there is a lot of exciting work being done right ...
• 13.1k

### Algebra oriented branch of theoretical computer science

Algebraic geometry is used heavily in algebraic complexity theory and in particular in geometric complexity theory. Representation theory is also crucial for the latter, but it's even more useful when ...
• 35.6k

### Turing award papers

Yes, it happens that the work that merits the Turing award was pioneered or introduced in a single very influential paper. Sometimes, this is even explicitly the reason for the award. For example, in ...
• 842

### Are there any open problems left about DFAs?

Title: Intersection non-emptiness for two DFA's Description: Given two DFA's $D_1$ and $D_2$, does there exist a string $x$ such that $D_1$ and $D_2$ both accept $x$? Open Problem: Can we solve ...
• 4,900
Accepted

### Why was there a need for Martin-Löf to create intuitionistic type theory?

Very briefly: the simply-typed $\lambda$-calculus does not have dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from ...
• 10.3k

### Importance of single author papers?

In some fields (like e.g. Economics and Mathematics) single authored papers -are- a good thing to have when you go on the job market. In theoretical computer science, collaboration is much more common,...
• 9,800

### What is the contribution of lambda calculus to the field of theory of computation?

Apart from the foundational role of the $\lambda$-calculus, which was mentioned in all other answers, I would like to add something on What exactly did the lambda calculus do to advance the theory ...
• 4,783
Accepted

### Curious about computer-assisted NP-completeness proofs

As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant. Erickson and Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-...
You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...