Noncomputability and the Busy Beaver Problem (UMAP)

This module describes the Busy Beaver problem and explores the Busy Beaver and shift functions. It proves that these functions are noncomputable, relates them to each other and to the halting problem, reviews invetsigations of their values, and describes other noncomputable functions based on Turing machines.

Table of Contents:

INTRODUCTION

TURING MACHINES

THE BUSY BEAVER PROBLEM

NONCOMPUTABILITY OF ?(n) AND S(n)

RELATIONSHIP BETWEEN ?(n) AND S(n)

?(n), S(n), AND THE HALTING PROBLEM

VALUES OF ?(n) AND S(n)

CLASS M MACHINES

SEARCHING FOR BUSY BEAVER

MORE NONCOMPUTABLE FUNCTIONS
Maximum Is at Any Instant
Touring Turing Machines
The Number of Halting Machines

CONCLUSION

EXERCISES

SAMPLE EXAM

SOLUTIONS TO THE EXERCISES

SOLUTIONS TO THE SAMPLE EXAM

APPENDIX
Current Champion Five-State Machines
Larger Class M Machines

REFERENCES

ACKNOWLEDGMENTS

ABOUT THE AUTHOR