Invisible wrote:
> Question: Why is this undecidable?

It's due to a proof known as Matiyasevich's theorem which I'm not 
familiar with the details of offhand.  The gist is that you can show 
that every recursively enumerable set* can be represented as the roots 
of such a polynomial.  Since there are non-computable recursively 
enumerable sets there must be such polynomials (known as Diophantine 
equations) which are not computable.

If you're interested in the details, this paper looks like it might be 
useful, although I haven't read it myself:

http://modular.math.washington.edu/edu/Spring2003/21n/papers/hilbert10.pdf

If you're interested in the details, but less so, this is probably more 
useful:

http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

More intuitively, note that the problem statement come pretty close to 
having Fermat's last theorem as a subproblem.

> Surely it's a trivial matter of iterating over all integers and testing 
> whether any of them is a root?

If there is no solution to a given polynomial, when does this program 
you describe halt?



* A recursively enumerable set is defines as any set for which these 
exists an algorithm that will eventually list any number in the set, and 
no numbers that are not.  Note that the algorithm is not required to 
ever halt, so you can't , in general, be sure which numbers are not in 
the set and which are in the set but it just hasn't gotten around to 
listing yet.

An example of such a set which is not computable would be the set of 
numbers corresponding to the binary representations of all programs 
which eventually halt.

Post a reply to this message

Eero Ahonen wrote:
> I once made a Pong -clone with Pascal. It was very hard to beat the
> computer, since I saved memory and used the same variable for the Y-axis
> placement for computer player and the ball :).

Nice!

-- 
~Mike

Post a reply to this message

>> Question: Why is this undecidable?
> 
>> Surely it's a trivial matter of iterating over all integers and 
>> testing whether any of them is a root?
> 
> If there is no solution to a given polynomial, when does this program 
> you describe halt?

...so it's "undecidable" because you can't always figure out the answer 
in finite time?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:
>   However, I unfortunately have absolutely no experience in using it, nor
> do I know how easy it is to integrate in Visual Studio. Being a C library
> it will most probably be of a much lower level library than an abstract
> high-quality C++ library would be, and consequently probably hard to use.

There are a few SDL C++ wrappers.

This one looked quite good:
http://sdlmm.sourceforge.net/

This one seems to suck at a first quick look:
http://sdlpp.sourceforge.net/

Post a reply to this message

Invisible wrote:
> Indeed. Without having a way to talk to the native graphics control
> system to set up a drawing surface, OpenGL is no help. (There also seems
> to be some disagreement above whether you can use GLUT on Windows...)

Again libSDL :)

Post a reply to this message

scott wrote:
>> Sadly, I'm utterly uninspired about what to write past my first usual 
>> program, namely "Jotto".  Any suggestions?
> 
> How about something to solve/play a game, like Sudoku, checkers, connect 
> 4, poker etc.  Not a huge OO-based project, but certainly something to 
> get started with.

That would be ... "Jotto".  ;-)  A good idea, tho. :-)

I'm more into the data processing stuff than the heavy calculation stuff, 
altho fractals and CAs are always fun. I'll have to see what libraries I can 
find for stuff before I decide, methinks.

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message

Warp wrote:
>   Coding a small game is always fun, and a good environment for
> object-oriented design 

Thanks for the pointers to the graphics libraries. I'll check it out.

Any suggestions on libraries for things like regular expressions, parsing 
CSV files, talking to databases, things like that? Or do people just 
interface to C libraries for that sort of thing?

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message

Invisible wrote:
> ...and this is the reason why. Almost *no* languages have the capability 
> to easily draw graphics these days.

Tcl/Tk does, as well as anything built on top of Tk in general (including 
Perl, Python, and Erlang). ;-)  No 3D stuff, tho.

> This made me actually laugh out loud. For real. Such a glowing 
> recommendation of the Win32 API! :-D

It's definitely ugly, and it shows its heritage too.

> (OTOH, I understand that the raw X Windows bindings are even harder... 

If you want *raw* X Windows, try formatting the socket data yourself.

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message

Mike Raiford wrote:
> Eero Ahonen wrote:
>> I once made a Pong -clone with Pascal. It was very hard to beat the
>> computer, since I saved memory and used the same variable for the Y-axis
>> placement for computer player and the ball :).
> 
> Nice!
> 

Nobody even noticed anything. Couple of guys tested it and played for
something like hour oslt and just told me that it's freaking hard :D.

-Aero

Post a reply to this message

>> Indeed. Without having a way to talk to the native graphics control
>> system to set up a drawing surface, OpenGL is no help. (There also seems
>> to be some disagreement above whether you can use GLUT on Windows...)
> 
> Again libSDL :)

It seems to do lots of interesting stuff. Sadly, I can't get the Haskell 
bindings for it to work. :-(

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message