Quasihalt

From BusyBeaverWiki
Revision as of 13:26, 10 July 2024 by Hsjoihs (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

  1. ↑ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
  2. ↑ https://nickdrozd.github.io/2020/10/08/quasihalting-behavior.html
  3. ↑ https://discord.com/channels/960643023006490684/1026577255754903572/1034531129941819493
  4. ↑ https://discord.com/channels/960643023006490684/1026577255754903572/1034531417742385263
  5. ↑ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Quasihalt&oldid=369"