Computability: how is this function computable?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Computability: how is this function computable?

Postby mat.tia » Fri Nov 15, 2013 4:15 pm UTC

I've been taking "Formal Methods in Computer Science" this semester, which is one of the most interesting courses I've had so far in my brief university career.
We deal with complexity, computability and formal semantics of programming languages.
I didn't have any trouble understanding the basic concepts of countability, different orders of infinity, the halt theorem (both formal and intuitive demonstration...) etc.
What I find hard to wrap my head around is how to discern if a function is computable or not in some case.
For example.

Let f(x) be a function that returns 1 if there is a sequence of the digit '5' repeating at least x times in the decimal representation of pi, 0 otherwise. I was told this function is computable.
It is so because there are two cases:
*) there is an /infinitely long/ of any finite length/g sequence of '5's in pi => f(x) = 1 always
**) the longest sequence of '5's in pi is k: => f(x) = 1 if x<=k, f(x) = 0 otherwise.
So my teacher said " ok this is computable because the function is either 1 (*) or {1 or 0} (**), it just depends on k. We don't know what k is, but k is there. So we don't know which of the programs is the right one, but it is there.

When I think of it myself, I think of it from another point of view it looks obvious to me that this should not be computable (although i know I'm wrong). I base this idea on the fact that
1) there is no way to predict how the digits of pi will be just looking at a limited amount of them (otherwise pi would not be irrational I think)
=> which means that the only way to know how the digits of pi are is to look at each of them.

So back to our original function. We have a Turing machine that has infinite tape, so our long irrational number can well fit on it. But when we activate the program and have it inspect each digit one at a time..... it will never return 0! It either returns 1 or is indefinite and hence goes on forever.

Where am I wrong?
Last edited by mat.tia on Mon Nov 18, 2013 8:39 pm UTC, edited 1 time in total.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Computability: how is this function computable?

Postby EvanED » Fri Nov 15, 2013 5:44 pm UTC

I'd say your intuition is pretty good, and it's somewhat a trick question. Definitely not entirely, and depending on your preparation it might be perfectly fair, but it's a bit subtle.

From an absolute, "what is true", perspective, let k be the maximum repeat length (perhaps ω if every finite string 5n appears) of 5 that appears in the decimal expansion of pi. There is such a k, we just don't know what it is. Do you agree so far?

OK, now define a family of functions g(x,y) = (x <= y) (and g(x, ω)=1). Each of those is trivially computable. Well, that means that f(x) = g(x, k) is also trivially computable once we stick in k from above, and because k exists, so does g(x, k).

However, the above proof is non-constructive; it doesn't tell you how to effectively produce a program to compute f or how to find k. So while f is computable, actually finding a program for f, or determining whether a candidate program computes f, is uncomputable.*

*Technically this may still be computable via other means, for instance someone could prove that pi is normal, which would imply that k=ω and then you'd know f(x)=1. But your intuition is right that you wouldn't be able to get it by computing digits of pi. (For all I know, someone has already proven a looser property than "normal" that would still imply that k=ω, but I somewhat doubt it.)

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Fri Nov 15, 2013 6:34 pm UTC

