图灵机是一种抽象的计算模型,它定义了一个在无限长的磁带上操作字符的机器。理论上,任何计算机能够完成的任务,图灵机都能模拟。在本文中,将探讨如何使用针织技术来模拟图灵机,并展示如何通过针织图案编码和解码信息。
图灵机的每个磁带单元格只能写入一次。如果需要再次写入,可以将已使用的磁带复制到新的部分。由于所有的计算都可以用二进制完成,因此可写的字符集可以限制为{0, 1},尽管更大的字符集可能有助于节省磁带。在本文中,将使用{0, 1, 2, 3}来编码所有内容,以4进制表示。
一种廉价且简单的模拟无限可写磁带的方法是使用纱线团。可以通过编织不同的针法来写入字符。如果需要覆盖一个已使用的位置,只需开始一个新的行;这就像倒带并复制图灵机的磁带一样。
本文解释了如何将任何内容编码为针法,渲染针织图,并再次解码完成的纱线磁带。使用Apache Batik SVG Toolkit来绘制图案。
可能会想要将图案输入到针织机中,将其变成一个真正的硬件图灵机。也可以手工编织它们,通过让信使戴上一顶温暖的帽子来传递秘密信息。
Java应用程序接受文本,将字符转换为4进制数字组,并将这些数字转换为一行针法:
private void encode(String clearText){
ByteBuffer bytes = Charset.forName("ISO-8859-15").encode(clearText);
StringBuilder resultBuilder = new StringBuilder(clearText.length() * 4);
// convert each character
while(bytes.hasRemaining()){
int currentValue = bytes.get();
String currentWord = Integer.toString(currentValue, 4);
// pad the number to a length of 4
while(currentWord.length() < 4){
currentWord = "0" + currentWord;
}
resultBuilder.append(currentWord);
}
ChartFrame frame = new ChartFrame();
frame.drawChart(clearText, resultBuilder.toString());
}
当手动读取一块布料时,可能会记下识别出的针法类型的数字...然后调用解码器,使用找到的针法行。它们将被解码为原始文本:
private String decode(String encodedText){
int n = 0;
StringBuilder resultBuilder = new StringBuilder(encodedText);
// translate blockwise to characters
while(n < resultBuilder.length()){
String currentWord = resultBuilder.substring(n, n+4);
int currentValue = Integer.parseInt(currentWord, 4);
String currentClearChar;
// decode or ignore
if(currentValue < 256){
ByteBuffer buffer = ByteBuffer.wrap(new byte[]{(byte)currentValue});
currentClearChar = Charset.forName("ISO-8859-15").decode(buffer).toString();
} else {
currentClearChar = "?";
}
// compress 4 digits to 1 character
resultBuilder.replace(n, n+4, currentClearChar);
n++;
}
return resultBuilder.toString();
}
对于每个数字,必须绘制相应的针法。使用了Craft Yarn Council的针织图符号,这些符号很容易用几何形状渲染。
图表由三个部分组成:列号、奇数行编码有效载荷,偶数行固定针法数量。
public void drawChart(String title, String base4Digits){
titleText = title;
// prepare SVG document
DOMImplementation impl = SVGDOMImplementation.getDOMImplementation();
String svgNS = SVGDOMImplementation.SVG_NAMESPACE_URI;
SVGDocument doc = (SVGDocument) impl.createDocument(svgNS, "svg", null);
SVGGraphics2D g = new SVGGraphics2D(doc);
g.setFont(new Font("sans serif", Font.PLAIN, 10));
// calculate chart width
countColumns = getCountCols(base4Digits);
countRows = (int)(200 / boxSize);
svgCanvas.setSize((2+countColumns)*boxSize, countRows*boxSize);
// fill background
g.setPaint(Color.darkGray);
g.fillRect(0, 0, svgCanvas.getWidth(), svgCanvas.getHeight());
// draw odd coding rows, even fixing rows
for(int y = 0; y < (countRows-2); y+=2){
// code symbols may add stiches
drawOddRow(y, base4Digits, g);
// fix excess stitches by knitting two together
drawEvenRow(y+1, base4Digits, g);
}
// draw column numbers
for(int x=0; x < countColumns; x++){
drawColNumber(x+1, countRows-1, g);
}
// prepare and show frame
titleText = titleText + " - start with " + (base4Digits.length()+2) + " stitches";
g.getRoot(doc.getDocumentElement());
svgCanvas.setSVGDocument(doc);
svgCanvas.getParent().setPreferredSize(svgCanvas.getSize());
pack();
setVisible(true);
}
绘制一行很简单:在每端放置一个针织符号,然后用符号填充空间:
private void drawOddRow(int y, String base4Digits, SVGGraphics2D g){
// label and left edge
drawRowNumber(0, y, g);
drawKnit(1, y, g);
// append one or two symbols per digit
int x = 2;
for(int n=0; n < base4Digits.length(); n++){
char currentChar = base4Digits.charAt(n);
/*
draw box
0 = knit
1 = purl
2 = yarn over, knit
3 = yarn over, purl
*/
switch(currentChar){
case '0': drawKnit(x, y, g); break;
case '1': drawPurl(x, y, g); break;
case '2': drawYarnOver(x, y, g); drawKnit(++x, y, g); break;
case '3': drawYarnOver(x, y, g); drawPurl(++x, y, g); break;
}
x++;
}
// right edge
drawKnit(x, y, g);
}
图表符号是原始形状。以下是一些示例:
private void drawBox(int col, int row, SVGGraphics2D g){
int x = col*boxSize;
int y = row*boxSize;
Rectangle2D.Double box = new Rectangle2D.Double(x, y, boxSize, boxSize);
g.fill(box);
g.setColor(Color.black);
g.draw(box);
}
private void drawColNumber(int col, int row, SVGGraphics2D g){
g.setColor(Color.black);
g.setPaint(Color.cyan);
drawBox(col, row, g);
g.drawString(String.valueOf(col), (col*boxSize)+boxPadding, (row*boxSize)+boxSize-boxPadding);
}
private void drawYarnOver(int col, int row, SVGGraphics2D g){
g.setColor(Color.black);
g.setPaint(Color.white);
int x = col*boxSize;
int y = row*boxSize;
int height = boxSize-(boxPadding*2);
Ellipse2D circle = new Ellipse2D.Double(x+boxPadding, y+boxPadding, height, height);
drawBox(col, row, g);
g.draw(circle);
}