Turing machine approach to runtime software adaptation

Jarosław Rudy

doi:10.7494/csci.2014.15.3.293

Authors

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

DOI:

https://doi.org/10.7494/csci.2014.15.3.293

Keywords:

runtime changes, dynamic modification, computability theory, Turing machines

Abstract

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.

Downloads

Download data is not yet available.

References

Cheng S.W., Garlan D., Schmerl B.R., Sousa J.a.P., Spitznagel B., Steenkiste P., and Hu N.: Software Architecture-Based Adaptation for Pervasive Systems. In: Proceedings of the International Conference on Architecture of Computing Systems: Trends in Network and Pervasive Computing, ARCS ’02, pp. 67–82. Springer-Verlag, London, UK, UK, 2002. ISBN 3-540-43409-7. URL http://dl. acm.org/citation.cfm?id=648198.751340.

Garlan D. and Schmerl B.: Model-based Adaptation for Self-healing Systems. In: Proceedings of the First Workshop on Self-healing Systems, WOSS ’02, pp. 27–32. ACM, New York, NY, USA, 2002. ISBN 1-58113-609-9. URL http: //dx.doi.org/10.1145/582128.582134.

Hopcroft J. and J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Cambridge, 1979. [4] Mukhija A. and 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. URL http://dx.doi.org/10.1007/978-3-540-31967-2_9.

Rosser B.: An Informal Exposition of Proofs of Godel's Theorems and Church’s Theorem. The Journal of Symbolic Logic, vol. 4(2), 1939. ISSN 00224812. URL http://dx.doi.org/10.2307/2269059.

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.

Taylor R., Medvidovic N., and Oreizy P.: Architectural styles for runtime software adaptation. In: Software Architecture, 2009 European Conference on Software Architecture. WICSA/ECSA 2009. Joint Working IEEE/IFIP Conference on, pp. 171–180. 2009. URL http://dx.doi.org/10.1109/WICSA.2009.5290803.

Valetto G. and 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. URL http://dx.doi.org/10.1145/582128.582142.

Valetto G. and Kaiser G.: Using Process Technology to Control and Coordinate Software Adaptation. In: Proceedings of the 25th International Conference on Software Engineering, ICSE ’03, pp. 262–272. IEEE Computer Society, Washington, DC, USA, 2003. ISBN 0-7695-1877-X. URL http://dl.acm.org/citation.cfm?id=776816.776848.

Valetto G., Kaiser G.E., and 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. URL http://dl.acm.org/citation.cfm?id=646199.681826.

Villazon A., Binder W., Ansaloni D., and Moret P.: Advanced Runtime Adaptation for Java. SIGPLAN Not., vol. 45(2), pp. 85–94, 2009. ISSN 0362-1340. URL http://dx.doi.org/10.1145/1837852.1621621.

Wang Q., Huang G., Shen J., Mei H., and 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. URL http://dl.acm.orgcitation.cfm?id=950785.950888.