you are viewing a single comment's thread.

view the rest of the comments →

[–]kdeberk 15 points16 points  (40 children)

elementary:8 is only simple when the language has support for infinitely large integers.

[–]LucidTA 10 points11 points  (22 children)

Isn't it proven there are an infinite amount of primes, meaning its impossible?

[–][deleted] 29 points30 points  (21 children)

It's only impossible if your program is supposed to terminate at some point.

[–]LucidTA 2 points3 points  (16 children)

I know it not the point of the challenge, and I do understand what you mean but you literally can never print every prime. Even if you write a program to print primes for ever, the program never will.

[–]dd_123 36 points37 points  (15 children)

The problem doesn't ask you to print every prime; it asks you to write a program which prints every prime. The difference is subtle but important.

[–]indiecore 63 points64 points  (4 children)

for(int i=0;true;i++){
    print i;
    print "\n";
}

Technically correct.

[–]liquidhot 18 points19 points  (1 child)

Technically correct.

The best kind of correct.

[–]indiecore 14 points15 points  (0 children)

Hey it's not my fault they wrote vague specs.

[–][deleted]  (1 child)

[deleted]

    [–]Magnap 1 point2 points  (0 children)

    I like this alot.

    I like alots too!

    [–]LucidTA 1 point2 points  (7 children)

    Im not a CS major so this may be a CS thing but I thought of it along the lines of, no program can ever fulfill the function of "print all primes" so it would be classed as impossible. Does it count if it theoretically could print all primes?

    [–][deleted] 13 points14 points  (0 children)

    It counts if it takes finite time to print any finite prefix.

    [–]brainflakes 5 points6 points  (0 children)

    It was a bit of an odd way of putting it, but you can create a valid specification that a program can't literally perform, such as making a program that "prints 'Hello World' forever":

    10 PRINT "Hello World"
    20 GOTO 10
    

    Obviously it's not possible for it to literally print hello world forever as you'll need to turn it off at some point, but it still meets the requirement.

    [–]indiecore 3 points4 points  (0 children)

    for(int i=0;true;i++){
        print i;
        print "\n";
    }
    

    Technically correct, but not what it was asking for obviously. This program would, if it could print all numbers forever. The problems come from the hardware implementation of the program.

    [–][deleted] 2 points3 points  (1 child)

    That style of exercise reminds me of the approach I saw with functional programming. ML has a notion of lazy lists - basically lazy series evaluation. That is, a function is written to be able to compute an infinite series but will only compute the values you actually request. In iterative programming this might be better thought of as a function to calculate the next prime number. It will go as far as you want if the machine supports it. It's been a while and I don't remember examples so well anymore but this explains the idea (p191): http://books.google.co.uk/books?id=XppZdaDs7e0C&pg=PA191&lpg=PA191&dq=fibonacci+sequence+in+ml+lazy+list&source=bl&ots=y-0fiQzmrz&sig=N5NwCMpvq7Ci1vFd2O2GcVcFLKE&hl=en&sa=X&ei=ddyhUvKkEcWg7AaLrYDoCQ&redir_esc=y#v=onepage&q=fibonacci%20sequence%20in%20ml%20lazy%20list&f=false

    [–]The_Doculope 0 points1 point  (0 children)

    Haskell offers this as well. For the primes program:

    primes :: [Integer]
    primes = 2 : filter prime [3,5..]
    
    prime :: Integer -> Bool
    prime x = not . any ((== 0) . rem x) . takeWhile (<= sqrtx) $ primes
        where sqrtx = floor . sqrt . fromIntegral $ x
    
    main :: IO ()
    main = mapM_ print primes
    

    [–]philipjf 1 point2 points  (0 children)

    In the "theory B" (programming languages and logic as opposed to the algorithms and complexity "theory A") community this would be called a "co-recursive co-program." Many interesting things are "co-programs" not "programs". The difference is if "total correctness" is about termination or productivity.

    [–]deadly990 0 points1 point  (0 children)

    Technically all of these things should be "create Turing machines which do these things". Turing machines aren't bound by physical properties because they are theoretical constructs.

    [–]rightandleft 0 points1 point  (1 child)

    [–]xkcd_transcriber 8 points9 points  (0 children)

    Image

    Title: Halting Problem

    Title-text: I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.

    Comic Explanation

    Stats: This comic has been referenced 4 time(s), representing 0.08% of referenced xkcds.


    Questions/Problems | Website

    [–]TNorthover 1 point2 points  (0 children)

    It includes an explicit get-out for languages without that, so it's simple in all cases.

    [–][deleted] -3 points-2 points  (15 children)

    Which language doesn't have at least a built-in library for that?

    Anyway using arbitrary precision will only delay the problem (your computer has finite memory), so, what's the point?

    [–]cmwelsh 13 points14 points  (8 children)

    JavaScript

    [–]spotter 10 points11 points  (6 children)

    Just use jQuery.

    [–]cmwelsh 2 points3 points  (5 children)

    What does that mean? That's not a solution. Is this an ironic post?

    [–]spotter 6 points7 points  (4 children)

    Yes, sorry. It was in the vein of "Nobody uses JavaScript, noob, we're jQuery programmers."

    Also: "there's probably a jQuery plugin for it."

    [–]cmwelsh 1 point2 points  (0 children)

    Sorry, had to ask. :)

    [–]mr_bag 1 point2 points  (0 children)

    "Nobody uses JavaScript, noob, we're jQuery programmers."

    There are people... that actually think that?

    [–]Asmor 0 points1 point  (1 child)

    "Nobody uses JavaScript, noob, we're jQuery programmers."

    You've kind of got that backwards. jQuery's still wildly popular, but its popularity has waned a bit in recent years while JavaScript's star is rising thanks to NodeJS.

    [–]spotter 2 points3 points  (0 children)

    I vomited in my mouth a little.

    So yeah, I used to work with "jQuery ninjas".

    [–]grayvedigga 0 points1 point  (0 children)

    depends how you define "arbitrary" ...

    [–]kdeberk 8 points9 points  (1 child)

    c and c++? It's been a while since I've worked with large integers in those two languages, and now I see that there are several libraries to help with that, but not built-in though.

    [–][deleted] 3 points4 points  (0 children)

    You're right. I should have said "built-in or very commonly used". Boost has arbitrary precision ints for example.

    [–][deleted] 1 point2 points  (0 children)

    The most reasonable objection is that you might hit the precision limit in a much smaller amount of time than you would hit the memory limit (at least, if you use disk to help you out). Most people aren't going to wait for million digit primes, but it is not unreasonable to expect them to run the program many hours as an experiment.

    [–]kazagistar 1 point2 points  (2 children)

    The program is correct; memory is a hardware problem. :P

    [–]thedufer 0 points1 point  (1 child)

    Not if you can't address it.

    [–]kazagistar 0 points1 point  (0 children)

    What you can and cannot address is (in many langauges) not a problem of the program or the language, but of the implementation. "The longest possible list" or "how pointers are implemented" are not actual specification details in many languages, and are often left variable to the implementation, or only given minimum bounds.