encodability

Encodability is the property of representing objects from one formal system within another through a systematic encoding. It deals with translating elements such as data, programs, or proofs into a target medium so that the source's meaning or behavior is recoverable or observable in the target.

A typical encoding consists of a mapping from source to target and, when possible, a decoding mapping back. Correct or lossless encodings preserve semantics: for every source object s, decoding(E(s)) = s and the observable behavior is preserved. Efficiency considerations measure the overhead in time and space introduced by the encoding; strong encodability often seeks polytime encodings or bounded resource growth. Full abstraction is a stringent form where the encoding preserves and reflects all observable behaviors.

In computability and formal languages encodability is used to compare expressiveness and to transport known results via reductions. Gödel numbering encodes syntactic objects as natural numbers; one can encode Turing machines, lambda terms, or programs into strings or numbers. Reductions between decision problems transfer decidability properties and complexity classes.

In programming practice encodability underpins serialization formats and cross-language execution. Encodings enable interpreters and compilers to translate high-level constructs into lower-level representations, as in continuation-passing style, defunctionalization, or CPS-conversion. Data encodings such as JSON or binary formats facilitate storage and communication.

Limitations include potential overhead, loss of information (lossy encodings), and divergence of resource usage or side effects. Not every object is easily encodable with fixed bounds, and adversarial encodings can complicate analysis.