If the microcode can contain a lookup table, then of course you can perform any function that fits within the size of your lookup table. For example, a 256 entry x 5 bit table could be used to implement 4-bit + 4-bit addition with 5-bit result. Or any other function with two 4-bit inputs and a result of 5-bits or less.

If you were implementing this in a Xilinx FPGA, for example, a 4-bit + 4-bit to 5-bit table would take 20 LUTs (5 x slice-M). For perspective, this is like 0.1% of a low end Artix-7 35-size FPGA.

The lookup table approach doesn't scale well though. Even a table taking two 8-bit operands would need 65,536 entries.

Instead of outright eliminating the ALU, you can use a smaller ALU (like 4 bits wide for example) + micro code to implement wider instructions (8/16/32/64-bit). The tradeoff for having less ALU hardware is of course more clock cycles.

Taken to the extreme you could make a 2-bit ALU, and perform addition with carry 32 times in micro code to do a 32-bit add instruction.

If the microcode can contain a lookup table, then of course you can perform any function that fits within the size of your lookup table. For example, a 256 entry x 5 bit table could be used to implement 4-bit + 4-bit addition with 5-bit result. Or any other function with two 4-bit inputs and a result of 5-bits or less.

If you were implementing this in a Xilinx FPGA, for example, a 4-bit + 4-bit to 5-bit table would take 20 LUTs (5 x slice-M). For perspective, this is like 0.1% of a low end Artix-7 35-size FPGA.

The lookup table approach doesn't scale well though. Even a table taking two 8-bit operands would need 65,536 entries.

Instead of outright eliminating the ALU, you can also use a smaller ALU (like 4 bits wide for example) + micro code to implement wider instructions (8/16/32/64-bit). The tradeoff for having less ALU hardware is of course more clock cycles.

Taken to the extreme you could make a 2-bit ALU, and perform addition with carry 32 times in micro code to do a 32-bit add instruction.