[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Bytecode: Safe or not? / luac manual
- From: Tony Finch <dot@...>
- Date: Tue, 1 Nov 2011 15:44:40 +0000
Rob Kendrick <firstname.lastname@example.org> wrote:
> The halting problem is impossible to solve. A byte code verifier is a
> halting problem. Thus, a perfect byte code verifier cannot exist.
That isn't true. The proof obligation for safe bytecode is much simpler
than the halting problem, because it only needs to accept bytecode that
can be created by the Lua compiler. It is fine if the checker rejects some
programs that do not crash the interpreter. It is rather like a static
type checker in this respect.
f.anthony.n.finch <email@example.com> http://dotat.at/
Fair Isle, Faeroes: Southwest backing southeast 5 to 7, perhaps gale 8 later.
Rough, occasionally very rough. Squally showers. Good, occasionally moderate.