Minimum-complexity pairing functions

摘要

Pairing functions are bijections from N x N to N, and they are important in logic, computing, and mathematics on the whole. We exhibit the first known pairing function 〈 ·, ·〉 which is computable in linear time and constant space. In fact, both 〈·, ·〉 and its inverse are computable by finite-state transducers which run in real time. By contrast, the familiar examples of pairing functions in the literature are computable in linear time if and only if integer multiplication can be accomplished in linear time, which is considered doubtful by many. We also present two kinds of monotone pairing functions which are computable on-line in linear time and log space; the first is also computable off-line in zero space. We conjecture that every monotone pairing function requires log space to compute on-line.