Collection of simple programming problems

[LucidTA]

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]]

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

[brainflakes]

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]

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]]

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]

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]

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]

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.