Computing Fundamentals Flashcards
Definition Computing
= performing calculations in accordance with effective methods
first generation computers
built in 1940 & 1950s
- enormous machines
- constisting several thousand vacuum tubes
- fraction of power of the computer today
ENIAC and colossus
second generation computers
- transistors replace vacuum tubes form mid 1950s
- small, use little power → smaller, faster & more reliable machines
third generation computers
- integrated circuits introduced in 1960
- massive increase in computational storage → integration of >billion of transistors
- keyboard, monitors and operating system
fourth generation computers
- microprocessor → single chip contains all computer components
- thousands of integrated circuits on single chip
- smaller and faster machines → home computers form mid-1970s
Intel P4004, Apple II
von Neumann architecture
- earliest computer manual rewiring for solving different problem
- today: general purpose → variety of programs can be run
- stores data and instructions in same memory
computer hardware components
- central processing unit: interacts with main memory; execute program instructions
- main memory: stores programs, operations & results of calculations
- bus: informaition flow
- different controler: output
central processing unit CPU
Arithmetic/logic unit: makes calculations and decisions
Control unit: controls processing steps and transfer
Register: provides small and fast amount of memory
Main memory
- different memory locations with unique addresses → to call stored variable
- every address housed by 1 byte (8 bit)
- larger values stored in consecutive memory locations
- volatile → main memory stores information when it is used
secondary memory
permanent memory, non-volatile, not as fast as main memory
- hard disc: based on magnetic media
- USB: consists integraed circuits
peripheral devices
connecte to the bus via controller
- input devices: keyboard, mouse, camera
- output devices: monitor, printer, speaker
Fetch - decode- execute- cycle
- Fetch: CPU fetches instruction form main memory
- Decoding: defines what kind of instruction needs to be executed
- Execute: only small caluclation performed at a time
theoretical computing machines
definition: abstract models of computing, eveloped to understand and treat computing and its limits by mathematical means
Entscheidungsproblem
Hilbert: Is there some mechanical procedure for answering all mathematical problems, belonging to some broad-ranging, well-defined class?
Turing: Is there an universal algrithm for deciding whether a Turing machine will ever stop? → no Turing machine exists
Turing machine
primitive model of mechanical device with same basic capabilities as human computer
- simple & useful abstract model of computation
- generally enough to embody computer program
Turing machine components
- Tape: no lenght limit, act as memroy, squares ( can be written with symbols)
- Tape head: can read and write symbols on tape & moves tape or moves along tape
- control unit: transition or program logic & state register
formal definition of touring machine
→ 7 touple
Q is a finite set of states → e.g. Q = {A, H}
q0 ∈ Q is the initial state → e.g. A
F ∈ Q is a set of halt or final states → e.g. F = {H}
Γ is a finite set of tape symbols → e.g. Γ = {0,1, ☐}
b ∈ Γ is the blank symbol → e.g. b = ☐
Σ ⊂ Γ is a set of input symbols → e.g. Σ = {0,1}
δ is the transition function
Mathematicel idealisation of Turing Machine
- unlimited nature of input, calculation space & output
- ideal approximation by today’s computer
Church-Turing-Thesis
- machines of this type can perform any mechanical operation
- Turing machine does define what is meant by algorithmic procedure
Universal Turing Machine
- coding instructions of arbitrary Turing machine T into a string of 0s and 1s → represented on a tape
- Tape used as intial part for some particular Turing machine U
- U = universal Turing machine → simulate arbitrary Turing machine
increment program counter
The program counter is a register that contains the address of the next instruction to be executed
How are the two states of the Turing machine defined and through what action does the state change from one to the other?
𝑄 is a finite set of states, e.g. Q={𝐴,𝐻}, and defined by the programmer/application.
𝛿 is the transition function and defines the state changes.
