This is not a blog title

I feel kind of stupid for getting stumped on exercise 5, but I simply cannot figure out how this can be computable. So far, the text has not formalized the notion of algorithm, so we're just going by vibes. However, the vibe is that this should only be partially computable. How could any algorithm for this ever terminate?

Ooh! This is a good one. How much of a hint/answer do you want?

To what extent have you defined completeness?

Now for 3 hints. Organised by most spoilery to least spoilery. Then the answer. If you do not want them yet ... close your eyes and scroll down. Or try it again. Or send another ask or something.

.

.

.

.

.

Hint #1:

I can confirm it is computable. I also will hint that the proof I have come up with is non-constructive. To my knowledge this is not one that we currently have the knowledge to build the constructive one.

.

.

.

.

.

Hint #2:

The trick is that for computability you just need to provide a Turing machine that outputs the right answer for every valid input, the Turing machine doesn't have to 'know' anything about π. This is the same way that "what is the remainder after division by 4" doesn't have to understand division or do division, it just needs to look at the last two bits.

.

.

.

.

Hint #3:

The output as n grows is 1s until eventually (or not) it becomes 0. Once it becomes 0 it always has to be 0. So it's either all 1s, or 1s up to some n, and then 0.

.

.

.

.

Answer;

I wanted my algorithm to take π as an input despite the fact that the only symbol in my alphabet is 1 and actually look for a string of 7s. I understand what the exercise is getting at now. My algorithm does need to look at π at all (though to compute this function, you would have to "hard code" the length of the longest string of 7s). Interesting

Let F be a function which takes as input (a computer program defining) a computable number x, and produces as output (a computer program defining) the corresponding f, so we may say F(x)=f. Let M be an arbitrary Turing machine, then construct some computable number x digit-wise as follows: if M has halted after n timesteps, then the n'th digit of x is 7, otherwise the n'th digit is 0. Let X(M)=x denote the function which takes M and produces x, then X is computable. Now the function F(X(M))(1) returns 1 if and only if M halts, so the halting problem becomes computable when given an oracle for F. It follows that any such F is uncomputable.

Suppose there were a constructive proof which proves that: for every computable x, there exists a computer program P which implements f, where f is defined relative to x instead of π, as in the OP. Since the proof is constructive, it can be converted into an algorithm F which takes as input a computer program defining a computable number x, and produces as output a computer program defining the corresponding f. But such an F is necessarily uncomputable, as we've seen, so no such constructive proof can exist.

My first instinct tells me halting oracle gives us F? If x is computable, you can create a program that keeps going to the right until it hits a non-seven number, call this M. And now let H be the halting oracle, so

So something like:

F(x)= λn. If H(M(x)), n<M(x); else True

Okay.

Idk if we can implement F using H, but your idea made me realize we can compute F provided we at least have a second halting oracle. Let H be an oracle to the usual halting problem, as before. Turing machines which are enhanced with the ability to call H will be called oracle Turing machines. This class of machines admits its own harder version of the halting problem, which even H cannot solve. Let H' be an oracle to this harder version of the halting problem. Now we can show that F is computable relative to H', using your construction.

Let M(x,n) be the machine which searches for a run of n consecutive 7s in x, and halts iff it finds one. Then H(M(x,n)) is true iff x contains a run of n consecutive 7s. Now consider the oracle machine C which keeps incrementing n higher and higher, checking H(M(x,n)) at each step, and halts only when it's false. So C halts if and only if there exists an n such that there is no run of n or more 7s. We can use our stronger oracle H' to decide whether or not C halts, and this lets us implement F relative to H'. To do that, first check H'(C). If C doesn't halt, then f=1 is constant, so F(x) can just output that f. Otherwise if C halts, then we can just run C directly until it halts, and this can tell us the largest n for which M(x,n) halts. In other words, it tells us the largest n for which there's a run of n consecutive 7s in the digits of x. Once we have that, then we can construct f, since f merely needs to compare its input to this maximum n.

Hmm.

Okay. Just got home from everything today. Trying to think.

Just rambling into text now:

Halting oracle somehow knowing there are arbitrary length strings is the trouble. Can this somehow be an oracle for second-halting?

Can we... somehow... ahh... diagonalise this? Show that it is not in H, instead of showing it is H'? Or zig zag this and do some universal algorithm nonsense? Show that-

Wait can we do a non-constructive version? Somehow show there's a maximum number we have to check that we can somehow know off of the computation of x? With H, we can get the busy beaver numbers for no oracle. x is computable. Do these help? I can't immediately see how.

At this point I discovered portal 2 was at 2 dollars on Steam.