What does "Turing Equivalent" mean?

In order for something to be Turing Equivalent, it must first be Turing Complete. This means that it must be able to perform any kind of computation that any Turing Machine can perform. In other words, it must be at least as powerful as any Turing Machine.

However, in addition to being Turing Complete, any computation that it can do must also be doable by some Turing Machine. In other words, it cannot be more powerful than all Turing Machines. In particular, it can't be more powerful than the Universal Turing Machine, which can do anything that any Turing Machine can do.

---

The question of whether something is "Turing Equivalent" was first considered by Alonzo Church and his student Alan Turing. Their understanding of the answer to this question became known as the Church-Turing Thesis.

Keep in mind that this was done before computers existed--at the least the electronic kind that we are so familiar with today. At that time, a computer was a person. It was someone who was given a set of written instructions by some engineer or mathematician. This human computer would then, with the assistance of an Adding Machine, carry out the instructions and eventually come up with an answer.

In other words, the engineer or mathematician would give the human computer an algorithm to follow.

---

So, what Alonzo Church and Alan Turing were really asking was whether any algorithm, no matter how complicated, could be implemented on a Turing Machine.

Although it was never proved with a rigorous mathematical proof, practically everyone today believes that the Church-Turing Thesis is true.

Any algorithm whatsoever can be implemented on a Turing Machine!