# Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, and the Machines that represent the software which actually gets designed and implemented, say $M_\alpha$ and $M_\beta$, respectively.

Specifically, my interest is in examining limitations (due to Rice's Theorem for instance) in automated detection of errors in software programs between the Language processed by the ideal machine, and the language processed by the developed/implemented Machines.

Any reference to prior work that works with some notions of exploring differences between two specified Turing Machines, or barring that a lower level Formal Language would be extremely helpful and appreciated; because i'd rather cite than write :-).

• Sounds like model-based testing. One develops a model of the desired system and then uses this to generate tests for the actual system. Dec 14 '11 at 7:24
• @DaveClarke thank you for the cross-reference to model-based testing, it should've occurred to me there are definite benefits to looking at model-based testing ... i wonder if i start with just FSA and build up i may be able to utilize a lot of the existing theory on fault modelling. (just thinking out loud) Dec 14 '11 at 9:35
• I'd also look at the theories of program refinement and the refinement calculus. R.-J. Back and J. von Wright have developed this theory. In the world of concurrent programming, there is the related concept of action refinement. Dec 14 '11 at 14:57
• @MartinBerger thank you for the suggestion of looking into action refinement. Specifically Action Refinement in Process Algebra and Security Issues dsi.unive.it/~srossi/Papers/lopstr07.pdf was an interesting find for sure! Dec 16 '11 at 15:16
• General update: The technical report "Attack Modeling for Information Security and Survivability" by Moore, A.P. and Ellison, R.J. and Linger, R.C.; provides a good starting basis. P.S. I may end up posting an answer to my own question as derived by all the wonderful suggestions by everyone.. Is that usual? Dec 16 '11 at 15:21