Properties of Ackermann's function

In summary: Could I improve something? (Wondering)In summary, the conversation discusses the properties of Ackermann's function, including its value compared to its inputs, and how it relates to other functions. The conversation also includes discussions on how to formally prove these properties through induction on various variables.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

I want to show the following properties of Ackermann's function:

  1. .
  2. .
  3. If , then .
  4. .
  5. .
  6. If , then .
  7. .
I have done the following:

  1. Induction on .
  2. Induction on .
    Base case: For we have , by the definition of .

    Inductive hypothesis: We assume that it holds for , that means (I.H.x)

    Inductive step: We want to show that .
    By the definition of and by the property we have .

  3. Induction on .
    Base case: For we have .

    Inductive hypothesis: We assume that it holds for , that means (I.H.)

    Inductive step: We want to show that .
    By the definition we have . By the (I.H.) and the property we have . By the property we have . So, we cocnlude that .
  4. By the property we have . So, we have .
    But how can we prove this formally??

  5. Induction on .
    Base case: For we have by the property .

    Inductive hypothesis: We assume that it holds for , that means (I.H.)

    Inductive step: We want to show that .
    By the definition of we have . By the (I.H.) we have . By the property we have . By the property we have According to the property , or equivalently . By the property we have . So, .

Is this correct?? Could I improve something?? (Wondering)

Could you give me some hints to prove the properties ?? (Wondering)
 
Physics news on Phys.org
  • #2
At the proof of the properties and do we use the properties and respectively?

But how? (Wondering)

For example, for the property would the proof be as follows?

Induction on .

Base case: For we have

Inductive hypothesis: We assume that it holds for , that means (I.H)

Inductive step: We want to show that .

How can we continue?
 
  • #3
I tried again to prove the property :



Induction on .

Base case: For we have .

Inductive hypothesis: We assume that it holds for , that means that (I.H.)

Inductive step: We want to show that
Is this correct? Could I improve something? (Wondering)

The proof of the property is similiar, isn't it?

On which variable do we use the induction for the property ?
 
  • #4
For the property do we do the following?

We will show that by induction on . Base case: For we have , so .

Inductive hypothesis: We assume that it stands for , . (I.H.)

Inductive step: We will show that it stands for , , that means that .
We have that .
. So, we have that . Is this correct?
 

FAQ: Properties of Ackermann's function

What is Ackermann's function?

Ackermann's function is a mathematical function that is used to show the growth rate of certain algorithms. It was first introduced by Wilhelm Ackermann in 1928.

What are the properties of Ackermann's function?

The properties of Ackermann's function include being a total computable function, being a non-primitive recursive function, and having extremely fast-growing values as the inputs increase.

Why is Ackermann's function important?

Ackermann's function is important because it can be used to compare the efficiency of different algorithms and to analyze the growth rate of certain problems. It is also a fundamental example in the study of computability and complexity theory.

What is the time complexity of Ackermann's function?

The time complexity of Ackermann's function is extremely high, with a runtime that grows faster than any polynomial function. It is often used as a benchmark for comparing the efficiency of different algorithms.

Can Ackermann's function be computed for all inputs?

No, Ackermann's function is not defined for all inputs. It is only defined for non-negative integer inputs. As the inputs increase, the values of the function grow extremely quickly and eventually exceed the capacity of any computer to compute.

Back
Top