Is VHDL Turing complete?

Question

Is VHDL Turing complete? My understanding is that VHDL creates a register machine, and that register machines - without arbitrary RAM - aren't Turing complete.

Is this accurate? For problems that can't be solved in register machines, is there a standard approach - use RAM outside the VHDL, and manage it via VHDL, for instance?

Answer 1

There are 3 main criteria for Turing Completeness:

1. Sequence. do this thing and then do that thing and then do the other thing
2. Selection. if this then something
3. Iteration (or recursion). do this over and over until this

The requirement for memory is not that it be infinite (which is impossible with modern technology, and all languages would fail), but that it be unbounded, or infinitely extendible: ie. if you run out, you can add more and try again.

So yes, I think VHDL certainly qualifies. It can do all that stuff.

Answer 2

Another way to show turing completeness is a chain of transformations:

1. Turing Machines are turing complete.
2. Turing Machines can be simulated by register machines and vice versa.
3. Register machines are an abstract and simple model of a modern processor
4. You can describe a processor with VHDL

So VHDL is turing complete.