PreprintCC BY 4.0arXiv
Bellman's Forest Problem and Computability
Abstract
The goal of this paper is to refine methods in computable analysis and to employ them in the study of solutions of an optimization problem posed by Bellman. This problem asks how to find optimal (shortest) paths which do not fit into given plane figures. We show that each instance of Bellman's problem has an arbitrarily small uniformly computable perturbation for which the minimal length of path is computable, and thus the class of optimal paths is a Π10 class, and there are uniformly computable paths which escape with arbitrarily small length greater than the minimum possible.
Related
- Bellman--Shoreline Search in Arbitrary Dimension: Exponential Vector Oscillators, Active Memory, Precession, and Effective Computability
- Bellman Search in Arbitrary Finite Dimension: A Self-Similar Cell Theorem and Effective Computability of Planar Shoreline Search
- Closed escape path of smallest diameter in forest: dual formulation of Lebesgue's universal covering problem
- Uniform Computability of Isotypic Block Diagonalization for Finite-Group Representations
- Turing universality, computability, and incompleteness in hypergraph Turán theory
BibTeX
@misc{canel2026bellmans,
title = {{Bellman's Forest Problem and Computability}},
author = {Jacob Canel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31352},
eprint = {2609.31352},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31352},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bellman's Forest Problem and Computability
AU - Jacob Canel
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31352
UR - https://arxiv.org/abs/2609.31352
AB - The goal of this paper is to refine methods in computable analysis and to employ them in the study of solutions of an optimization problem posed by Bellman. This problem asks how to find optimal (shortest) paths which do not fit into given plane figures. We show that each instance of Bellman's problem has an arbitrarily small uniformly computable perturbation for which the minimal length of path is computable, and thus the class of optimal paths is a Π_1^0 class, and there are uniformly computable paths which escape with arbitrarily small length greater than the minimum possible.
ER -