> What is the minimum required for a fully-functional programming
> language?(i.e. one in which, theoretically, you could perform any
> calculation).
Well, Minsky's register machines are Turing-strong, and they just have
increment and decrement (by one), but the decrement is a conditional
that jumps to one place if it succeeds and to another if you try to
decrement a register whose value is zero.

> iirc machine code seems to get by purely on 'ifs' and assignments -
> would in theory a language be functional that only had these two
> functions (and presumably the ability to loop over the whole code, but
> not individual sections of it).
I designed a processor over the Summer that had about 20 instructions:
the usual set of arithmetic (add, subtract, etc.) and logical
(or, and, etc.) operations, instructions to load from and store to
memory, a few types of branch, and an if. However, it is possible to
make do with only one instruction:
subtract-and-write-back-conditionally-branching. Computers like this
(which are entirely theoretical, nobody would want to use something like
this) are called single instruction computers (SICs).

Daniel

-- 
A most peculiar man    With the windows closed      And Mrs Reardon says
He died last Saturday  So he'd never wake up  He has a brother somewhere
He turned on the gas   To his silent world   Who should be notified soon
And he went to sleep   And his tiny room    .oO( http://sad.istic.org/ )

Post a reply to this message