Computer Science

[taeto]

This is a science forum. I go to check what goes on in Computer Science, and it will say "Computer Help". Like what is that supposed to mean: there is discussion on how to write programs, or how to repair a desktop? Judging from the titles of contributions, that is actually pretty much it. No trace of science here.

I am not a computer scientist, but I do happen to know what Computer Science is, in real life. namely CS is a mathematical theory which deals with measuring the theoretical efficiency of computation. For example, the prominent open questions are problems like NP=P? and whether natural numbers can be factorized in polynomial time. But there are many more less famous.

For NP=P, if you propose a solution to win the $1M Clay prize money, you have to work out your precise solution in the framework of ZFC set theory, or you will be disqualified. The reason being that ZFC contains the objects that have the structures of Universal Turing Machines, which are ultimately the things the statement NP=P says something about. You cannot just go work from intuition, or say that your new motherboard seems fast, so it will probably do it fine.

CS is probably closer to set theory than to anything else in the forum. I would prefer to have it placed in the corresponding section. Then "Computer Help" could be fine with staying right where it is. I see no connection whatsoever with the notion of "Computer Help" and science, but if the Gods who decide things around here think that it has to stay, then so be it. Just please, whatever it is, do not confuse it with actual CS science.   

[fiveworlds]

Quote

For NP=P, if you propose a solution to win the $1M Clay prize money, you have to work out your precise solution in the framework of ZFC set theory, or you will be disqualified.

That's nonsense there is no proof that ZFC is versatile enough to write p vs np in either direction. P vs np details a set of problems which you have to prove work on a deterministic Turing machine in a polynomial amount of time. For instance I can prove that I can replace words in sentences with a deterministic Turing machine in polynomial time using the following python function which replicates the action of a real deterministic Turing machine. 

But it can do more than that you can easily replace cities "Cork, London, New York, Brussels" with their shortest travelling salesman result. There is of course a limitation of the number of cities but it'll work for flights and stuff.

Did you know that time complexity on a Turing machine is measured by how many moves the read/write head has to make. Therefore if you make the read/write head large enough to read any input on your tape you never need to move the read head anything but forward making all algorithms O(n). Of course there is a problem with that approach because a Turing machine allows for an infinite tape size and it is not possible to have an infinitely large read head. So you could prove p=np simply by showing that no problem requires an infinite amount of tape.

Quote

 

def DeterministicTuringMachineWordReplace(tape, readHead, writeHead):
   
    #Remove any whitespaces from the start and end of the words
   
    readHead = readHead.strip()
    writeHead = writeHead.strip()

    #Validate that the string is not empty after removing whitespace
   
    if len(readHead) == 0:
        print("String to be replaced should not be empty")
        return
   
    if len(writeHead) == 0:
        print("Replacement string should not be empty")
        return

    if len(tape) == 0:
        print("Sentence should not be empty")
        return

    #Validate that the words only contains valid english characters
   
    letters = "abcdefghijklmnopqrstuvwzyz"
    for letter in readHead:
        if letter.lower() not in letters:
            print("Expected english letters in string to be replaced saw:"+letter)
            return

    for letter in writeHead:
        if letter.lower() not in letters:
            print("Expected english letters in replacement string saw:"+letter)
            return

    #Create the dictionary of replacements. Words preceded by a . should start with a capital letter
       
    options = {
       readHead + " ": writeHead + " ",
       readHead + ",": writeHead + ",",
       " " + readHead + " ":" " + writeHead + " ",
       " " + readHead + ".":" " + writeHead + ".",
       "." + readHead + " ":"." + writeHead[0:1].upper() + writeHead[1:len(writeHead)] + " ",
       "." + readHead + ",":"." + writeHead[0:1].upper() + writeHead[1:len(writeHead)] + ",",
       " " + readHead + "!":" " + writeHead + "!",
       " " + readHead + ":":" " + writeHead + ":",
       " " + readHead + "?":" " + writeHead + "?"
    }

    outputTape = ""
    i = 0
    #Loop through the whole sentence
    while i < len(tape):
        if tape in letters and i != 0:
            outputTape = outputTape + tape
            i = i + 1
            continue
       
        #If there isn't enough letters left to make the word then append the letters to the output sentence
        if len(tape) - i - 2 < len(readHead) :
            outputTape = outputTape + tape
            i = i + 1
        else:
            replace = False
            for k in options:
               
                #Match the word against the possible options
                if tape[i:i+len(readHead)+2] == k:
                    outputTape = outputTape + options[k]
                    replace = True
                    i = i+len(readHead)+2
                    break
                elif tape[i:i+len(readHead)+1] == k:
                    outputTape = outputTape + options[k]
                    replace = True
                    i = i+len(readHead)+1
                    break
               
            if replace == False:
                outputTape = outputTape + tape
                i = i + 1
               
    print("Original sentence:" + tape)
    print("Changed sentence:" + outputTape)

 

 

 

