Computer Science – Logic in Computer Science
Scientific paper
2009-10-29
Computer Science
Logic in Computer Science
37 pages; missing equations in table 3 added; combined with arXiv:0911.1851 [cs.PL] and arXiv:0911.5018 [cs.LO]; introduction
Scientific paper
10.1007/s00236-012-0154-2
Instruction sequence is a key concept in practice, but it has as yet not come prominently into the picture in theoretical circles. This paper concerns instruction sequences, the behaviours produced by them under execution, the interaction between these behaviours and components of the execution environment, and two issues relating to computability theory. Positioning Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines, and taking instruction sequences as programs, we analyse the autosolvability requirement that a program of a certain kind must solve the halting problem for all programs of that kind. We present novel results concerning this autosolvability requirement. The analysis is streamlined by using the notion of a functional unit, which is an abstract state-based model of a machine. In the case where the behaviours exhibited by a component of an execution environment can be viewed as the behaviours of a machine in its different states, the behaviours concerned are completely determined by a functional unit. The above-mentioned analysis involves functional units whose possible states represent the possible contents of the tapes of Turing machines with a particular tape alphabet. We also investigate functional units whose possible states are the natural numbers. This investigation yields a novel computability result, viz. the existence of a universal computable functional unit for natural numbers.
Bergstra Jan Aldert
Middelburg C. A.
No associations
LandOfFree
Instruction sequence processing operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Instruction sequence processing operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction sequence processing operators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-404435