Free

# Ackermann's Function - Research Paper Example

Summary
As far as the computability theory is concerned, Ackermann function can be described as one of the earliest and simplest-discovered forms of the general computable function, which is not a primitive recursive. It is important to realize that often, all the primitive recursive…

## Extract of sample "Ackermann's Function"

Ackermann’s Function Ackermann’s Function OverviewAs far as the computability theory is concerned, Ackermann function can be described as one of the earliest and simplest-discovered forms of the general computable function, which is not a primitive recursive. It is important to realize that often, all the primitive recursive functions happen to be computable and total. However, the Ackermann’s function has often effectively illustrated that all the total computable function are not primitive recursive (Memon 2014); this function was developed by Wilhelm Ackermann, who is one of the renowned mathematicians, whose influence continues to be experienced in modern times.
How the algorithm works
After Ackermann made a publication of his particular function (having only three non-integer functions) a lot of efforts have been done by other authors in the process of modifying the function to apply to various situations, so that at present, this particular function can apply effectively to the numerous variants that comprise the very original function. One of the common versions of the Ackermann’s function is the Ackermann-Peter function, which is a two-argument, is often defined using the non-negative integers m and n as shown (Hazewinkel 2001). From the function below, one can easily deduce that the values are growing and expanding rapidly, even for the tiny inputs (Monin 2003). For instance, take A (4,2), and one can easily see that it is an integer comprising of about 19, 729 decimal digits.
Inefficiencies with the algorithm
Inasmuch as this function has been used widely with success, it has been termed as quite ineffective especially when it comes to computing complex numbers, making the process very slow. The complexity associated with this function often grows quite fast, especially when it comes to its memory and run-time. For this reason, it is often the best and widely used in the process of teaching learners some of the complex types of various recursions. Additionally, it is also used as a test case especially when it comes to compiler development used in optimizing recursions.
The numbers used in the illustration for the issue of A (4, n) seem to be quite large, such that one can describe the Ackermann’s function as being extremely slow especially when it comes to computing very large numbers (Sundblad 2003). Inasmuch as the numbers tend to grow very quickly, this function is often concerned with making recursions and subtractions. Following this realization, one can therefore devise some other shortcuts that can bring about another function deemed efficient and effective as shown.
Running time of the algorithm
The sequence of numbers as used in the Ackermann function has been classified as 1↑1, 2↑↑2, 3↑↑↑3, etc. in this regard, the nth number in the function is described as being n↑n(n = 1, 2, 3, ...), such that m↑kn becomes the Knuths up-arrow type or version of the particular Ackermann function.
From the above understanding, the initial numbers in the Ackermann functions thus becomes;
In the above illustration, a tower of titration can be seen clearly in the function’s middle layer. The final result has the layer which has tetrated 4’s whose maximum heights are equivalent to the total calculations as evidenced in the respective middle layer. It is important to realize that as far as size comparison is concerned, the expression 44 is already in above a googolplex, which means that the fourth number in the function will often be quite large.
Conclusion
In conclusion, we can note that from the above form of computing A (m, n) especially where m ≤ 3, it tends to become trivial. In such a case, the computations for m≥4 become quite easily done, additionally, it also becomes possible for A (4, 2) to run in the python format, something that later reveals a 19,000 digit answer (Rao 2012). In conclusion, it is possible to say that when computing A (4, 3), it is actually infeasible. Even when it comes to making optimizations, some of the most efficient computers can actually deplete their memories in attempting to compute these values effectively.
References
Hazewinkel, M. (2001), "Ackermann function", New York: Springer.
Memon, A. (2014). Advances in Computers. Burlington: Elsevier Science.
Monin, J. H (2003), Understanding Formal Methods, New York: Springer.
Rao, K. (2012). Discrete mathematics. Oxford, U.K.: Alpha Science International.
Sundblad, Y. (2003). "The Ackermann function. A theoretical, computational and formula manipulative study". BIT Numerical Mathematics. 11 (1): 107–119. Read More
Cite this document
• APA
• MLA
• CHICAGO
(“Ackermann's Function Research Paper Example | Topics and Well Written Essays - 500 words”, n.d.)
Ackermann's Function Research Paper Example | Topics and Well Written Essays - 500 words. Retrieved from https://studentshare.org/information-technology/1683303-ackermanns-function
(Ackermann'S Function Research Paper Example | Topics and Well Written Essays - 500 Words)
Ackermann'S Function Research Paper Example | Topics and Well Written Essays - 500 Words. https://studentshare.org/information-technology/1683303-ackermanns-function.
“Ackermann'S Function Research Paper Example | Topics and Well Written Essays - 500 Words”, n.d. https://studentshare.org/information-technology/1683303-ackermanns-function.
Click to create a comment or rate a document

## CHECK THESE SAMPLES OF Ackermann's Function

### Federal function

...? Running head: Federal function The federal government Federal government is a system in the UnitedStates where the autonomous republics of the fifty states are considered in one national government. The federal government is constituted of three cardinal branches: the judiciary, exercutive and the legislature which wields various powers as stipulated in the American constitution. The federal government has its headquarters at Washington D.C .The relationship between the state and the federal government is partial and in most cases the states enjoys certain degrees of autonomy. Current public problem. In the recent past, the federal government has been faced with a looming crisis in which it plans laying off about eight...
3 Pages(750 words)Essay

### Management Function and Organising Function

... Introduction In typical scenarios, earthquakes and other natural calamities have far reaching implications on the holistic functioning of the society. Besides leading to loss of life, these calamities culminate in destruction of property as well as important infrastructure. This was exemplified in the 2010 Haitian earthquake that led to significant loss of lives and property. Rescue initiatives were hampered by different factors including lack of sufficient infrastructure. In particular, the region had experienced extensive destruction of transport and communication facilities. The victims found it difficult to communicate important information to the rescuers so that relative initiatives could be effected. This made it difficult... of...
6 Pages(1500 words)Essay

### Linear Function

...Session Long Project Write a brief paper describing a linear function that comes from your own life. It should relate a particular 'thing' to another 'thing'. It could be something about the amount of money you spend, the number of minutes you spend on the phone, number of miles you run each day, number of push ups, etc... Life is mixture of all types of function. Every thing we do is related to some other thing in our life in one or other way, linearly or nonlinearly. As an example duration for which our phone work is inversely proportional to the number of minutes you spend on the phone. More time you spend on phone, less time the battery last. Again amount of water needed is directly proportional to...
2 Pages(500 words)Essay

### S

..., to push shifts in the development strategies of governments and international institutions, specifically, international financial institutions (IFIs). Whichever way shows direct inter-relationship between these international organisations and the international business. It is this relationship that concerns this paper. A. The International Monetary Fund, World Bank and the United Nations: Composition, roles and functions Believing that the main reasons for the two succeeding world wars were due to national economic disparities and trade conflict, and that unrestricted fair trade would bring about equal opportunity for the economic development of nation-states thereby eliminating the reasons for war (Hull, 1948, p....
12 Pages(3000 words)Essay

### Contemporary artists - Ackermann, Andre, Applebroog, Arevalo, Acconci

...Contemporary Artists Art is a fascinating the scope of which is beyond the limits of our imagination. Only an aesthetic mind person can obtain pleasure from the elegance of an art since it is highly associated with human emotions. So a good artist will always be an artistic mind person who finds beauty from all objects around him. However, such a person may not necessarily be an artist because creation of an art is something beyond that skill. Art and artists existed always from the very origin of human history to this electronic century. This paper will specifically discuss the achievements of some contemporary artists like Rita Ackermann, Carl Andre, Ida Applebroog, Javier Arevalo, and Vito Acconci who contributed much...
6 Pages(1500 words)Essay

### Compare and Contrast Speech treatment of dysarthria

.... Though, the studies discussed may have a variety of differences, it is apparent that all the articles strived in coming up with the appropriate speech therapy that could aid in improving the quality of life of the patients experiencing dysarthria. References Ackermann, H. & Ziegler, W. (1991). Articulatory Deficits in Parkinsonian Dysarthria: an Acoustic Analysis. Journal of Neurology, Neurosurgery and Psychiatry, 54, 1093-1098. Astrom, M., Tripoliti, E., Hariz, M.I., Zrinzo, L.U., Torres, I.M., Limousin, P. & Wardell, K. (2010). Patient-Specific Model-Based Investigation of Speech Intelligibility and Movement during Deep Brain Stimulation. Stereotactic and Functional Neurosurgery, 88,...
7 Pages(1750 words)Research Paper

### Revenue Budget(s)s

...Part 2 The changes in the surplus and deficit are attributed to the change in license system from an old style to a newer system. Part 3 If the number of vehicles failing inspection would increase then this would increase the revenue obtained from the vehicle inspection fees by an additional 15%. Therefore making standards tougher would result in more vehicles failing the inspection and subsequently lead to an increase in revenue. This would be beneficial to the organization. Part 4 a) If the new system is implemented at the beginning of the year, there would be higher deficits in general for that financial year. This is because the cost incurred by the organization in contracting outsiders for the licenses is much higher... 2 The changes in...
1 Pages(250 words)Case Study

### Job selection-multiple criteria decision analysis

.... DSS in action: Integrated application in a multi-criteria decision aid process. European Journal of Operational Research, 113:315–335, 1999. 6. A. Barcus and G. Montibeller. Supporting the allocation of software development work in distributed teams with multi-criteria decision analysis. Omega, 36:464–475, 2008. 7. V. Belton, F. Ackermann, and I. Shepherd. Integrated support from problem structuring through to alternative evaluation using COPE and VISA. Journal of Multi-Criteria Decision Analysis, 6:115–130, 1997. 8. S. Benartzi and R.H. Thaler. Risk aversion or myopia? Choices in repeated gambles and retirement investments. Management Science, 45(3):364–381, 1999. 9. P.L. Berger and T. Luckmann. The...
7 Pages(1750 words)Math Problem

### Polynomial function

... Nonic degree polynomial functions Introduction: Mathematics involves the solution of complex functions by utilizing different methods. Mathematics utilizes the polynomial expressions that consist of variable and coefficients that are correlated to each other through operation of addition, subtraction, multiplication and non negative exponent. The highest value of integer exponent determines the degree of polynomial expression. Nonic degree polynomial functions are those functions that have highest degree of 9. Consider the following equation: In this equation the highest degree of “x” is 9, this it is a polynomial function of degree 9. Now consider another equation: The addition of the highest degree of both x and y is 9, thus... it is a...
3 Pages(750 words)Assignment

### S&S Air Company

...S&S AIR COMPANY Internal growth rate= (Return on Asset x Retention ratio Return on Asset x Retention ratio) Return on Asset= 2,029,766/19,986,170=0.10 Retention ratio= 1-dividend pay-out; Dividend pay-out= 610,000/2,029,766=0.3 1-0.3=0.7 IGR= (0.1 X 0.3)/1-(0.1 X 0.3) 0.03/0.97=0.031 3.1% Sustainable Growth Rate= (Net income/ Shareholder’s equity) x (1-retention ratio) (2,029,766/11,435,815) x (1-0.7) 0.18 x 0.3=0.053 5.3% Internal growth rate: This percentage of (5.3%) is the maximum growth S&S Company can grow with external financial aid. Sustainable Growth rate: Refers to the growth rate a S&S Air company can grow...
1 Pages(250 words)Case Study