Edited June 17, 2018 by fiveworlds

[fiveworlds]

Actually I will prove you cannot use ZFC to solve p vs np. 

Quote

The axiom of extension says that two sets are equal if and only if they have the same elements. For example, the set {1,3} and the set {3,1} are equal.

A turing machine reads a two number tape {a,b} and gets the power.

a^b does not equal b^a therefore {1,3} and {3,1} are not equal sets and ZFC cannot be used to solve p vs np.

Edited June 17, 2018 by fiveworlds

[Strange]

Fiveworlds, please stop posting on topics you clearly have no clue about. It is embarrassing to watch.

You have demonstrated limited programming knowledge (and defended that by saying you are learning, which is fair enough) but you very obviously have absolutely no idea at all about mathematics or computer science. Your posts on these subjects are just ridiculous.

[StringJunky]

On 15/06/2018 at 7:22 PM, taeto said:

This is a science forum. I go to check what goes on in Computer Science, and it will say "Computer Help". Like what is that supposed to mean: there is discussion on how to write programs, or how to repair a desktop? Judging from the titles of contributions, that is actually pretty much it. No trace of science here.

I am not a computer scientist, but I do happen to know what Computer Science is, in real life. namely CS is a mathematical theory which deals with measuring the theoretical efficiency of computation. For example, the prominent open questions are problems like NP=P? and whether natural numbers can be factorized in polynomial time. But there are many more less famous.

For NP=P, if you propose a solution to win the $1M Clay prize money, you have to work out your precise solution in the framework of ZFC set theory, or you will be disqualified. The reason being that ZFC contains the objects that have the structures of Universal Turing Machines, which are ultimately the things the statement NP=P says something about. You cannot just go work from intuition, or say that your new motherboard seems fast, so it will probably do it fine.

CS is probably closer to set theory than to anything else in the forum. I would prefer to have it placed in the corresponding section. Then "Computer Help" could be fine with staying right where it is. I see no connection whatsoever with the notion of "Computer Help" and science, but if the Gods who decide things around here think that it has to stay, then so be it. Just please, whatever it is, do not confuse it with actual CS science.   

It is what it is. This is not  really a computer-based forum. 

[taeto]

10 hours ago, fiveworlds said:

That's nonsense there is no proof that ZFC is versatile enough to write p vs np in either direction. P vs np details a set of problems which you have to prove work on a deterministic Turing machine in a polynomial amount of time. For instance I can prove that I can replace words in sentences with a deterministic Turing machine in polynomial time using the following python function which replicates the action of a real deterministic Turing machine. 

But it can do more than that you can easily replace cities "Cork, London, New York, Brussels" with their shortest travelling salesman result. There is of course a limitation of the number of cities but it'll work for flights and stuff.

Did you know that time complexity on a Turing machine is measured by how many moves the read/write head has to make. Therefore if you make the read/write head large enough to read any input on your tape you never need to move the read head anything but forward making all algorithms O(n). Of course there is a problem with that approach because a Turing machine allows for an infinite tape size and it is not possible to have an infinitely large read head. So you could prove p=np simply by showing that no problem requires an infinite amount of tape.

 

 

Sorry, but the rules for the Clay prizes state explicitly that whatever proof you have, it has to be a valid proof in ZFC.

Your last remarks seems not quite on point. Depending on what you mean exactly by your condition of requiring an infinite amount of tape. If a problem is in NP, then it follows easily that each YES-instance of it can be solved without using an infinite amount of tape, simply because there has to be some way to find a solution in finite time. For some NO-instances  of NP problems you have to use infinite time for searching, and I doubt that it has any bearing on anything whether you also use infinite tape or not. But even if the problem is in P, you cannot in general do with just a finite amount of tape, because there will be instances that require more space just for stating their input. Either way, the TM that solves all instances has to have an infinite amount of tape available.

8 hours ago, fiveworlds said:

Actually I will prove you cannot use ZFC to solve p vs np. 

A turing machine reads a two number tape {a,b} and gets the power.

a^b does not equal b^a therefore {1,3} and {3,1} are not equal sets and ZFC cannot be used to solve p vs np.

