Finding a Lower Bound on $\Sigma$ Function w/Green(1964)

  • Context: Graduate 
  • Thread starter Thread starter CRGreathouse
  • Start date Start date
  • Tags Tags
    Bound Function
Click For Summary
SUMMARY

The discussion centers on finding a non-trivial lower bound for the busy beaver (\Sigma) function, specifically referencing M. W. Green's 1964 paper titled "A lower bound on Rado's Sigma function for binary Turing machines." The participant seeks the actual function from the paper, as existing references only provide the value for G_8(0) < \Sigma(8). Additionally, they mention a potentially relevant piece by Julstrom from the 35th Annual Midwest Instruction and Computing Symposium that may provide insights into Green's work.

PREREQUISITES
  • Understanding of the busy beaver function and its significance in computability theory.
  • Familiarity with binary Turing machines and their operational principles.
  • Knowledge of mathematical logic and lower bounds in computational complexity.
  • Access to academic papers and the ability to interpret research findings.
NEXT STEPS
  • Locate and review M. W. Green's 1964 paper on the lower bound of the \Sigma function.
  • Examine Julstrom's work on "Ackermann's Function in the Numbers of 1s Generated by Green's Machines."
  • Research the implications of lower bounds in computability and complexity theory.
  • Explore additional literature on the busy beaver problem and its historical context.
USEFUL FOR

This discussion is beneficial for theoretical computer scientists, mathematicians specializing in computability theory, and researchers interested in the complexities of Turing machines and the busy beaver function.

CRGreathouse
Science Advisor
Homework Helper
Messages
2,832
Reaction score
0
I was trying to find a non-trivial lower bound on the busy beaver (\Sigma) function, but I haven't been able to find the function I want. A result of Green (1964, see below) appears to have what I want, but I've never seen the actual function -- all references I have just mention the value for G_8(0)&lt;\Sigma(8).

Can anyone here help me locate this paper (given the reference), or alternately communicate the result to me? The paper is only four pages long, so that's an upper bound on the complexity of the function. :biggrin: Thanks.

M. W. Green. "A lower bound on Rado's Sigma function for binary Turing machines". Switching Circut Theory and Logical Design, Proceedings of the Fifth Annual Symposium (1964), pp. 91-94.
 
Physics news on Phys.org
I may have found something in the 35th Annual Midwest Instruction and Computing Symposium papers. There's a piece by Julstrom called "Ackermann's Function in the Numbers of 1s Generated by Green's Machines" that looks promising.
 

Similar threads

To find the boundedness of a given function
  • · Replies 14 ·
Replies
14
Views
4K
Undergrad Finding the derivative of a characteristic function
  • · Replies 5 ·
Replies
5
Views
3K
Graduate Correct Form of Likelihood Function for Data w/ Upper/Lower Bound
  • · Replies 8 ·
Replies
8
Views
5K
Graduate Calculating nonequilibrium Green's Functions
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Green function issue: can bound. cond. be applied mode-wise?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate A question about Green's function
  • · Replies 2 ·
Replies
2
Views
2K
Upper and lower bounds of a triple integral
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Quadratic lower/upper bound of a function
  • · Replies 1 ·
Replies
1
Views
6K
Finding k in a probability density function
  • · Replies 4 ·
Replies
4
Views
4K
Graduate Finding a Green Function for y''+1/24y=f(x) with Bounded Conditions | Math Help
  • · Replies 4 ·
Replies
4
Views
3K