How many distinct chess games are possible, and which is the longest?

@#271

Thus the question becomes, what trumps what, the fact that the pirate "does not wish to die" or the conditional ""if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against" I would say the conditional wins(counterintuitively) because the pirate not wishing to die and the pirate condemning himself to death are not mutually exclusive. For example a mother could sacrifice herself to save her child in an extreme set of circumstances, and the whole time not wish to die, but still choose to in order to acomplish something more important to her than her life. Thus since the if-then statement does not say anything about the pirates life, and since not wishing to die and condemning yourself to death is not mutually exclusive, the pirate would say no to zero coins, even if it ment his death according to the original stipulations.

watcha, what exactly is a "computable" function in this case? is it simply that the output can be figured out for any given N? if so then the answer is no because if there was such a problem, the function describing its time complexity w.r.t. N would be a computable function that grows at the same speed as itself...

How do you prove this? Since this is a computer science puzzle, you have to present an actual algorithm that computes the time complexity of a problem that is supposed not to have computable time complexity and thereby derive the contradiction.

the bigger is p the smaller time it will take to finish the program:

///////////////////////////////////////////////

#include<iostream>

#include<windows.h>

using namespace std;

int main() {

       double p, d;

       //cin >> p;

       p = 0.0001;

       cout << "time started.";      

       d = 1.0/p;

       Sleep(d);

       cout << "press enter to exit.";

       cin.ignore();

}

///////////////////////////////////////////////

Can you explain to me in non-mathematical terms what you are saying?

Logically would I say: no, because you start saying that it is a computable problem. My question in return would be: is it possible for a computable problem to have a function, that makes it not computable anymore? Seems like a contradictio in terminis to me. If it is a contradiction in terminis would it be not a challenge to solve.

Problem P is computable if there exists a Turing machine T, that for any instance I of problem P as an input halts and outputs the solution to that instance.

Example of a problem that is not computable ( a very fundamental one, for that matter ): the halting problem ( H ). It is well defined ( because a computer program on a given input will either halt or not ), so it has a solution, but there exists no Turing machine which for any instance of H halts and outputs a correct yes or no answer. This is a ground breaking result by Turing ( the proof is ridiculously simple - once you know what to look for ).

The halting problem is the computer science equivalent of Gödel's incompleteness theorem ( they are the formulation of one and the same problem in different languages ).

The basic idea is that in Peano arithmetic you can enumerate proofs. Write a program that enumerates all the proofs of Peano arithmetic. Run it with a statement in the langauge of Peano arithmetic as an input, and make it halt if during the enumeration of proofs if it hits upon the proof of that given statement. If you can solve the halting problem of this machine, then you are able tell whether any statement of Peano arithmetic can be proven from its axioms ( because if the program does not halt, it means that there is no proof, if it halts, there is proof ). Gödel showed that if Peano arithmetic is consistent, it cannot be complete, that is: there exists a true statement in its language about integers, which it cannot prove. If the halting problem were solvable, then Gödel's proof should be wrong, which it is not, therefore the halting problem cannot be solvable.

Solution to the puzzle:

If problem P is computable then there exists a Turing machine T which halts and outputs the solution to any instance of P.

First, it is possible to enumerate all instances of P of size N because T has an alphabet of finite size S ( by the definition of Turing machines ), therefore there can be at most S^N different inputs of size N.

Second, any Turing machine can be simulated by a universal Turing machine ( fundamental theorem of computer science - another ground breaking result by Turing ). Build a Turing machine U, which for a given N as input generates all instances of P of size N and then simulates T on all those instances and counts the number of steps in which T halts ( this can be done because P is computable, therefore T is guaranteed to halt ), takes the maximum of those counts and outputs this maximum.

U(N) computes the time complexity of P for a given N ( because no instance of P of size N can take more steps to solve than U(N) ). U(N) is a computable function, therefore the time complexity of P cannot grow faster than any computable function.

I cannot prove it unless you tell me what "computable" means in terms of functions(as i originally asked) does it just mean that "there is a way to compute the output for any given input?" I'm a student of pure mathematics and haven't done much computer science so while I know what a function is at every level of abstraction, I've never used the word "computable" in any rigorous sense. I've looked at PvsNP and learned all the(obviously) relavent defintions due to its prize money, so I have a limited grasp on things like turing machines. From your prompt, it seems you introduce some problem(call it P) such that the function of the time complexity f(P,N)(a "general time complexity function" can be thought of as a function with two inputs, one being the problem itself P, and the other being the input size N) is given, then you ask "could it be the case that f(P,N) grows faster than any 'computable' function?" and from any defintion I can put to "computable" that is obviously no since f(P,N) grows at the same speed as f(P,N) w.r.t. N, and since f(P,N) is given in the problem, it seems to me that f(P,N) would be computable by any well-fitting definition I can think of.

So if I am misunderstanding what "computable" means(as I feel I must be, for otherwise this is a trivial problem) in this case, please let me know. Thanks.

If I can get a rigorous defintion that would be awesome, but if not, at least try to explain to me how a given function could not be computable.

"at least try to explain to me how a given function could not be computable"

