[FOM] universal machine as a primitive instruction

[Dustin Wehr]

Most named complexity classes have universal machines. Interesting
exceptions, for which it is open whether they have universal machines,
include BPP and NP intersect coNP. Classes not known to have universal
machines are sometimes called "semantic classes".

>> Is Turing-computable the only notion of computability
>> that supports a universal machine?
>
> I would say no. Because if you take combinatory logic without the
> combinator K but with only S and * then you get a notion of computability
> that supports a universal machine but is  not Turing-computable...hmmm...
> is it right?
>
> D.