New answers tagged

2

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.


1

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 ...


3

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