Population

hello, world

    A. First Edition

    This is first edition of my "hello, world" program and it is actually not exactly a program, but a problem.

    B.The problem

    This is from our text book of comp335. The problem is designed to prove there is something that

    computer cannot do.

    Suppose we have a program called "turing" which takes another program, say "input", as input and

    output something according to the output of that "input" program. Then the author of book tried to

    prove such kind of "turing" program cannot exist.

    Suppose the "turing" program will output "yes" if the "input" program output "hello, world" and for

    all other kinds of output (even no output is considered to be a kind of output.) of "input", "turing"

    will output "hello, world". Then if we use "turing" itself as its input program, what happens?

    In the text book, they said, assume "turing" output a "yes", then according to above rule, the input

    program should have output a "hello, world". And this input program is "turing" itself which by

    assumption has output a "yes". This leads to contradiction of our assumption of output of "turing"

    is a "yes". So in conclusion such a program can not exist. Then it proves that some kind of program

    is impossible to write which means there is something cannot be done by computer.

    ¡¡

C.The idea of program
¡¡

Is it a kind of problem that computer cannot accomplish? I always feel suspect about it. Not for

the correctness of proof, but for the problem itself. The following is my idea:

1. The concept of "program" and "process": We all know that "program" is usually referred to the

source code which defines the run-time behavior of our program. Whereas "process" is the run-time

entity of program and it is described by a series of states value which are stored in operating

system. One program can have many different processes running at same time. And the behavior of each

process may vary depending on its particular running environment, even they are both originated from

same "program".

2. The "turing" program is the source code that defines the property of its all running processes---

output "yes" for input "hello, world" and output "hello, world" for non else. However, does it mean

it can only have one running "process"? Certainly not! We all know for a fixed time and space there

can only exist one object. Same thing happens for computer environment! One "turing" program (or

process, if you like.) is using another "turing" program (process) output as its input. This itself

implies that it should be considered as two processes, or at least one process but running

continually with two different input and output. Suppose for simplicity sake, we create two

independent "turing" processes, one accept another one's output as its input. Why should we confuse

ourselves by the particular assumption in the proof that "assume "turing" output a "yes", then

according to above rule, the input program should have output a "hello, world". And this input

    program is "turing" itself which by assumption has output a "yes". This leads to contradiction of

    our assumption of output of "turing" is a "yes"".  Quite obviously the "turing" program has two

    independent processes which cannot have the same input all the time. Then why bother to say there

    exists a contradiction?

¡¡

//The following is just original what is going on in my mind and you can ignore them now.

/*

Is it a kind of problem that computer cannot accomplish? I always feel suspect about it. Not for

the correctness of proof, but for the problem itself. We know that the problem defined by author is

like a function, or more commonly, a logic implication:

If input is "hello, world", then output is "yes".

Let's define as following propositions:

Input()={ The input of "turing" program is "hello, world".}

Output()={ The output of "turing" program is "yes".}

Then it is like this implication:

Input()==>Output() is equivalent to: Input()<==>Input()&&Output()

This says that Input() is true then both Input() and Output must be true. But we force our "turing"

program to be in such an awkward situation that the "input" of this "turing" program is same as the

"output" of it. Do we force the functional relation of "turing" becoming a "loop"? Can we do it?

*/

¡¡

/*

//The below is non-sense and disregard them!!

For this above implication, can we have converse implication such as following???

If the output is "yes", then the input is "hello, world".

The above one is obviously not possible true given first implication.

Then why should we ask computer to do something we know impossible even for logic or for brain of

human?

*/

    D.The major functions

    E.Further improvement

    F.File listing

    1. turing.cpp (main)

    ¡¡

    file name: turing.cpp

    #include <iostream>

    using namespace std;

    char* turing(char* input);

    int main()
    {
    	char* hello="hello,world";
    	char* yes="yes";
    	cout<<turing(turing(hello))<<endl;

    	cout<<"now if it is yes?\n";
    	cout<<turing(turing(yes))<<endl;

    	return 0;
    }

    char* turing(char* input)
    {
    	if (strcmp(input, "hello, world")==0)
    	{
    		return "yes";
    	}
    	else
    	{
    		return "hello, world";
    	}
    }

    Here is the result: The result shows for any input, "hello, world" or not "hello, world", in this case "yes",

    the output of function "turing" is always "yes".

yes
now if it is yes?
yes
Press any key to continue

¡¡

Here is the result: This is more output if we change the main function like following:

    int main()
    {
    	char* hello="hello,world";
    	char* yes="yes";
    	cout<<turing(turing(hello))<<endl;

    	cout<<"now if it is yes?\n";
    	cout<<turing(turing(yes))<<endl;

    	cout<<"what's more, if we use output of turing as input once more!\n";
    	cout<<turing(turing(turing(hello)))<<endl;
    	cout<<"now change it to yes\n";
    	cout<<turing(turing(turing(hello)))<<endl;

    	return 0;
    }

This is more intiguing! As why is that? Is it a logic? I mean true or false really mean something to

the world or not? Suppose we change all "true" to "false" of our world, what will happen?

yes
now if it is yes?
yes
what's more, if we use output of turing as input once more!
hello, world
now change it to yes
hello, world
Press any key to continue