Let BB(n) be the maximum number of steps that an n-state Turing machine can make on an initially blank tape before halting. ( Here the maximum is over all n-state Turing machines that eventually halt. )

BB(n) grows faster than any computable function.

S=1/BB(1)+1/BB(2)+1/BB(3)+... is an uncomputable real number.

proof: http://www.scottaaronson.com/democritus/lec4.html ( answers to homework section, at the bottom of the page )

In this case BB(n) is not a function... at least in the mathematical sense. assuming it is "supposed to be" a function from the positive integers to the positive integers, for it to be a function, every input needs to have an output associated with it. In this case, I dont think (n,x) with BB(n)=x has any solutions in the cartesian product of the positive integers cross the positive integers, so unless this is a vacuous function, it does not appear to be a function at all.

There is a trick that you can make, when confronted with uncomputable problems: use an oracle. Suppose that an oracle could tell you whether a given Turing machine for a given program will halt. However it turns out that this oracle machine has its own halting problem. Of course you can have an other oracle that solves the halting problem of the oracle machine. But this will also have a halting problem, and so on. The same goes for Gödel's incompleteness theorem: Peano arithmetic cannot prove its own consistency, but you can prove its consistency in a stronger axiomatic system, namely ZFC ( Zermelo Fraenkel set theory + axiom of choice ). However ZFC has its own incompleteness problem, so you have to go to an even more powerful system, which again will have its own incompleteness problem, and so on.

If the proof of the halting problem is very simple, how come that Gödel's proof is so complicated?

I never understood this. But now I think the key is this:

There is a one-to-one correspondence between the halting problem and statements in Peano arithmetic. You can state the halting problem of a Turing machine in the language of Peano arithmetic as a proper statement about integers. However the translation is complicated. What Gödel invented with Gödel numbering was turning Peano arithmetic into a programming language, and this is not easy. Also it is not easy to state the halting problem as a statement in the langauge of Peano arithmetic. So while the proof of the halting problem is nuts, the translation between the two systems is complicated, therefore you cannot save the work that Gödel performed and this is why that the proof is still presented in his original formulation.

There is a deep philosophical debate about what a function is. But if you walk down the alley of claiming that BB(n) is not a function, then you have no reason any more to believe that uncomputable real numbers exist. They exist as Dedekind cuts, Dedekind cuts are well defined, yet some of them are not constructible. So you become an N.J. Wildberger ( who is a math professor who openly questions the existence of real numbers - also one who is openly called a crackpot ). N.J. Wildberger also questions the current definition of functions.

Do you believe in real numbers?

What exactly do you mean by an "uncomputable real number"? all real numbers are computable in the sense that any real number can be thought of as the limit of a squence of rational numbers.(this is actually how you "build" the real numbers from ring axioms)

There are solutions to equations that exist, but are not computable by finite means, is that what you are refering to? (such as roots of general complex polynomials of degree 5 or more. this can be seen quickly from the fundamental theorem of algebra and the unsolvability of the general quintic) but that has nothing to do with the existance of real numbers.

I think the problem showing up here is that we're using two different(but similar) languages. I think we need to hash out each others definitions to see exactly what the other is saying. 

'Can be thought of' and 'generate its n-th digit in a finite number of discrete steps' are not the same thing.

Computable number is a well defined thing, there is no question about what a computable number is, and that there are uncomputable real numbers:

http://en.wikipedia.org/wiki/Computable_number

Turing's original paper:

On computable numbers, with an application to the Entscheidungsproblem

http://draperg.cis.byuh.edu/archive/winter2014/cs320/Turing_Paper_1936.pdf

chess philosophy ?

Okay, now I understand what you mean by a computable number. Now, how does that apply to BB(n) being a function? if it was a function, it would be one from the positive integers to the positive integers, which are ALL computable numbers. so I'm not sure how BB(n) not being a function has anything to do with the computability of numbers since its "supposed" domain and range are all computable?

I've been looking into all this, and I think the problem I'm having is actually arising from what exactly the definition of a "state" is in terms of a turing machine, and I cannot find a good place that has a defintion of it. Do you know of a good definiton?

AHHHH!! I found it now, a "state" is a much more basic type of thing than what I was thinking of for it. so a state is a rather limited function from {0,1} to {(a,b,c):aE{0,1}, bE{R,L}, and cE{the set of all possible states}}.(please let E be the symbol for "is an element of" Sorry, I was taking state to e something a little looser, in which BB(n) would be infinity for all n, which is why I was having trouble accepting it as a function. Now it makes sense that there are only finitely many eventually-halting n-state turing machines(up to isomorphism) and so BB(n) is a function. K, now I understand what you're saying.

Lol, sorry, as I said earlier, I dabble more into the classical pure maths rather than much computer science, so I'm not sharp on all the defintions. 

Look, I can't give an introduction to computer science here. Not only because I'm in no way qualified to do so ( I did my own research into the subject, but that's all ) but because you have to get familiar with the basics yourself and get an own hard fought understanding.

What is fascinating is how computer science makes you re-examine what you know about math.

I think this is enough of me and computer science for a while.