Computing Fundamentals

Question 1

Definition Computing

Answer 1

= performing calculations in accordance with effective methods

Question 2

first generation computers

Answer 2

built in 1940 & 1950s
- enormous machines
- constisting several thousand vacuum tubes
- fraction of power of the computer today
ENIAC and colossus

Question 3

second generation computers

Answer 3

• transistors replace vacuum tubes form mid 1950s

- small, use little power → smaller, faster & more reliable machines

Question 4

third generation computers

Answer 4

• integrated circuits introduced in 1960
• massive increase in computational storage → integration of >billion of transistors
• keyboard, monitors and operating system

Question 5

fourth generation computers

Answer 5

• 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

Question 6

von Neumann architecture

Answer 6

• earliest computer manual rewiring for solving different problem
• today: general purpose → variety of programs can be run
• stores data and instructions in same memory

Question 7

computer hardware components

Answer 7

• central processing unit: interacts with main memory; execute program instructions
• main memory: stores programs, operations & results of calculations
• bus: informaition flow
• different controler: output

Question 8

central processing unit CPU

Answer 8

Arithmetic/logic unit: makes calculations and decisions
Control unit: controls processing steps and transfer
Register: provides small and fast amount of memory

Question 9

Main memory

Answer 9

• 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

Question 10

secondary memory

Answer 10

permanent memory, non-volatile, not as fast as main memory

• hard disc: based on magnetic media
• USB: consists integraed circuits

Question 11

peripheral devices

Answer 11

connecte to the bus via controller

• input devices: keyboard, mouse, camera
• output devices: monitor, printer, speaker

Question 12

Fetch - decode- execute- cycle

Answer 12

• 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

Question 13

theoretical computing machines

Answer 13

definition: abstract models of computing, eveloped to understand and treat computing and its limits by mathematical means

Question 14

Entscheidungsproblem

Answer 14

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

Question 15

Turing machine

Answer 15

primitive model of mechanical device with same basic capabilities as human computer

• simple & useful abstract model of computation
• generally enough to embody computer program

Question 16

Turing machine components

Answer 16

• 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

Question 17

formal definition of touring machine

→ 7 touple

Answer 17

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

Question 18

Mathematicel idealisation of Turing Machine

Answer 18

• unlimited nature of input, calculation space & output

- ideal approximation by today’s computer

Question 19

Church-Turing-Thesis

Answer 19

• machines of this type can perform any mechanical operation

- Turing machine does define what is meant by algorithmic procedure

Question 20

Universal Turing Machine

Answer 20

• 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

Question 21

increment program counter

Answer 21

The program counter is a register that contains the address of the next instruction to be executed

Question 22

How are the two states of the Turing machine defined and through what action does the state change from one to the other?

Answer 22

𝑄 is a finite set of states, e.g. Q={𝐴,𝐻}, and defined by the programmer/application.
𝛿 is the transition function and defines the state changes.