Quasihalt
Jump to navigation
Jump to search
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/