Last Update: 20 September 2013
Note: or material is highlighted |
h = {<"yes", print "hello">, <"no", print "bye">, <input ≠ "yes" & input ≠ "no", print "sorry">}
k = {<0,1>, <2,4>, <4,8>,…}
Strictly speaking, this is not correct, because functions (considered extensionally) don't "do" anything.
However, a computer can be viewed as such a machine!
i.e., there is an algorithm A_{f} such that, for all input i, A_{f}(i) = f(i)
and A_{f} specifies how f's input and output are related…
(the word "algorithm" comes from the name "Al-Khuwarizmi", Arab mathematician, ca. 780-850 AD, i.e., about 1200 years ago)
and must be able to execute each step (in a finite amount of time?)
(or any other bistable pair
that can flip-flop between two easily distinguishable states,
such as "on"/"off", "magnetized/de-magnetized",
"high-voltage/low-voltage", etc.).
For more info on this particular model of Turing machines, see:
…where—recursively—"this" and "that" can be:
The optional additional grammatical rules are:
(For more info, see "Great Ideas in Computer Science": Lecture Notes #3, Lecture Notes #4 .
Effective computability =df (anything equivalent to) Turing-machine computability |
I.e., an algorithm is_{df} (expressible as) (anything equivalent to) a Turing-machine program.
This is a proposed definition.
How
do we know that Turing-machine computability captures the intuitive notion of effective
computability?
Evidence:
i.e., there are no intuitively effective computable algorithms that are not Turing-machine computable