show/hide this revision's text 3 clarified last sentence

The best model depends upon the hardware being considered.

I agree with Joel David Hamkin's answer and with Mark Sapir's answer. The point of computability models, such as Turing machines, regular languages, push-down automata with stacks, etc., is to show the equivalence of these models. THe reason for the big-O notation order of complexity is to show that, within a small additive constant, complexity can be defined in terms of a linear, polynomial, or exponential (or otherish) relation to a particular characteristic factor of the input (usually the size of the input). The only thing that changes for that computation on different systems is a multiplicative factor, or the additive constant.

Kolmogorov talks about quantitating this type of complexity based on abstract state machines, and coming up with a minimal-descriptor length type of explanation of complexity, and prefix-complexity.

Complexity can refer to

  • space-complexity, how much memory (RAM, lengths and numbers of tapes of Turing machines, how much space on a 2-d grid for a 2-d turing machine, how much of the stacks for push-down stack automata) is required to perform the calculation, as a function of the size or characteristic of the input

  • time-complexity, how much time (number of computation steps, number of movements of the read-head + number of movements of the write-head, number of clicks of the clock = crystal-oscillator for the CPU circuits for synchronous logic circuitry)

  • logic complexity (~? algorithmic complexity ?) - how many gates (AND, NOT, OR, XOR, NOR, flip-flops, latches, multiplexors, demultiplexors, line traces) are required to build the circuit (e.g. how can you implement a shift-bit-adder with silicon logic using only NPN transistors or only TTL logic), how many transistors, how many relays and wires, how much "surface area" for a 2-d instantiation of a circuit on a LSI / VLSI large-scale-integration very-large-scale-integrated circuit chip, how much "volume" for a 3-d multi-layer VLSI circuit chip, how many traces of the FPGA (field programmable gate array) are required to implement the algorithm in hardware, i.e. how large is the program to describe/implement the algorithm

However, the computer science courses that talk about computability theory are talking about these concepts abstractly, even when they talk about it for a particular algorithm, or even for a particular circuit (like a bit-adder with carry-over shifting) in electrical engineering circuit design classes.

The best model depends upon the hardware being considered.

A model for data-flow in the Connection Machine with a 10-dimensional hyper-cube network architecture for its 1024 processors and single-bit processing is not going to be an adequate model for data-flow in a TCP/IP 10-gigabit ethernet network connected Beowulf cluster with 1024 nodes consisting of hex-core 64-bit processors, or for a Tilera cluster of 16 chips with 64 cores per chip with multiple orders of communication latency difference between intra-chip vs. inter-chip communication time delays.

Or a model for SIMD (single instruction multiple data) type of parallelization is not going to be reasonable for a model of GPU (graphical processing unit) computation using the GPU as a co-processor.

It is not reasonable to speak of a "best model" without specifying the hardware, or at least the architecture, and the limits of the amount of RAM available (at the different levels of use and speed, level I cache, level II cache, ..., RAM dedicated to one CPU, RAM shared between multiple CPUs, RAM that will be swapped out to disk/hard drive, external NAS=network attached storage), and the algorithms and processes which are to be optimized and analyzed for complexity.

show/hide this revision's text 2 corrected spelling "added -> adder"

The best model depends upon the hardware being considered.

I agree with Joel David Hamkin's answer and with Mark Sapir's answer. The point of computability models, such as Turing machines, regular languages, push-down automata with stacks, etc., is to show the equivalence of these models. THe reason for the big-O notation order of complexity is to show that, within a small additive constant, complexity can be defined in terms of a linear, polynomial, or exponential (or otherish) relation to a particular characteristic factor of the input (usually the size of the input). The only thing that changes for that computation on different systems is a multiplicative factor, or the additive constant.

Kolmogorov talks about quantitating this type of complexity based on abstract state machines, and coming up with a minimal-descriptor length type of explanation of complexity, and prefix-complexity.

Complexity can refer to

  • space-complexity, how much memory (RAM, lengths and numbers of tapes of Turing machines, how much space on a 2-d grid for a 2-d turing machine, how much of the stacks for push-down stack automata) is required to perform the calculation, as a function of the size or characteristic of the input

  • time-complexity, how much time (number of computation steps, number of movements of the read-head + number of movements of the write-head, number of clicks of the clock = crystal-oscillator for the CPU circuits for synchronous logic circuitry)

  • logic complexity (~? algorithmic complexity ?) - how many gates (AND, NOT, OR, XOR, NOR, flip-flops, latches, multiplexors, demultiplexors, line traces) are required to build the circuit (e.g. how can you implement a shift-bit-added shift-bit-adder with silicon logic using only NPN transistors or only TTL logic), how many transistors, how many relays and wires, how much "surface area" for a 2-d instantiation of a circuit on a LSI / VLSI large-scale-integration very-large-scale-integrated circuit chip, how much "volume" for a 3-d multi-layer VLSI circuit chip, how many traces of the FPGA (field programmable gate array) are required to implement the algorithm in hardware, i.e. how large is the program to describe/implement the algorithm

