Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example complexity of result of program $101$ after 3 steps is (5 + 1)*3 = 18. Have this or similar complexity measure been studied somewhere? What's its name?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.