According to Wikipedia, P′′ is a "primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines." P′′ contains only four instructions has influenced languages such as Brainfuck.

While a modern interpreter would not be too difficult to write (I'm debating tackling it as a weekend project myself), are there any modern P′′ interpreters? What about references to the original source code/interpreter from the '60s?


The original Böhm paper itself is hard to find (see for example How to prove the structured program theorem?), let alone the original interpreter from the 60s...

However, the esoteric programming languages wiki has an implementation of a P′′ interpreter in Haskell, on the P′′ page.

  • 1
    Is it possible that Böhm never implemented the interpreter? I imagine that as time on a computer was limited and expensive, he never bothered. Afterall, he didn't need to if this was really an academic exercise.
    – OmarL
    Oct 20 '16 at 10:26
  • 1
    @Wilson I wondered about that, it could be that the language is just a thought experiment to support the proof of the theorem; reading the original paper might give better insight. Oct 20 '16 at 12:44
  • It would be great to see that original paper. Is it not available to the public?
    – JAL
    Oct 20 '16 at 18:41
  • I haven't found it; it's not on the ACM DL at least, and the various citation sites only mention citations of it, not the original. I haven't looked through bitsavers yet... Oct 21 '16 at 15:12
  • 1
    It might be available from a number of libraries. It doesn't seem to be online anywhere or in any currently-available reprint. Oct 24 '16 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.