However, the computer science courses that talk about computability theory are talking about these concepts abstractly, even when they talk about it for a particular algorithm, or even for a particular circuit (like a bit-adder with carry-over shifting) in electrical engineering circuit design classes.

The best model depends upon the hardware being considered.

A model for data-flow in the Connection Machine with a 10-dimensional hyper-cube network architecture for its 1024 processors and single-bit processing is not going to be an adequate model for data-flow in a TCP/IP 10-gigabit ethernet network connected Beowulf cluster with 1024 nodes consisting of hex-core 64-bit processors, or for a Tilera cluster of 16 chips with 64 cores per chip with multiple orders of communication latency difference between intra-chip vs. inter-chip communication time delays.

Or a model for SIMD (single instruction multiple data) type of parallelization is not going to be reasonable for a model of GPU (graphical processing unit) computation using the GPU as a co-processor.

It is not reasonable to speak of a "best model" without specifying the hardware, or at least the architecture, and the limits of the amount of RAM available (at the different levels of use and speed, level I cache, level II cache, ..., RAM dedicated to one CPU, RAM shared between multiple CPUs, RAM that will be swapped out to disk/hard drive, external NAS=network attached storage), and the algorithms and processes to be optimized.

show/hide this revision's text 1

The best model depends upon the hardware being considered.

I agree with Joel David Hamkin's answer and with Mark Sapir's answer. The point of computability models, such as Turing machines, regular languages, push-down automata with stacks, etc., is to show the equivalence of these models. THe reason for the big-O notation order of complexity is to show that, within a small additive constant, complexity can be defined in terms of a linear, polynomial, or exponential (or otherish) relation to a particular characteristic factor of the input (usually the size of the input). The only thing that changes for that computation on different systems is a multiplicative factor, or the additive constant.

Kolmogorov talks about quantitating this type of complexity based on abstract state machines, and coming up with a minimal-descriptor length type of explanation of complexity, and prefix-complexity.

Complexity can refer to

  • space-complexity, how much memory (RAM, lengths and numbers of tapes of Turing machines, how much space on a 2-d grid for a 2-d turing machine, how much of the stacks for push-down stack automata) is required to perform the calculation, as a function of the size or characteristic of the input

  • time-complexity, how much time (number of computation steps, number of movements of the read-head + number of movements of the write-head, number of clicks of the clock = crystal-oscillator for the CPU circuits for synchronous logic circuitry)

  • logic complexity (~? algorithmic complexity ?) - how many gates (AND, NOT, OR, XOR, NOR, flip-flops, latches, multiplexors, demultiplexors, line traces) are required to build the circuit (e.g. how can you implement a shift-bit-added with silicon logic using only NPN transistors or only TTL logic), how many transistors, how many relays and wires, how much "surface area" for a 2-d instantiation of a circuit on a LSI / VLSI large-scale-integration very-large-scale-integrated circuit chip, how much "volume" for a 3-d multi-layer VLSI circuit chip, how many traces of the FPGA (field programmable gate array) are required to implement the algorithm in hardware, i.e. how large is the program to describe/implement the algorithm

However, the computer science courses that talk about computability theory are talking about these concepts abstractly, even when they talk about it for a particular algorithm, or even for a particular circuit (like a bit-adder with carry-over shifting) in electrical engineering circuit design classes.

The best model depends upon the hardware being considered.

A model for data-flow in the Connection Machine with a 10-dimensional hyper-cube network architecture for its 1024 processors and single-bit processing is not going to be an adequate model for data-flow in a TCP/IP 10-gigabit ethernet network connected Beowulf cluster with 1024 nodes consisting of hex-core 64-bit processors, or for a Tilera cluster of 16 chips with 64 cores per chip with multiple orders of communication latency difference between intra-chip vs. inter-chip communication time delays.

Or a model for SIMD (single instruction multiple data) type of parallelization is not going to be reasonable for a model of GPU (graphical processing unit) computation using the GPU as a co-processor.

It is not reasonable to speak of a "best model" without specifying the hardware, or at least the architecture, and the limits of the amount of RAM available (at the different levels of use and speed, level I cache, level II cache, ..., RAM dedicated to one CPU, RAM shared between multiple CPUs, RAM that will be swapped out to disk/hard drive, external NAS=network attached storage), and the algorithms and processes to be optimized.