Turing machine approach to runtime software adaptation

• Autorzy: Rudy J.

Identyfikatory

DOI

10.7494/csci.2014.15.3.293 293

• Języki publikacji: EN

Abstrakty

EN

In this paper, the problem of applying changes to software at runtime is considered. The computability theory is used in order to develop a more general and programming-language-independent model of computation with support for runtime changes. Various types of runtime changes were defined in terms of computable functions and Turing machines. The properties of such functions and machines were used to prove that arbitrary runtime changes on Turing machines are impossible in general cases. A method of Turing machine decomposition into subtasks was presented and runtime changes were defined through transformations of the subtask graph. Requirements for the possible changes were considered with regard to the possibility of subtask execution during such changes. Finally, a runtime change model of computation was defined by extension of the Universal Turing Machine.

Słowa kluczowe

EN

runtime change; dynamic modification; computability theory; turing machines

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2014
• Tom: Vol. 15 (3)
• Strony: 293--310
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Rudy J.

• Institute of Computer Engineering, Control and Robotics, Wrocław University of Technology, Janiszewskiego 11–17, 50-372 Wrocław, Poland

Bibliografia

• [1] Bennett C. H.: Logical Reversibility of Computation. IBM J. Res. Dev., vol. 17 (6), pp. 525–532, 1973. ISSN 0018-8646. http://dx.doi.org/10.1147/rd.176.0525.
• [2] Church A.: An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, vol. 58n(2), pp. 345–363, 1936. ISSN 00029327. http://dx.doi.org/10.2307/2371045.
• [3] Hopcroft J., J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Cambridge, 1979.
• [4] Kleene S. C.: Introduction to Metamathematics. North Holland, 1952.
• [5] Mukhija A., Glinz M.: Runtime Adaptation of Applications Through Dynamic Recomposition of Components. In: Proceedings of the 18th International Conference on Architecture of Computing Systems Conference on Systems Aspects in Organic and Pervasive Computing, ARCS’05, pp. 124–138. Springer-Verlag, Berlin, Heidelberg, 2005. ISBN 3-540-25273-8, 978-3-540-25273-3. http://dx.doi.org/10.1007/978-3-540-31967-2_9.
• [6] Rosser B.: An Informal Exposition of Proofs of G ̈odel’s Theorems and Church’s Theorem. The Journal of Symbolic Logic, vol. 4 (2), 1939. ISSN 00224812. http://dx.doi.org/10.2307/2269059.
• [7] Rudy J.: Runtime software adaptation: approaches and a programming tool. Journal of Theoretical and Applied Computer Science, vol. 6 (1), pp. 75–89, 2012. ISSN 2299-2634.
• [8] Turing A.: On Computable Numbers with an Application to the Entscheidungs Problem. In: Proc. London Mathematical Society, vol. 2 (42), pp. 230–265, 1936.
• [9] Valetto G., Kaiser G.: A Case Study in Software Adaptation. In: Proceedings of the First Workshop on Self-healing Systems, WOSS ’02, pp. 73–78. ACM, New York, NY, USA, 2002. ISBN 1-58113-609-9. http://dx.doi.org/10.1145/582128.582142.
• [10] Valetto G., Kaiser G. E., Kc G. S.: A Mobile Agent Approach to Process-Based Dynamic Adaptation of Complex Software Systems. In: Proceedings of the 8th European Workshop on Software Process Technology, EWSPT ’01, pp. 102–116. Springer-Verlag, London, UK, UK, 2001. ISBN 3-540-42264-1.
• [11] Villazón A., Binder W., Ansaloni D., Moret P.: Advanced Runtime Adaptation for Java. SIGPLAN Not., vol. 45 (2), pp. 85–94, 2009. ISSN 0362-1340. http://dx.doi.org/10.1145/1837852.1621621.
• [12] Wang Q., Huang G., Shen J., Mei H., Yang F.: Runtime Software Architecture Based Software Online Evolution. In: Proceedings of the 27th Annual International Conference on Computer Software and Applications, COMPSAC ’03, pp. 230–. IEEE Computer Society, Washington, DC, USA, 2003. ISBN 0-7695-2020-0