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 ...
  • 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 ...
  • 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

Only top scored, non community-wiki answers of a minimum length are eligible