I think you have made your point very clearly.
If I understand correctly, the distinction is in between the function that calculates the constant k (max repeating '5's) and the function that uses it once it has been defined. From this is obvious that the latter is trivially computed.
Assuming that we are talking of a random irrational number that we don't know any property of, is the function that computes k computable?
And if so, how is it different from the halt problem?
If I define kind_of_halt(n) = { #of steps in which program n terminates, 0 otherwise } and I implement it with a program that keeps a counter of steps and simulates the input program n to finally return the counter state when the procedure terminates, how is it different from calculating k above?
As the only way to find out if something is there in an infinite list you might have to go all the day*, the same happens if you want to know that length of a list that can or cannot be infinite, right?
Maybe I'm looking too much at the practical computations and I should just look at k as an ipse dixit variable whose value is somewhere floating.

*way
Last edited by mat.tia on Sat Nov 16, 2013 12:36 pm UTC, edited 2 times in total.

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Fri Nov 15, 2013 7:14 pm UTC

Ok so I read again your answer and you already answered my first point. But I still don't see the difference between that overall situation (computable) and the function halt that takes kind_of_alt as an input, since they both depend on an uncomputable function. Both these NC functions try to find a value that can be at an infinite point, for which they have to go through an infinite list.
So why can the function calculating the sequence of 5s in pi be computable even if it depends by a parameter whose value is uncomputable?
We could also say that halt is trivially computed by the program that returns 0 or 1, given the correct algorithm, which we don't know, but exists and implements kind_of_halt, behaving as the function "looking" for k, but it instead looks for the end of the program instruction log-list.
The more I think of this the more I can't think of considering a function that treats irrationals (or another that depends by the termination of such) as computable.
Sorry for double posting but I'm slow and I'd like to fully understand this point since I feel it be an essential part of CS theory.

Derek
Posts: 2180
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Computability: how is this function computable?

Postby Derek » Fri Nov 15, 2013 9:17 pm UTC

I don't think this function is computable by computing the digits of pi, because you never know when you've seen the maximum run of 5's. If there is a proof of the maximum run of 5's in the digits of pi, then this function is computable. However, if no such proof exists, then this function is incomputable.

To the best of my knowledge, no such proof exists at the moment, nor is there a proof that it can't be proven, so I would say that the status of this function is unknown right now.

User avatar
Sizik
Posts: 1243
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Computability: how is this function computable?

Postby Sizik » Sat Nov 16, 2013 4:59 am UTC

Shouldn't there be a third case? It's possible that there's no infinite sequence of 5s, but there still are runs of 5s of any finite length (e.g. something like 0.5155155515555155555...).
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Computability: how is this function computable?

Postby EvanED » Sat Nov 16, 2013 5:35 am UTC

I'll try to answer more later, but I'll respond to this now:
Sizik wrote:Shouldn't there be a third case? It's possible that there's no infinite sequence of 5s, but there still are runs of 5s of any finite length (e.g. something like 0.5155155515555155555...).
Yes and no. There's no possible third case, but the original wording was slightly sloppy: instead of saying "there is an infinitely long sequence of '5's", it should have said "runs of 5s are unboundedly long" (or "of any finite length", or whatever).

There is no possible way, however, to have an actual infinite run of 5s. The only way that you could have an infinite run of 5s was if it was at the end, but then its decimal representation would be eventually repeating and hence pi would be rational. :-)

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Sat Nov 16, 2013 12:27 pm UTC

Derek wrote:I don't think this function is computable by computing the digits of pi, because you never know when you've seen the maximum run of 5's. If there is a proof of the maximum run of 5's in the digits of pi, then this function is computable. However, if no such proof exists, then this function is incomputable.

Yes pi here just represents a list of digits of which we know nothing about.
We could modify the original function so that instead of having the value of pi "hardcoded", it could take any irrational number as an input (just using the smn theorem). Which is eventually encoded as a natural number.
Here lies the problem: how can an irrational number be different from a list of instructions/steps performed by an algorithm, since they're both encoded as list of digits/a natural number for a machine?



EvanED wrote: There's no possible third case, but the original wording was slightly sloppy: instead of saying "there is an infinitely long sequence of '5's", it should have said "runs of 5s are unboundedly long" (or "of any finite length", or whatever).
yes I meant non-limited instead of infinite, sorry for the sloppiness



btw this exercise was taken from the text Kfoury, Moll, Arbib:"A Programming Approach to Computability", Springer-Verlag, 1982 which claimed that the function IS computable.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Computability: how is this function computable?

Postby korona » Sat Nov 16, 2013 1:20 pm UTC

The function "f(x, n) = 1 if the decimal representation of x contains more than n consecutive 5s and 0 otherwise" is clearly not computable.
However f(pi, n) is, or more generally the function gx(n) = f(x, n) for a fixed x.

Let k be the maximal number of consecutive 5s in the decimal representation of pi. It is either finite or does not exist. But if it exists then it is a fixed constant that I can simply write down. It is NOT a variable! So lets assume that k = 47.

Then

Code: Select all

function g(int n) {
   return n <= 47;
}

is a program that computes gpi(n). This program obviously halts, so gpi(n) is computable.

Now lets assume that such a k does not exist. Then

Code: Select all

function g(int n) {
   return true;
}

computes gpi(n) correctly.

Note that none of the programs actually operates on the number pi. Both programs only do elementary integer arithmetic. Since we do not know the value of k we don't know if the first or the second program is correct. But one of those programs MUST be correct (well 47 is probably the wrong value for k but you get the idea).

The problem with this idea is of course that we don't know the value of k. The function "k(n) = maximal number of 5s in the decimal representation of n" is clearly not computable. But maybe we can get the number of k(pi) by some other means i.e. someone could work out a proof that k(pi) = 47 and then the program above is correct.

