Information Technology Reference
In-Depth Information
information model, which is the research synthesis of scientific evidence related to
human information process. The fifth chapter briefly discusses future work and
preparing experiments which will be essential for future research and hypothesis
verification.
2 Critical Review: Open Problems in Computer Science
2.1 Physical Walls
Computer science has already faced physical walls in implementation of logical gates,
in silicon chip (concerning size, overheating, unsustainable power consumption).
Therefore researchers and chip industries are switching to HW and SW paralleliza-
tion. Nowadays parallel switch help us to survive in trend of performance growth
(approximately doubling every 18 months) [3]. But once it is done (maximal parallel
speedup is reached) there is no obvious clue how to continue this settled performance
growth (one cannot parallelize task that was completely parallelized before) [6].
Here we can also recall Feynman [8] research question: “ How small can you make
a computer ?” Gordon Moor himself is also expecting that his law is limited by eco-
nomics, including the rising cost of advanced lithography and new wafer fabs [22].
Although advanced lithography is still promising the decreasing (shrinking) of chip
size design, at current rate of lithography scaling (~0.7 every two years), the industry
will reach the length scale of atomic crystal lattices (order 1nm) by mid 2040s.
2.2 Theoretical Walls
Theoretical walls are open questions closely related to computational model (Turing
machine, TM) and its implementation consequences which are restricted by physical
limitation (as described above). Here we can list undecidable problems like (Halting
Problem, Post Correspondence Problem), NP-hard and NP-complete problems like
(Travelling Salesman Problem, SAT Problem, Knapsack Problem, Graph Coloring
Problem). However, any problem in category of undecidable problems (e.g. Halting
problem) or in category of NP-complete walls (e.g. 3-SAT problem) is not efficiently
solvable by using classical computation methodology.
Beside the fact there exist theoretical computational models more powerful than
TM, like TM with Oracle, Iterative TM with advice, Site machines (reflecting capa-
bility of distributed computing and modern personal computer non-uniform computa-
tion), real number models, variants of neural networks with real numbers [34], due to
the infinite descriptive properties it is not possible to implement it efficiently and use
in practice. Thus effective “ artificial ” computable theoretical model remains bounded
by Turing machine.
In spite the Turing Machine model is formally described, closely related Church-
Turing hypothesis is still an open question itself and needs formalization so that it can
be finally proved or disproved (confirmed or disconfirmed).
2.3 Human-Computer Walls
Beside the physical and theoretical walls computer science is also dealing with many
human-computer interaction (HCI) problems/issues which are consequences of
Search WWH ::




Custom Search