I actually ended up spending some time thinking about Turing machines when trying to solve a LeetCode problem.
I like to have a handful of problems that (1) have known solutions, (2) that I should be able to figure out in a reasonable time, (3) and that I should be able to make significant progress on entirely in my head. I then work on these when lying in bed trying to fall asleep, or when exercising, and similar times, and LeetCode is a good source for such problems.
The problem was given an array of integers find the smallest positive integer that is not in the array, and do it in O(N) time and O(1) space.
The O(1) space part was killing me. I just could not do it in less than O(N).
I decided to spend a while trying to prove that it could not be done in O(1) space. Presumably that would fail, but maybe if I could figure out why it failed that would also suggest how to do it in O(1) space. And thus I ended up thinking about Turing machines and other models of computation.
Except my attempts to prove it cannot be done on O(1) space seemed to succeed, so I was stumped. I spent a couple months on this stupid problem, before finally giving in and peeking at a solution.
It turns out that on LeetCode you can modify input arrays. I'm not a barbarian so I had assumed that inputs were supposed to be immutable.
I like to have a handful of problems that (1) have known solutions, (2) that I should be able to figure out in a reasonable time, (3) and that I should be able to make significant progress on entirely in my head. I then work on these when lying in bed trying to fall asleep, or when exercising, and similar times, and LeetCode is a good source for such problems.
The problem was given an array of integers find the smallest positive integer that is not in the array, and do it in O(N) time and O(1) space.
The O(1) space part was killing me. I just could not do it in less than O(N).
I decided to spend a while trying to prove that it could not be done in O(1) space. Presumably that would fail, but maybe if I could figure out why it failed that would also suggest how to do it in O(1) space. And thus I ended up thinking about Turing machines and other models of computation.
Except my attempts to prove it cannot be done on O(1) space seemed to succeed, so I was stumped. I spent a couple months on this stupid problem, before finally giving in and peeking at a solution.
It turns out that on LeetCode you can modify input arrays. I'm not a barbarian so I had assumed that inputs were supposed to be immutable.