3
votes
ASCII invariant string for base64 Encoding
The base64 encoding of the empty string is the empty string, so arguably the empty string could be considered an example of the sort you are looking for. But there are no other examples. The base64 ...
D.W.♦
- 150k
3
votes
Accepted
Reddiag being a calculable function (Gödel, Escher, Bach)
The passage in question has a standing assumption that RedProgram enumerates all computable total functions. Since Reddiag is ...
- 29.1k
3
votes
Ackermann Function without Recursion or Stack
Note: this answer assumes one more rule on the WHILE language (which is not in the paper linked by OP), which is that the variables within are limited to a certain size. It does not matter which size, ...
- 1,273
1
vote
Prove that the problem MATCH is NP-complete
Let $\phi = c_1 \wedge c_2 \wedge \dots c_m$ be a 3-SAT formula on $n$ variables $x_1, \dots, x_n$, where $c_i$ is the $i$-th clause.
Assume w.l.o.g. that no clause contains both a literal and its ...
- 26.1k
1
vote
Let A, B two languages such that A=B does that implies that coA=coB
This question is not answerable, as you have not defined the notation coA. Normally, we use the "co-" prefix with complexity classes (sets of languages) rather than languages (sets of ...
D.W.♦
- 150k
1
vote
Given computable function, what are conditions for computability of inverse function?
Also note that if the function is injective and not necessarily surjective, then the inverse will be partial computable
- 111
Only top scored, non community-wiki answers of a minimum length are eligible