3 ms·
Considering cardinalities, functions and strings are equal. Using javascript notation, ‘fn => fn.toString()’ is an injective function from functions to strings
by ulucs 8y ago
Considering cardinalities, functions and strings are equal. Using javascript notation, ‘fn => fn.toString()’ is an injective function from functions to strings and ‘str => () => str’ is an injective function from strings to functions.
- DougBTX 8y agoThat argument seems like it makes total sense, but I feel like I’m missing something so I’ll just have to say I don’t know!
- joshuamorton 8y agoA more handwavy, but conceptually sound argument is that these functions to generate bit sequences can themselves be represented as turing machines. And if they can be represented as turing machines, we can write them down as a string (or a bit sequence). In general, a bunch of magic happens once you recognize (heh) that the sets of turing machines, strings (binary or otherwise), and integers are all countable and that you can biject between them fairly cleanly.
- tomp 8y agoThe argument is basically, "all actual Turing machines are finite, because the universe/computer memory is finite".