A guided tour of minimal indices and shortest descriptions

DOI10.1007/S001530050112zbMath0910.03037OpenAlexW2085799383MaRDI QIDQ1127831

Marcus Schaefer

Publication date: 10 August 1998

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001530050112

zbMATH Keywords

minimal indicescomputabilityopen problemsGödel numberingMINdescriptionsbtt-reductionssize of programs

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Gödel numberings and issues of incompleteness (03F40)

Related Items (7)

On the Turing degrees of minimal index sets ⋮ An incomplete set of shortest descriptions ⋮ Index Sets and Universal Numberings ⋮ Index sets and universal numberings ⋮ Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs ⋮ On the degrees of constructively immune sets

This page was built for publication: A guided tour of minimal indices and shortest descriptions