Dynamic Turing Machine: model and properties for runtime code changes

• Autorzy: Rudy J.

Identyfikatory

DOI

10.7494/csci.2016.17.2.187

• Języki publikacji: EN

Abstrakty

EN

In this paper, a dynamic model of computation based on the Universal Turing Machine is proposed. This model is capable of applying runtime code modifications for 3-symbol deterministic Turing Machines at runtime and requires a decomposition of the simulated machine into parts called subtasks. The algorithm for performing runtime changes is considered, and the ability to apply runtime changes is studied through computer simulations. Theoretical properties of the proposed model, including computational power as well as time and space complexity, are studied and proven. Connections between the proposed model and Oracle Machines are discussed. Moreover, a possible method of implementation in real-life systems is proposed.

Słowa kluczowe

EN

computability theory; models of computation; Turing machine; runtime code changes

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2016
• Tom: Vol. 17 (2)
• Strony: 187--224
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Rudy J.

• Wroclaw University of Science and Technology, Department of Control Systems and Mechatronics, ul. Janiszewskiego 11–17, 50-372 Wrocław

Bibliografia

• 1. Arora S., Barak B.: Computational complexity: a modern approach. Cambridge University Press, 2009.
• 2. Chen H., Yu J., Chen R., Zang B., Yew P.C.: POLUS: A POwerful Live Updating System. In: Proceedings of the 29th International Conference on Software Engineering, ICSE ’07, pp. 271–281, IEEE Computer Society, Washington, DC, USA, 2007, ISBN 0-7695-2828-7, http://dx.doi.org/10.1109/ICSE.2007.65.
• 3. Cheng S.W., Garlan D., Schmerl B.R., Sousa J.a.P., Spitznagel B., Steenkiste P., 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, http://dl.acm.org/citation.cfm?id=648198.751340.
• 4. Cook S.A., Reckhow R.A.: Time bounded random access machines. Journal of Computer and System Sciences, vol. 7(4), pp. 354 – 375, 1973, ISSN 0022-0000, http://www.sciencedirect.com/science/article/pii/S0022000073800297.
• 5. Davis M.: The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication, 1965.
• 6. Dmitriev M.: Towards flexible and safe technology for runtime evolution of java language applications. In: In Proceedings of the Workshop on Engineering Complex Object-Oriented Systems for Evolution, in association with OOPSLA 2001 International Conference, 2001.
• 7. Elgot C.C., Robinson A.: Random-Access Stored-Program Machines, an Approach to Programming Languages. J. ACM, vol. 11(4), pp. 365–399, 1964, ISSN 0004-5411, http://doi.acm.org/10.1145/321239.321240.
• 8. Garlan D., Cheng S.W., Huang A.C., Schmerl B., Steenkiste P.: Rainbow: Architecture-Based Self-Adaptation with Reusable Infrastructure. Computer, vol. 37(10), pp. 46–54, 2004, ISSN 0018-9162, http://dx.doi.org/10.1109/MC.2004.175.
• 9. Hopcroft J., J.D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Cambridge, 1979.
• 10. Kleene S.C.: Recursive Predicates and Quantifiers. Transactions of the American Mathematical Society, vol. 53(1), pp. pp. 41–73, 1943, ISSN 00029947, http://www.jstor.org/stable/1990131.
• 11. Oreizy P., Medvidovic N., Taylor R.N.: Runtime Software Adaptation: Framework, Approaches, and Styles. In: Companion of the 30th International Conference on Software Engineering, ICSE Companion ’08, pp. 899–910, ACM, New York, NY, USA, 2008, ISBN 978-1-60558-079-1, http://doi.acm.org/10.1145/1370175.1370181.
• 12. Parra C., Blanc X., Cleve A., Duchien L.: Unifying Design and Runtime Software Adaptation Using Aspect Models. Sci. Comput. Program., vol. 76(12), pp. 1247–1260, 2011, ISSN 0167-6423, http://www.sciencedirect.com/science/article/pii/S0167642310002303, special Issue on Software Evolution, Adaptability and Variability.
• 13. Rudy J.: Performance and Overhead Analysis in Runtime Code Modification. Journal of Applied Computer Science, vol. 21(2), pp. 75–89, 2013.
• 14. Rudy J.: Turing machine approach to runtime software adaptation. Computer Science, vol. 15(3), pp. 293–310, 2014, ISSN 2300-7036.
• 15. Rudy J.: Dynamic Random-Access Stored-Program Machine for Runtime Code Modification. International Journal of Foundations of Computer Science, vol. 26(4), pp. 441–463, 2015, ISSN 0129-0541.
• 16. Turing A.: On Computable Numbers with an Application to the Entscheidungs Problem. Proc. London Mathematical Society, vol. 2(42), pp. 230–265, 1936.
• 17. 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, http://dl.acm.org/citation.cfm?id=646199.681826.
• 18. 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://doi.acm.org/10.1145/1837852.1621621.
• 19. 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, http://dl.acm.org/citation.cfm?id=950785.950888.
• 20. Zhang J., Cheng B.H.C.: Model-based Development of Dynamically Adaptive Software. In: Proceedings of the 28th International Conference on Software Engineering, ICSE ’06, pp. 371–380, ACM, New York, NY, USA, 2006, ISBN 1-59593-375-1, http://doi.acm.org/10.1145/1134285.1134337.
• 21. Zhang J., Cheng B.H.C., Yang Z., McKinley P.K.: Architecting Dependable Systems III. chap. Enabling Safe Dynamic Component-based Software Adaptation, pp. 194–211, Springer-Verlag, Berlin, Heidelberg, 2005, ISBN 3-540-28968-2, 978-3-540-28968-5, http://dl.acm.org/citation.cfm?id=2167692.2167703.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.