thoughts of heck

I’ve been a software engineer, and some days I’ve written unit tests during my work. So I was on my first semester in my Masters and revisited Turing machines. One time we had a final exam on it, and I had a colleague who teaches programming, and wondered how they would check all the code submissions. I suggested maybe they can write unit tests, just like how Turing deciders halt and decide if an input is rejected or not.

Huh, a unit test is a Turing decider. It made sense.

Unit tests are programs that run to test the code per “unit”, or per action. Turing Deciders, on the other hand, are a type of Turing machine that always stops. A Turing machine is simply an abstract machine but I wouldn’t go over explaining it further. Just imagine a machine that takes an input and always stops with a result of accept or reject.

Unit tests call a function with a sample input, and if the output is expected then the test passes, otherwise it fails. The definition of a Turing decider is also similar. A Turing decider has an input string, and it decides whether the string is a member of a predefined formal language (hence the name “decider”).

If a unit test is a Turing decider, then what is the formal language of a unit test? The input of a unit test is the testable code, not the sample input. I have no idea if this is plausible but, is the formal language of a unit test the set of accepted implementations of the requirement? The set of multiple character arrangements of code that return what is expected?

Another interesting thing is unit tests also emulate the halting problem (well technically, all programs do anyway). The halting problem is the problem of finding out if the program will run forever, and it turns out, no program can identify another program if it can run forever. If you try to create a program that checks if another program runs forever, it also runs forever, therefore never actually checking.

In current computers this comes in the form of a finite stack, where, if the stack gets filled by the program, it creates a stack overflow problem and would halt. The computer does not know for sure whether the program is running endlessly, just that it provided a finite amount of space to determine if the program should be halted or not.

This also happened in one of the unit tests I ran. The unit test got stuck with no outputs, just running endlessly, which turned out to be the program also running endlessly.

I suppose those are all my musings. I still have the lingering question of what the formal language of unit tests are.