Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.02764 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916880652959744 |
|---|---|
| author | Doubrovinski, Konstantin |
| author_facet | Doubrovinski, Konstantin |
| contents | The informal question of when two theorem proofs are "essentially the same" goes back to David Hilbert, who considered adding it (or something largely equivalent) to his famous list of open problems, but eventually decided to leave it out. Given that the notion of a formal proof is closely related to that of a (computer) program, i.e. a recursive function, it may be useful to ask the same question with regard to programs instead. Here we propose a minimalistic approach to this question within Recursion Theory, building heavily on the use of Kolmogorov Complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When are two algorithms the same? Towards addressing Hilbert's 24th problem Doubrovinski, Konstantin Logic in Computer Science The informal question of when two theorem proofs are "essentially the same" goes back to David Hilbert, who considered adding it (or something largely equivalent) to his famous list of open problems, but eventually decided to leave it out. Given that the notion of a formal proof is closely related to that of a (computer) program, i.e. a recursive function, it may be useful to ask the same question with regard to programs instead. Here we propose a minimalistic approach to this question within Recursion Theory, building heavily on the use of Kolmogorov Complexity. |
| title | When are two algorithms the same? Towards addressing Hilbert's 24th problem |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2508.02764 |