The Post Correspondence Programming Language: Domino-Oriented Programming (davidlazar.github.io)

49 points by 14113 10y ago ↗ HN

4 comments

[ 2.8 ms ] story [ 21.6 ms ] thread

spb 10y ago ↗

What are the practical implications and applications of this?

It shows that there are some problems (eg PCP), that are literally impossible to solve for every case. If you were able to come up with an algorithm that could do so, you would've found a solution to the halting problem, which we know is impossible. Other than that, it's just some person having fun compiling between two different esoteric programming languages.

tomerv 10y ago ↗

If you find this interesting, take a look at FRACTRAN[1].

[1] https://en.wikipedia.org/wiki/FRACTRAN

gue5t 10y ago ↗

I was terribly confused because I thought this was referring to Post's Correspondence Principle: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.380....

This concerns instead the Post Correspondence Problem: https://en.wikipedia.org/wiki/Post_correspondence_problem

Surprising namespace clash!