Shingo GitHub

Assembly Language and Models of Computation

Annotated slides from MIT 6.004 (Spring 2017) Lecture 10.1, covering the UASM assembly language used for the Beta ISA and a concise introduction to models of computation, universality, and uncomputability.

Summary

The document explains how the UASM assembler translates symbolic assembly code into binary for the Beta processor. It describes key language features—symbols, labels, macros, expressions, and the dot (.) location counter—and shows how macro expansions assemble instruction fields, manage instruction formats, and support pseudoinstructions for readability. The second half shifts to foundational theory: finite state machines (FSMs) cannot handle unbounded counting; Turing machines (TMs) with an infinite tape overcome this limitation. By encoding a TM’s description as an integer, a Universal Turing Machine can emulate any TM, leading to the stored-program concept. Church’s Thesis asserts all realizable discrete computation is TM-computable. The Beta ISA (with conditional branches and arithmetic) is Turing universal. The lecture closes by proving the existence of uncomputable functions, notably the Halting problem, via a diagonalization argument.

Key Claims

  • Assembly language raises programming above raw binary by naming registers, instructions, and memory addresses.
  • UASM uses two-pass assembly: first to populate a symbol table, second to generate binary output.
  • Macros such as BETAOP and BETAOPC hide the bit-level composition of Beta instructions.
  • Pseudoinstructions (e.g., CMOVE, PUSH, POP) improve code clarity without adding hardware.
  • FSMs cannot decide whether a string of parentheses is well‑formed because they lack unbounded counting.
  • A Turing machine’s behavior can be captured as an integer function; TMs can be enumerated by an index.
  • A Universal Turing Machine exists and can execute any TM’s program given its index; this is the theoretical basis for general‑purpose computers.
  • An ISA with conditional branching and basic arithmetic is Turing universal (the Beta qualifies).
  • The Halting function (f_H(k, j): does TM k halt on input j?) is provably uncomputable; no algorithm can determine it in finite steps.