Skip to main content

Consortium for Mathematics and its Applications

Product ID: 99728
Supplementary Print
Undergraduate

Noncomputability and the Busy Beaver Problem (UMAP)

Author: Bryant A. Julstrom


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

©1999 by COMAP, Inc.
UMAP Module
36 pages

Mathematics Topics:

Computer Science , Analysis

Application Areas:

Computers & Technology

Prerequisites:

Familiarity with finite state machines

You must have a Full Membership to download this resource.

If you're already a member, login here.

Not yet a member?