返回资讯中心
外部精选
软件工程
#开发者实时流

HOL Light Tutorial

Our formulation of the bug puzzle was a typical, if somewhat frivolous, example of a

Hacker News 最新stmonty2026/10/16 · 2026/10/169 分钟阅读

以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。

Our formulation of the bug puzzle was a typical, if somewhat frivolous, example of a so-called ‘state transition system’, which essentially consists of:

For the bug puzzle, the set of states is ℝ2 ×ℝ2 ×ℝ2, the ‘state’ being in this case the position of the three bugs. The transition relation is move, and tells us whether from one state we can pass ‘immediately’ to another state. The system can then evolve by starting in some initial state σ0 and passing through a sequence of states σ0 → σ2 → σ2 →⋯ according to the transition relation (τσiσi+1 for each i). We verified that a certain property I (having a specific oriented area) was an ‘invariant’, i.e. when I(σ) and τσσ′ then also I(σ′), and deduced from this the property we wanted.

A similar methodology is often useful in practical applications. The behaviour of a computer system can be modelled as a state transition system, where the state is roughly the complete contents of all storage cells (at least those relevant to the problem being considered) and the transition relation determined by the program. We will discuss more thoroughly the interpretation of a program as a transition relation in section 16, but an example should give the general idea. An assignment statement x := e in a programming language defines a transition from σ to σ′ precisely when state σ′ has these properties: (i) in state σ′, the variable x has the value resulting

from evaluating e in state σ, and (ii) all other variables have the same values in σ′ and σ. Although for an assignment statement the final state is completely determined by the initial state, it’s convenient to keep the generality of a relation since this allows us to consider nondeterministic behaviour.

We will give here a simple example in concurrent programming lifted from Lamport (1994), consisting of two parallel instances of essentially the same program. Each program has three atomic instructions labelled 10, 20 and 30, and they use a shared semaphore variable sem to ensure that at most one of them can be in the ‘critical section’ (20 and 30) at any time. The critical sections just increment variables x and y respectively and restore the semaphore, but one could imagine something more interesting here such that the mutual exclusion property is important:

PROGRAM1 PROGRAM2

10: sem > 0 -> sem := sem - 1 10: sem > 0 -> sem := sem - 1 20: x := x + 1 20: y := y + 1 30: sem := sem + 1 30: sem := sem + 1

We assume both programs start at label 10 with x = y = 0 and sem = 1. The syntax g -> c means that execution must wait till the guard g is true, after which the command c can be executed. We assume that each single line is atomic, but that otherwise the executions of the two programs may be interleaved in any way (for example, by the operating system). The goal is to prove that whatever the order of interleaving, at least one program will be at the label 10 at any time, i.e. that we have mutual exclusion of the critical section 20/30.

In order to model this as a state transition system, we first fix the state. This will contain the values of the variables x, y and sem, together with two ‘program counters’ pc1 and pc2 indicating where the two programs are in their execution. We therefore choose the tuple of values (x,y,pc1,pc2,sem), lying in the state space ℕ5. (Of course, the detailed order of the variables in the state space makes no real difference as long as we’re consistent.) Although the start state is completely fixed, we will specify it as a predicate on states:

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →