Busy Beaver Computation Using Quantum Algorithms

A guided research project in Algorithms & Discrete Mathematics.

← Algorithms & Discrete Mathematics projects

Experience Research Algorithms & Discrete Mathematics

Question

Can quantum search ideas help explore small machines with extremely long halting times?

The bounded experiment is computable, even though the general Busy Beaver problem is not.
The bounded experiment is computable, even though the general Busy Beaver problem is not.

Goals

  • Encode and test small Turing machines in a bounded search.
  • Compare a classical search with a quantum-search formulation.

Method

Search a finite set of small machines while treating halting within a chosen limit as the test.

  • Enumerate machine descriptions and simulate each one for a bounded number of steps.
  • Formulate the test as an oracle for amplitude amplification.
  • Compare query counts and verify all candidate record holders classically.