Programming

In applied CS, it's common to talk about pure and impure functions instead of Turing machines.

Pure functions are, broadly speaking, equivalent to Turing machines. A pure function may only depend on its inputs (like a Turing machine) and has no outputs besides the return value (like the end state of a Turing machine's tape).

Impure functions cover algorithms that aren't Turing machines. For example, you might have a random number generator rand: 1 → N that outputs different natural numbers on every invocation rand() and is hence impure. Output functions are also impure, e.g., a function write: N → 1 that writes a number into a file can't be a Turing machine, because Turing machines have no concept of files.

Computer programs that consist entirely of pure functions aren't very useful, because they can't interact with the user or reality. The typical approach to solving this is to put the core program logic inside pure functions that interact with impure parts through a limited interface. That way, you can apply CS concepts to the important parts of the program and neatly separate out the impure parts.

Edit: Changed ∅ to 1 (singleton set) in function definitions. A function can't return ∅ and a function taking ∅ can't be called.

Well, "algorithm" isn't a perfectly well defined term, and to be precise about randomness we sometimes say "randomized algorithm" if an algorithm uses an RNG. You can also extend the notion of Turing machine to include a randomization feature if you need that for something. I would say this whole issue is usually not important. It shows up mostly in some niche areas.

I would expect the CT thesis would gloss over the issue a little bit, and at the end of the day allow randomized computations as being realizeable.

Can I ask what book you are using? The ones I know of are now pretty old, I guess.

I don't know of instances where RNG's can make an uncomputable function computable. I think maybe that never happens. It is an open research question (called P=BPP) whether an RNG can allow solving a problem efficiently where the only non-randomized solutions are inefficient (i.e. a PRNG won't work, you need a real RNG).

The studies about computability and Turing machines etc. started in the 1920s, before there were computers, so the subject area was mathematical logic rather than the then-nonexistent "computer science". These days CS is mostly about specific algorithms, and even complexity theory (a niche area in theoretical CS, which in turn is a niche area in CS) is mostly about the computable, and stratifying computable functions into layers according to how many computations it takes to solve them.

If you're interested in the more "out there" questions of what can be computed at all, you might benefit from studying some logic (I mean the kind taught in math departments). Computability theory is imho mostly a topic in logic. It overlaps CS, but only somewhat. I think any theory-oriented programmer should study logic at least a little though, say enough to understand how predicate logic works. Unfortunately I don't know of a good book to suggest, but maybe someone else here does. There are good Wikipedia articles in the topic, but I find it useful to have something to read in linear order.