New answers tagged


The encodings you mention are admissible. Why do you think they need to be bijections? In fact, there is no admissible numbering of partial computable maps that is a bijection. If there were one, we could decide equality if partial computable maps, which would allow us to implement the Halting oracle.


Any reasonable encoding will do. For example, you can imagine a version of C (or your favorite programming languages) in which integers are unbounded, and there is a reasonable input/output convention. Interpret $i \in \mathbb{N}$ as encoding a string $s_i$ in ASCII (in base 256). If $s_i$ is a valid C program, then it encodes some partially computable ...


Your problem is equivalent to numerical 3-dimensional matching and is NP-complete. It is listed under code SP16 in Computers and Intractability; A Guide to the Theory of NP-Completeness by Garey and Johnson.

Top 50 recent answers are included