Jump to content
Can't remember your login details? Read more... ×
Sign in to follow this  
freespace

For the lols

Recommended Posts

Hrm. Proof via reductio ad absurdum...

 

Assumption: It is possible to know if a program is susceptible to infinite-looping

 

Assertion 1: Therefore there would be a list of programs which you know are not susceptible to infinite-looping

 

Assertion 2: Therefore there would be a list of programs that you know will halt.

 

My good man, that is ABSURD! You can not know for sure that a program halts. Therefore assumption must be wrong

 

QED.

 

Hrm, on second thought that logic is not too airtight. I'm sure there is a proof to be thought up, and that it's along the lines of all programs are susceptible to infinite-looping...

 

[edit]: Got it!

 

Assumption: There is a program which is not susceptible to infinite-looping.

 

Assertion 1: Therefore there would be a program which you knew would halt.

 

That is a contradiction, there can not be a program which you knew did not halt. Therefore the assumption must be wrong. Therefore all programs are susceptible to infinite looping.

 

QED

 

Which means that I should go in and undercut all the current bids :P

 

Rob.

Edited by robzy

Share this post


Link to post
Share on other sites

Not quite.

 

For example, a program is not susceptible to halting if it has no loops, conditionals, or function calls

 

The halting problem is for _all possible pairs of program and input_.

 

If you had a program which works 90% of the time, it still doesn't solve the halting problem, but it might meet the specification for a solution which detects whether a program is "susceptible" to halting.

Edited by freespace

Share this post


Link to post
Share on other sites

Aw dang. I was so proud of myself for a second there :P

 

Although I will say that I don't have much appreciation for your definition of susceptibility :P

 

[edit]: Oh, come to think of it. A program that did not have any loops, conditionals or function calls would only have a single state - right? So perhaps a question of susceptibility comes down to how many states a program can have?

 

Rob.

Edited by robzy

Share this post


Link to post
Share on other sites

[edit]: Oh, come to think of it. A program that did not have any loops, conditionals or function calls would only have a single state - right? So perhaps a question of susceptibility comes down to how many states a program can have?

I don't think so, it would just be a program which advanced through states unconditionally.

Share this post


Link to post
Share on other sites

[edit]: Oh, come to think of it. A program that did not have any loops, conditionals or function calls would only have a single state - right? So perhaps a question of susceptibility comes down to how many states a program can have?

I don't think so, it would just be a program which advanced through states unconditionally.

 

Hrm, that's a good point.

 

And... after reading the intro to the wikipedia article again I see my problem. I'm assuming that the halting problem states that you can never know if any program will halt or not. In actual fact it says you can't know about this for all problems.

 

This is what you were getting at when you pointed out "for all program-input" pairs, gotcha.

 

Rob.

Share this post


Link to post
Share on other sites

Oh, come to think of it. A program that did not have any loops, conditionals or function calls would only have a single state - right? So perhaps a question of susceptibility comes down to how many states a program can have?

Pretty much. If you have no function calls, conditions or loops, you've got a programme full of constants.

Share this post


Link to post
Share on other sites

Pretty much. If you have no function calls, conditions or loops, you've got a programme full of constants.

Is that still technically a program?

Share this post


Link to post
Share on other sites

Pretty much. If you have no function calls, conditions or loops, you've got a programme full of constants.

Is that still technically a program?

 

I'd say not. If it has one state only then it doesn't actually *do* anything and couldn't be classified as a programme. A library of definitions maybe.

Share this post


Link to post
Share on other sites

I'd say not. If it has one state only then it doesn't actually *do* anything and couldn't be classified as a programme. A library of definitions maybe.

intput R;

A = r * 3.141

output A;

 

^--- That is a program, and it does something, it does a calculation. The fact that no loops or conditionals were needed is unimportant.

 

In the scope of this problem a program would surely be defined as something along the lines of "a list of instructions", which that is.

 

Rob.

Share this post


Link to post
Share on other sites

Technically, your calculation is calling a method....

 

A list of only variables would not be a program.

Share this post


Link to post
Share on other sites

Technically, your calculation is calling a method....

No it is call a program. It is a list of instructions which controls what the machine does. Ergo, it is a program.

 

For example, a sequence of turtle commands to draw say, a square, is a program.

Share this post


Link to post
Share on other sites

A list of only variables would not be a program.

Incorrect.

 

a = 5
b = 3
d = 6

^-- That is a program. The computer has to read and act on (execute) each of those instructions.

 

Rob.

Share this post


Link to post
Share on other sites

Technically, your calculation is calling a method....

No it is call a program. It is a list of instructions which controls what the machine does. Ergo, it is a program.

 

For example, a sequence of turtle commands to draw say, a square, is a program.

 

I was not disputing that, just that a list of only variables could be a program.

 

 

A list of only variables would not be a program.

Incorrect.

 

a = 5
b = 3
d = 6

^-- That is a program. The computer has to read and act on (execute) each of those instructions.

 