EDIT: In response to Dereks answer: Even if there is neither a proof that k has a certain value nor a proof that k does not exist the function remains computable (were no proof exists means that the proposition "k exists" is independent from some axiomatization of mathematics). By the law of the excluded middle the sentence "k exists and is a finite constant or k does not exist" is still true and that is the only fact that you need for the mechanism above to work.

That is why intuitionists do not accept the law of the excluded middle.

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Sat Nov 16, 2013 1:39 pm UTC

thanks korona, I perfectly understand what you're saying and I agree with you on that.
What I do not understand is why we can't apply the exact same reasoning to the halt problem, with k being, if existing, the finite number of steps in which the program ends.
Unless the function haltn(x), instead of halt(n,x), for a fixed program n is computable... is it?

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Computability: how is this function computable?

Postby korona » Sat Nov 16, 2013 1:42 pm UTC

The function "haltp(n) = the program p halts (say with empty input on a deterministic Turing machine) in n steps" is computable (for a fixed p). In this case the function can be computed explicitly by simply simulating the Turing machine. Even the function "halt(p, n)" is computable. But the function "halt(p) = 1 if the program p halts in an arbitrary number of steps" is not computable.

Computability applies to functions and not to constants. For each program p you have a constant "haltp". You know that a fixed Turing machine either halts or does not halt. For each individual machine you might be able to work out a proof that it halts (i.e. determine the value of haltp). But there is no general algorithm that tells you which Turing machines halt.

EDIT: Assume that you know the values of haltp for each program p. The function halt(p) remains uncomputable unless you find a way that returns the correct haltp given only p. You cannot do something like

Code: Select all

function halt(p) {
   if(p == program1)
      return halt[sub]program1[/sub]
   if(p == program2)
      return halt[sub]program2[/sub]
   ...
}

because that algorithm would not have a finite description.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Computability: how is this function computable?

Postby jestingrabbit » Sat Nov 16, 2013 7:37 pm UTC

mat.tia wrote:*) there is an infinitely long sequence of '5's in pi => f(x) = 1 always
**) the longest sequence of '5's in pi is k: => f(x) = 1 if x<=k, f(x) = 0 otherwise.


There is another case here.

Consider the sequence 01001000100001000001000000100000001000000001000000000100...etc. There isn't any longest sequence of 0s, and there isn't an infinite sequence either.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Computability: how is this function computable?

Postby jareds » Sun Nov 17, 2013 12:57 am UTC

jestingrabbit wrote:
mat.tia wrote:*) there is an infinitely long sequence of '5's in pi => f(x) = 1 always
**) the longest sequence of '5's in pi is k: => f(x) = 1 if x<=k, f(x) = 0 otherwise.


There is another case here.

Consider the sequence 01001000100001000001000000100000001000000001000000000100...etc. There isn't any longest sequence of 0s, and there isn't an infinite sequence either.

There definitely is not an infinitely long sequence of 5s in π; so I would charitably replace the OP's case with your case (and indeed EvanED did such replacement in the first reply).

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Mon Nov 18, 2013 8:33 pm UTC

Ok, I think I got it. Probably some confusion was helped by my notation.
The problem is that k (even if not mentioned by exercise text) is presumed to be defined as a constant. Although a practical usage of the overall function, to the state of our knowledge, would need that k replaced by a function that computes its value, we can still assume that k is given.
Also, if k was given for any irrational number, you could not extend this function to a total over the irrationals because they're too many to be listed.
The same way, you could not define a total halt' that contains all cases for all programs as constants because the listing would be infinite.
I guess there would be no problem then to just define a (useless) halte, assuming given the constant number of steps it takes the program e to end (empty otherwise)
Thanks for the ideas, discussing this was very helpful to better grasp the concept.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Computability: how is this function computable?

Postby skeptical scientist » Thu Dec 26, 2013 7:02 am UTC

mat.tia wrote:Assuming that we are talking of a random irrational number that we don't know any property of, is the function that computes k computable?

No, it isn't.

And if so, how is it different from the halt problem?

It's just as hard as the halting problem, because given a program, you can define a (computable) real number where knowing the length of the longest sequence of repeating fives in that number determines whether the given program halts. (In fact, it is a harder problem than the halting problem.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

mat.tia
Posts: 90
Joined: Tue Nov 22, 2011 11:06 am UTC
Location: Torino

Re: Computability: how is this function computable?

Postby mat.tia » Thu Dec 26, 2013 11:51 am UTC

skeptical scientist wrote:given a program, you can define a (computable) real number where knowing the length of the longest sequence of repeating fives in that number determines whether the given program halts.
true, I didn't think of that but it is the clearest way of proving it


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 46 guests