1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#!/bin/sh
#
# This script requires two arguments which are file names:
#
# 1. The name of a C source file which defines a three-valued halting
# decider function, whose prototype is:
#
# ternary halting_decider(const char *program, const char *input);
#
# This function tries to answer the question: does the program,
# when given the specified input, halt? It can return TRUE, or FALSE.
# It can also return ERROR when, for whatever reason, it deems
# that neither TRUE nor FALSE is the correct answer.
#
# 2. The name of a C source file which defines the following boolean
# function, which returns 0 or 1:
#
# int error_decider(const char *hdecider, const char *program,
# const char *input);
#
# Error decider functions try to answer the question: does the given
# program, when operating on the given input, behave in such
# a way that the given decider must return ERROR for that program?
#
set -e # stop on any errors
MYDIR=$(dirname "$0")
. "$MYDIR"/lib.sh
if [ $# != 2 ] ; then
printf "usage: $0 <halting_decider>.c <error_decider.c>\n"
exit 1
fi
ORIG_HALTING_DECIDER=$1
ORIG_ERROR_DECIDER=$2
HD_FULL_HASH=$(file_hash $ORIG_HALTING_DECIDER)
ED_FULL_HASH=$(file_hash $ORIG_ERROR_DECIDER)
HD_HASH=$(short_hash $HD_FULL_HASH)
ED_HASH=$(short_hash $ED_FULL_HASH)
HALTING_DECIDER=hd-${HD_HASH}.c
ERROR_DECIDER=ed-${ED_HASH}.c
cp $ORIG_HALTING_DECIDER $HALTING_DECIDER
cp $ORIG_ERROR_DECIDER $ERROR_DECIDER
PROGRAM_BASENAME=pg-${HD_HASH}-${ED_HASH}
printf "halting decider: %s\n" $HALTING_DECIDER
printf "error decider: %s\n" $ERROR_DECIDER
printf "\n"
printf "generating program %s from these deciders\n" $PROGRAM_BASENAME.c
cat > ${PROGRAM_BASENAME}.c <<!
#include <stdio.h>
#include <stdlib.h>
#include "ternary.h"
#define HD_HASH "$HD_HASH"
#define ED_HASH "$ED_HASH"
#define PG_BASE "$PROGRAM_BASENAME"
#define PG_SELF PG_BASE ".c"
#define HD_NAME "$HALTING_DECIDER"
#include "$ERROR_DECIDER"
#include "$HALTING_DECIDER"
int main(int argc, char **argv)
{
const char *input;
if (argc != 2) {
fprintf(stderr, "this program test case requires input\n");
return EXIT_FAILURE;
}
input = argv[1];
if (error_decider(HD_NAME, PG_SELF, input)) {
switch (halting_decider(PG_SELF, input)) {
case FALSE:
printf("decider %s RIGHT: %s/%s does not halt\n", HD_NAME, PG_SELF, input);
for(;;);
case TRUE:
printf("decider %s RIGHT: %s/%s halts\n", HD_NAME, PG_SELF, input);
return EXIT_SUCCESS;
case ERROR:
printf("decider %s WRONG: TRUE and FALSE are viable answers for %s/%s\n",
HD_NAME, PG_SELF, input);
abort();
}
} else {
switch (halting_decider(PG_SELF, input)) {
case FALSE:
printf("decider %s WRONG: %s/%s does not halt\n", HD_NAME, PG_SELF, input);
return EXIT_SUCCESS;
case TRUE:
printf("decider %s WRONG: %s/%s halts\n", HD_NAME, PG_SELF, input);
for(;;);
case ERROR:
printf("decider %s RIGHT: neither TRUE nor FALSE is correct for %s/%s\n",
HD_NAME, PG_SELF, input);
abort();
}
}
/* notreached */
puts("internal error");
abort();
}
!
printf "compiling %s to %s\n" $PROGRAM_BASENAME.c $PROGRAM_BASENAME
gcc $PROGRAM_BASENAME.c -o $PROGRAM_BASENAME
printf "\n"
printf "executing test case %s %s\n" ./$PROGRAM_BASENAME $PROGRAM_BASENAME
./$PROGRAM_BASENAME $PROGRAM_BASENAME
|