Rob.

 

I'm not convinced that assigning variables is a list of instructions that are executed on. The computer will assign those variables...but generally a program will execute instructions based on information..variables. It seems wrong at some level to say that a program only having variables is still a program. Indeed, such a 'program' will not compile in most main languages.

Share this post


Link to post
Share on other sites

I'd say not. If it has one state only then it doesn't actually *do* anything and couldn't be classified as a programme. A library of definitions maybe.

intput R;

A = r * 3.141

output A;

 

^--- That is a program, and it does something, it does a calculation. The fact that no loops or conditionals were needed is unimportant.

 

In the scope of this problem a program would surely be defined as something along the lines of "a list of instructions", which that is.

 

Rob.

 

input and output are functions.

 

 

A list of only variables would not be a program.

Incorrect.

 

a = 5
b = 3
d = 6

^-- That is a program. The computer has to read and act on (execute) each of those instructions.

 

Rob.

 

Yeah? What if the compiler just goes "fuck off, that's a bunch of contants" and does nothing :)

Compiler optimisations would hopefully not make execute those instructions, as it should detect they never change and are never used.

Share this post


Link to post
Share on other sites

input and output are functions.

Not necessarily, they could be #defines.

 

Yeah? What if the compiler just goes "fuck off, that's a bunch of contants" and does nothing :)

Compiler optimisations would hopefully not make execute those instructions, as it should detect they never change and are never used.

This is irrelevant. The action of the compiler has no bearing on whether a sequence of instructions is a program. The compiler could go fuck off for any program, and thus make all program not a program.

 

Further, those variable could map to special hardware registers, in which case robzy's program is configuring the hardware, and the compiler is broken for "optimising them away".

Edited by freespace

Share this post


Link to post
Share on other sites

Yeah? What if the compiler just goes "fuck off, that's a bunch of contants" and does nothing :)

Compiler optimisations would hopefully not make execute those instructions, as it should detect they never change and are never used.

You're thinking in too-high a level. You're thinking like a programmer, not a mathematician.

 

Rob.

Share this post


Link to post
Share on other sites

This is irrelevant. The action of the compiler has no bearing on whether a sequence of instructions is a program. The compiler could go fuck off for any program, and thus make all program not a program.

For programs with errors, this is true. For a 'correct' program, with 'correct' logic, such as simply declaring a variable, if it does not compile, then it is because it is not a program, at least not that the compiler can understand.

 

Further, those variable could map to special hardware registers, in which case robzy's program is configuring the hardware, and the compiler is broken for "optimising them away".

If that was the case, then it would not just be a collection of static variables, and so would be fine. The same thing in a high level language, is not a program. I'm pretty sure.

Share this post


Link to post
Share on other sites

For programs with errors, this is true. For a 'correct' program, with 'correct' logic, such as simply declaring a variable, if it does not compile, then it is because it is not a program, at least not that the compiler can understand.

Or, the compiler is sabotaged, or it was rigged, or the compiler is broken. If you think the compiler decides whether a source file contains a program, you are mistaken.

 

If that was the case, then it would not just be a collection of static variables, and so would be fine. The same thing in a high level language, is not a program. I'm pretty sure.

A high level language can still have variable which have special meaning. Also robzy never said it was a high level language. In any case, it is irrelevant:

 

A program is any sequence of instructions for the computer. Whether those instructions are useful, meaningful, are irrelevant. The only thing that matter is that the computer can interpret and execute the instructions.

 

See http://wordnetweb.princeton.edu/perl/webwn...omputer+program

Share this post


Link to post
Share on other sites

A program is any sequence of instructions for the computer. Whether those instructions are useful, meaningful, are irrelevant. The only thing that matter is that the computer can interpret and execute the instructions.

Indeed, the word compiler should not even come into this discussion. Even assembly is too high level. The pure machine code is what it's about.

 

For example, the program "20 A2 22 A3 24 A4" in Intel4004 code has no conditionals, loops, or anything like that. It simply sets the value of 3 pairs of registers and then implicitly halts.

 

Rob.

Edited by robzy

Share this post


Link to post
Share on other sites

Or, the compiler is sabotaged, or it was rigged, or the compiler is broken. If you think the compiler decides whether a source file contains a program, you are mistaken.

Indeed. I was talking about a fully functioning and correctly working compiler for our theoretical discussion. A compile can certainly aid in determining if a source file contains a correct program or not, under specific conditions.

 

A high level language can still have variable which have special meaning. Also robzy never said it was a high level language. In any case, it is irrelevant:

 

A program is any sequence of instructions for the computer. Whether those instructions are useful, meaningful, are irrelevant. The only thing that matter is that the computer can interpret and execute the instructions.

 

See http://wordnetweb.princeton.edu/perl/webwn...omputer+program

It's nice to see someone else who appreciates wordnet.

 

