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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.