Undecidable Theories¶
Tarski, A., Mostowski, A., & Robinson, R. M. (1953). Undecidable Theories.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Embeddability
- Scheduling embeds events into time slots without resource conflict, so that interval scheduling and bin-packing existence are embeddability questions; cartography and political districting embed a partition of a territory into regions satisfying contiguity and population constraints; mathematical logic embeds one theory into another preserving inference structure (interpretability of theories); and linguistic phonotactics embeds a borrowed word into a language's permissible phoneme sequences, sometimes finding no embedding and forcing epenthesis or substitution.
This sourceDevelops interpretability — the embedding of one logical theory into another preserving inference structure — as a general method in proofs of undecidability.
- Scheduling embeds events into time slots without resource conflict, so that interval scheduling and bin-packing existence are embeddability questions; cartography and political districting embed a partition of a territory into regions satisfying contiguity and population constraints; mathematical logic embeds one theory into another preserving inference structure (interpretability of theories); and linguistic phonotactics embeds a borrowed word into a language's permissible phoneme sequences, sometimes finding no embedding and forcing epenthesis or substitution.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:a0ecc499730c · see in the full table