# Selected Problems in Computability

Nov 1, 2006 · peterb · 1 minute readComputers

Sometimes, we do hardcore research in computer science. It’s in our blood.
Here are some of the papers we have submitted to various academic journals at
the moment. 10. The Travelling Salsman problem *(peterb)*

9. Mutual Exclusion in the Men’s Room *(psu)*

8. “Given a description of a program and a finite input, decide whether the
program is a lousy piece of fucking garbage.” Also known as the Hating
problem. *(peterb)*

7. Compute the value of pie to an arbitrary number of diners. *(peterb)*

6. Finding an assignment of substitute teachers that makes any 3 variable
logical formulae true, also known as 3SUB *(psu)*

5. For any non-trivial property of partial functions, the question of whether
a given algorithm computes a partial function with this property is
irritating. *(peterb)*

4. The Unstable Marriage problem *(psu)*

3. Redundant Array of Idiot Developers *(peterb, with props to sdavis for the
assist)*

2. All Cretans are liars. No, seriously. Have you ever been to Crete? I mean,
Jesus. *(peterb)*

1. Automatic Path planning in hostile environments: the Blood Gulch case
study *(psu)*

0. The Speculative Dining Philosopher’s Problem: Eat dessert first. *(psu)*