I feel like the question answers itself. Turing complete. Decidable. Pick one.