en.wikipedia.org/wiki/Turing_machine#Formal_definition gives the formal definition of a TM as a set in Set Theory.

Btw it is possible to represent an ordered pair (a,b) as a set as well: the most famous definitions are by Wiener, Hausdorff and Kuratowski, see en.wikipedia.org/wiki/Ordered_pair

51 minutes ago, StringJunky said:

It is what it is. This is not  really a computer-based forum. 

Sure. And sorry about the rant. I am newbie and just hoped that in a science forum it would be easier to find those contributions that actually deal with science topics.

Edited June 17, 2018 by taeto
make precision

[fiveworlds]

Quote

Sorry, but the rules for the Clay prizes state explicitly that whatever proof you have, it has to be a valid proof in ZFC.

Where? http://www.claymath.org/millennium-problems/rules-millennium-prizes

There is a rule however that states I need to publish in a peer reviewed journal which I cannot because most of them only accept papers from people with degrees that I don't have. So therefore I couldn't enter the competition if I wanted to.

Quote

I doubt that it has any bearing on anything whether you also use infinite tape or not.

Yes it does. The difference between a DTM and an NDTM is to do with the movement of the read head. If the read head can read the whole problem without moving then the problem is in P. If the problem requires an infinite tape then the read head has to move. Therefore all you need to do to prove p = np is prove that no reasonable problem requires an infinite tape. The internal working of how a Turing Machine calculates anything then becomes irrelevant you can use any algorithm even existing ways of calculating travelling salesman etc.

https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine

 

Quote

 

Deterministic Turing Machine[edit]

In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation.

A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things:

• the symbol to be written to the tape,
• the direction (left, right or neither) in which the head should move, and
• the subsequent state of the finite control.

For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5.

Non-Deterministic Turing Machine[edit]

By contrast, a non-deterministic Turing machine (NTM), the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to:

• Write a Y, move right, and switch to state 5

or

• Write an X, move left, and stay in state 3.

 

•  

Edited June 18, 2018 by fiveworlds

[taeto]

On 6/18/2018 at 8:54 PM, fiveworlds said:

Where? http://www.claymath.org/millennium-problems/rules-millennium-prizes

That is actually a good question. I have a firm memory that tells me that it at least used to be a very explicit requirement that every proof can be verified within the theory ZFC. The rules were modified in September of 2012, however. I would be very interested to know whether the requirement got changed, and why. It would clearly be absurd to allow a proof in a theory of your own choice, as you might simply add as a new axiom the exact statement that you desire to proof, or at least some more disguised statement which would imply it. But I definitely surprised by your observation, so I salute you for that.  

Anyway, the official description of the problem is written by Stephen Cook and it does define a Turing Machine in the language of ZFC. That makes it unlikely that a proof outside ZFC is in any way meaningful. But I am open to suggestion. Do you have a theory to propose different from ZFC in which you would suggest to attempt a proof?

Scott Aaronson has a discussion of the dependence of the NP=P question on ZFC on page 26-28 of www.scottaaronson.com/papers/pnp.pdf.

On 6/18/2018 at 8:54 PM, fiveworlds said:

There is a rule however that states I need to publish in a peer reviewed journal which I cannot because most of them only accept papers from people with degrees that I don't have. So therefore I couldn't enter the competition if I wanted to.

•  

If you submit anything rubbish, they would obviously turn it down. If you submit an actual solution they would quite obviously be delighted, no matter what degrees you do or do not have, heck, it would not matter whether you finished high school or not. Did you ever submit a paper to a journal, or are you just guessing here?

On 6/18/2018 at 8:54 PM, fiveworlds said:

Yes it does. The difference between a DTM and an NDTM is to do with the movement of the read head. If the read head can read the whole problem without moving then the problem is in P. If the problem requires an infinite tape then the read head has to move. Therefore all you need to do to prove p = np is prove that no reasonable problem requires an infinite tape. The internal working of how a Turing Machine calculates anything then becomes irrelevant you can use any algorithm even existing ways of calculating travelling salesman etc.

https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine

Not sure what you mean by that. You quote an informal description of a DTM that requires the read head to move either backwards or forwards every time it needs to read from a different cell. 

I also do not know what you mean by saying that a problem "requires an infinite tape". Either example of a TM requires an infinite tape, otherwise it is simply not even possible to accept all legal inputs. If your TM factorizes integers, and its tape only has room for inputs of N bits that are available on your tape, then what will it do with an integer that has to be written with N+1 bits?

Edited June 19, 2018 by taeto