Monash University
Browse

On the phenomenon of autocomputability

Download (114.59 kB)
report
posted on 2022-08-31, 02:57 authored by A Arslanov
Following Trakhtenbrot's concept of autoreducible set, we look at the general phenomenon of autocomputability of infinite binary sequences. We define another appropriate mathematical model of this concept: the strongly autoreducible set. For this purpose, we need to introduce a natural restricted form of wtt-reduction between sets: minimal weak truth table reduction. Then we prove several basic facts about strongly autoreducible sets.

History

Technical report number

2000/76

Year of publication

2000

Usage metrics

    Monash Information Technology Technical Reports

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC