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

In summary, the person is looking for a non-trivial lower bound on the busy beaver function. They mention a result from Green (1964) that seems to have what they need, but they can't find the actual function. They ask for help locating the paper or for someone to communicate the result to them. They mention finding a piece by Julstrom in the 35th Annual Midwest Instruction and Computing Symposium papers that could be helpful.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
I was trying to find a non-trivial lower bound on the busy beaver ([itex]\Sigma[/itex]) 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 [itex]G_8(0)<\Sigma(8)[/itex].

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
  • #2
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.
 
  • #3


Hi there,

Thank you for sharing your experience in trying to find a lower bound on the busy beaver function. It can be frustrating when we come across references to papers or results that we are unable to access or understand fully. However, I believe I can offer some assistance in your search.

The paper by M. W. Green that you mentioned, "A lower bound on Rado's Sigma function for binary Turing machines", was published in the proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design in 1964. This symposium was organized by the Institute of Radio Engineers and held in Atlantic City, New Jersey from October 12-14, 1964.

After some digging, I was able to locate a copy of the proceedings online through the IEEE Xplore Digital Library. I have included the link below for your convenience. The paper you are looking for can be found on pages 91-94.

https://ieeexplore.ieee.org/document/1455349

I hope this helps in your search for the function you are looking for. If you have any further questions or need any additional assistance, please do not hesitate to reach out. Best of luck in your research!
 

1. What is the Sigma function and why is it important?

The Sigma function, denoted by σ, is a mathematical function that represents the sum of all positive divisors of a given integer. It is important because it has many applications in number theory, including in the study of prime numbers and perfect numbers.

2. Why is it difficult to find a lower bound on the Sigma function?

Finding a lower bound on the Sigma function is difficult because it involves finding the minimum value of the function for all possible input values, which can be a challenging task for large numbers.

3. What is the significance of Green's 1964 paper on finding a lower bound on the Sigma function?

Green's 1964 paper, "Lower Bounds for the Sigma Function", provided a groundbreaking method for finding a lower bound on the Sigma function. This method, known as the Green-Tao theorem, has been instrumental in solving many unsolved problems in number theory.

4. How does one use Green's method to find a lower bound on the Sigma function?

Green's method involves using a combination of analytical and combinatorial techniques to prove that the Sigma function is bounded below by a specific function. This is done by constructing a set of integers with certain properties and showing that the Sigma function of this set is larger than the desired lower bound.

5. Can Green's method be used to find other lower bounds on mathematical functions?

Yes, Green's method can be applied to other mathematical functions to find lower bounds. It has been used to find lower bounds on the number of prime numbers in a given interval and the number of solutions to certain polynomial equations. It is a powerful tool in number theory research.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
13
Views
250
Replies
5
Views
1K
  • Quantum Physics
Replies
1
Views
618
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
4K
Replies
1
Views
1K
  • Differential Equations
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
Replies
1
Views
6K
  • General Discussion
Replies
4
Views
643
Back
Top