Apologies if the title is confusing, but I couldn’t think of better phrasing in short text.
Whenever we define / specify a certain automaton (such as a finite state machine or a turing machine) by defining all of its States, transition function, etc., this feels awfully similar to defining an algorithm. For example, I can define a machine that can tell if a number is divisible by 3. It is very similar to writing an algorithm and the steps to solving the problem.
Now I understand that the two aren’t exactly equivalent. But would it be incorrect to say that the specification of a machine is a type of algorithm, since we’re defining the steps it takes to solve a problem (how to respond to a specific state or input to solve a specific problem)?
Yes, that’s essencially the church-turing-thesis
That’s the only church I’ll trust
Ermph, maybe there is a mathematical correspondence but the connotations are different. We usually think of an algorithm in terms of the relationship between its input and its output. But determining that by inspecting the state diagram of a Turing machine is literally impossible, by a result called Rice’s theorem. Are you taking a class or reading a book? Or just curious, etc. (that is fine)? What direction do you want to take this in?
A “Turing machine” is a mathematical construction that can be given a formalized definition, but “algorithm” is a jargon word that is a bit less formal and has some wiggle room. But, if you say there is an algorithm to compute X, that means (except in some special contexts) that there is a Turing machine that does it, and vice versa.
Actually nowadays “algorithm” can include steps where you generate random numbers (“roll a 6 sided die and do X with the result”). Turing machines are deterministic and that difference is sometimes significant. There is additional jargon to make this precise, that I’ll skip here.
Are you taking a class or reading a book?
Reading a book actually. A programmer by craft who never studied CS, so decided to do it on my own. I appreciate the depth of your answer, thank you! :)
So Turing machines cannot be considered equivalent to algorithms when we involve steps like random number generation? How does church-turing address this? Isn’t that part of what’s “computable”?
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 → Nthat outputs different natural numbers on every invocationrand()and is hence impure. Output functions are also impure, e.g., a functionwrite: N → 1that 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.
It would be incorrect, but only because you’ve learned from vague teaching materials. You’re on the right track; let’s just be a bit more precise about terminology.
An algorithm is a sequence of numbered steps, where some steps make decisions and some steps point towards other steps. Equivalently (thanks to the structured-programming theorem) an algorithm is a flowchart with decision nodes. Machines typically evaluate algorithms directly; the numbered steps can be mapped to sequences of machine instructions. Machine states arise from considering how a particular algorithm behaves on a given machine.
A specification is a pair of claims, often called the precondition and postcondition, which logically connect the inputs and outputs of a machine. The idea is that, if we fulfill the precondition prior to running the machine, then the outputs of the machine will fulfill the postcondition. The study of specifications is often called “formal methods”, a terrible name for a great idea.
The connection is hopefully straightforward to see: an algorithm might happen to fulfill a specification. In general, there are often multiple algorithms for a given specification; for example, there’s usually an infinite number of ways to add a do-nothing instruction to an algorithm without changing any of its behaviors. A classic example is sorting; there are many sorting algorithms, all of which fulfill the postcondition that the output list is sorted, usually with the precondition that the input list contains sortable/orderable elements.