On Higher Order Busy Beaver Function
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909709895729152 |
|---|---|
| author | Cao, Zining |
| author_facet | Cao, Zining |
| contents | In this paper, we extend Busy Beaver function to a class of higher order Busy Beaver functions based on Turing oracle machine. We prove some results about the relation between decidability of number theoretical formula and higher order Busy Beaver functions, and the relation between computability of max-min partial recursive functions and higher order Busy Beaver functions. We also present some conjectures on higher order Busy Beaver functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20321 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Higher Order Busy Beaver Function Cao, Zining Computational Complexity Formal Languages and Automata Theory Logic in Computer Science In this paper, we extend Busy Beaver function to a class of higher order Busy Beaver functions based on Turing oracle machine. We prove some results about the relation between decidability of number theoretical formula and higher order Busy Beaver functions, and the relation between computability of max-min partial recursive functions and higher order Busy Beaver functions. We also present some conjectures on higher order Busy Beaver functions. |
| title | On Higher Order Busy Beaver Function |
| topic | Computational Complexity Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2507.20321 |