Universal Turing Machine

Question 1

What are models of computations

Answer 1

• Abstract notion of computation
• Models which describe how an output is computed given an input

Question 2

What are UTMs

Answer 2

• The idea of connecting multiple Turing machines together
• A machine that can simulate other machines
• Where TMs can be fed as inputs into other TMs
  
  • Where computing devices can perform computations on other computing devices

Question 3

What are the features of UTM?

Answer 3

Features of UTM

• A TM that can simulate a arbitrary TM on an arbitrary input
• Simulates any other machine
• Is reprogrammable
• Reads the definition of simulated TM as well as the tape of simulated TM from its own tape

Question 4

What is the structure of UTM

Answer 4

• UTM has three bits of information that the machine is simulating
  
  • Basic description of the machine
  • The contents of the machine tape
  • Internal state of the machine
• The state and tape contents allow for control of the machine by changing its state based on that info
• Computer running other computeres

Question 5

How does UTMs work step by step?

Answer 5

• Look at contents of tape and the state to determine configuration of machine
• Then consult the description of the machine to see what should be done with the produced config
• State should then be modified to reflect the result of the move

Question 6

What is the Church-Turning Thesis?

Answer 6

Question 7

What are the limits of computability?

Answer 7

Cant solve undecidable problems

• No way, even give unlimited resources and infinite amount of time
• That the problem can be decided by algorithmic means

Question 8

What is the halting problem?

Answer 8

Write a program that given a program as an input can answer the question if
the program halts or loops forever.

Can we trust autonomous drones and weapons to choose the right target if
(and when) used in a war zone?