Selected Problems in Computability

On November 1, 2006, in Computers, by peterb

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)

 

4 Responses to “Selected Problems in Computability”

  1. I went to Dundee, Scotland in 2000 for the Instil (Integrating Speech Technology in Language Learning) symposium there, and Beijing in 2004 as a tourist. Other than that it’s been mostly Mountain View, Menlo Park, or San Mateo. I can’t believe you stayed in Pittsburgh.

  2. P.S. In 2000-2001 I would spend 1-2 weeks per month in Mission Viejo.

  3. Tim F says:

    ViTRioL: Toward a Standard Grammar for Delineating How My Choice of Programming Language Plus Rigorous Discipline and Best Practices Beats Hands Down Your Choice Plus Ignorance and Sloppiness Through an Obviously Contrived Example and Pointless Insistence on Maintaining Semantics (Draft)

  4. Tim F says:

    Open Brace at the End of This Line vs. at the Start of the Next Line: My Brilliant Opinion that I’m So Sure Will Settle This Now and Forever