Quasihalt: Difference between revisions
Jump to navigation
Jump to search
(Created page with "A program is called '''quasihalting''' if it has any states which are reached no more than a fixed number of times during the course of a computation.<ref>https://www.sligocki.com/2021/03/06/beeping-busy-beaver/</ref> A machine is said to '''quasihalt''' when it ''enters'' a cycle of behavior in which it does not visit all machine states.<ref>https://nickdrozd.github.io/2020/10/08/quasihalting-behavior.html</ref><ref>https://discord.com/channels/960643023006490684/10265...") |
(No difference)
|
Latest revision as of 13:26, 10 July 2024
A program is called quasihalting if it has any states which are reached no more than a fixed number of times during the course of a computation.[1]
A machine is said to quasihalt when it enters a cycle of behavior in which it does not visit all machine states.[2][3][4]
Relationship with Beeping Busy Beavers
By introducing the concept of quasihalting, it becomes succinct and straightforward to define the Beeping Busy Beaver problem: "the Beeping Busy Beaver problem is to find the TM which runs longest before quasihalting."[5]
References
- ↑ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
- ↑ https://nickdrozd.github.io/2020/10/08/quasihalting-behavior.html
- ↑ https://discord.com/channels/960643023006490684/1026577255754903572/1034531129941819493
- ↑ https://discord.com/channels/960643023006490684/1026577255754903572/1034531417742385263
- ↑ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/