The level of language is certainly not irrelevant. What may be considered a valid program in a high level language(i.e. what constitutes instructions) can and does differ from what may be considered a valid program at a hardware level. For the low level you describe, there are no programs, only sequences of instructions. A program must have an entry point, for starters. The loader is responsible for placing variables into memory, not the program/process itself, and so the program does not actually execute any instructions....

 

 

Indeed, the word compiler should not even come into this discussion. Even assembly is too high level. The pure machine code is what it's about.

 

For example, the program "20 A2 22 A3 24 A4" in Intel4004 code has no conditionals, loops, or anything like that. It simply sets the value of 3 pairs of registers and then implicitly halts.

 

Rob.

I would argue that pure machine code does not constitute a program.

 

I guess this is getting into semantics now, but I don't consider a a sequence of hardware instructions at the lowest level of hardware to be a program.

Share this post


Link to post
Share on other sites

Indeed. I was talking about a fully functioning and correctly working compiler for our theoretical discussion. A compile can certainly aid in determining if a source file contains a correct program or not, under specific conditions.

A compiler does not decide what and what isn't a program.

 

It's nice to see someone else who appreciates wordnet.

 

The level of language is certainly not irrelevant. What may be considered a valid program in a high level language(i.e. what constitutes instructions) can and does differ from what may be considered a valid program at a hardware level. For the low level you describe, there are no programs, only sequences of instructions. A program must have an entry point, for starters. The loader is responsible for placing variables into memory, not the program/process itself, and so the program does not actually execute any instructions....

A program is a program, it doesn't matter what language you write it in. It certainly doesn't need "entry pointers", and it doesn't need a loader either. And of course the program doesn't execute any instructions - a program _is_ the instructions. Only the CPU can execute instructions.

 

I would argue that pure machine code does not constitute a program.

 

I guess this is getting into semantics now, but I don't consider a a sequence of hardware instructions at the lowest level of hardware to be a program.

Now you are just talking crap. All programs end up as "a sequence of hardware instructions at the lowest level of hardware". If those aren't "a group of instructions which can be interpreted and executed by a computer" I don't know what is.

Share this post


Link to post
Share on other sites

A compiler does not decide what and what isn't a program.

For a given language, it validates if a program is able to be compiled or not. That was the only point I made, as above...

 

A program is a program, it doesn't matter what language you write it in. It certainly doesn't need "entry pointers", and it doesn't need a loader either. And of course the program doesn't execute any instructions - a program _is_ the instructions. Only the CPU can execute instructions.

It's not as simple as that. If you think otherwise, perhaps you can write a program that can successfully be compiled in a high level language, only declaring constants, and get it to execute instructions. I'd like to see that. Do you not draw a line?

 

Is a c++ source file containing just x = 1 + 1; a valid program despite the fact it can't compile? Is a shellscript declaring variables a program, despite the fact it calls on other processes? Do pure arbitrary hardware instructions without a logical grouping constitute a program?

 

Oh, and Entry Points and loaders...

 

All programs end up as "a sequence of hardware instructions at the lowest level of hardware". If those aren't "a group of instructions which can be interpreted and executed by a computer" I don't know what is.

I know that all programs end up as hardware instructions. Grouping hardware instructions into a program provides a level of abstraction. Without that level of abstraction, then you don't have a program anymore. Do you see what I'm getting at? You're not contradicting a thing I said.

Edited by TheSecret

Share this post


Link to post
Share on other sites

For a given language, it validates if a program is able to be compiled or not. That was the only point I made, as above...

Not necessarily. The compiler merely converts the syntax into machine code. A complier may enact whatever rules it wants to prevent compilation, but this doesn't mean it cannot be compiled.

 

It's not as simple as that. If you think otherwise, perhaps you can write a program that can successfully be compiled in a high level language, only declaring constants, and get it to execute instructions. I'd like to see that.

It's possible. It comes down to what the compiler deems incorrect according to specifications.

 

I know that all programs end up as hardware instructions. Grouping hardware instructions into a program provides a level of abstraction. Without that level of abstraction, then you don't have a program anymore. Do you see what I'm getting at? You're not contradicting a thing I said.

You could argue that declaring constants in a higher level syntax is a form of abstraction. Writing it in assembly would require extra knowledge of the instructions sets, which in turn is an abstraction of binary. Edited by .:Cyb3rGlitch:.

Share this post


Link to post
Share on other sites

Indeed, the word compiler should not even come into this discussion. Even assembly is too high level. The pure machine code is what it's about.

 

For example, the program "20 A2 22 A3 24 A4" in Intel4004 code has no conditionals, loops, or anything like that. It simply sets the value of 3 pairs of registers and then implicitly halts.

 

Rob.

I would argue that pure machine code does not constitute a program.

 

I guess this is getting into semantics now, but I don't consider a a sequence of hardware instructions at the lowest level of hardware to be a program.

 

If you say that then it is clear that you do not understand the halting problem.

 

Rob.

Edited by robzy

Share this post


Link to post
Share on other sites

what does 10101110111001110010101101011110 mean to my computer?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×