User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic: Difference between revisions
No edit summary |
|||
| Line 58: | Line 58: | ||
==algorithm vs program vs index vs Godel number== | ==algorithm vs program vs index vs Godel number== | ||
I think all of these are essentially the same in that they are all ways of encoding some objects one cares about, but I notice that my "mental imagery" is different for them. | |||
* Godel number I think is used most in logic when numbering formulas. It's also the case that when numbering formulas, no two godel numbers have the same formula, i.e. the mapping from godel numbers to formulas is injective. (This is not the case when numbering computable functions.) | |||
* When I think of "algorithm" or "program", I imagine it being a string rather than a natural number (it seems most concrete to me to imagine a Python program). This distinction turns out to not be important, since we can just think of strings as integers. | |||
* When I think of "index" I think of natural numbers. I also imagine there being some sequence of indices, whereas with "algorithm" or "program" I can think of them in isolation. | |||
==notes== | ==notes== | ||