forked from aepsilon/turing-machine-viz
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
801 lines (776 loc) · 36.5 KB
/
index.html
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Visualize and simulate Turing machines as animated state diagrams.
Create and share your own machines using a simple format. Examples and exercises are included.">
<meta name="keywords" content="Turing machine, finite automata, simulator, visualization, state diagram">
<meta name="robots" content="NOODP">
<title>Turing machine visualization</title>
<!-- Bootstrap -->
<link href="https://maxcdn.bootstrapcdn.com/bootswatch/3.3.6/lumen/bootstrap.min.css" rel="stylesheet"
integrity="sha384-mvYjhBJXQ9VlNETV/xXShy849GsBHnKzVVudnMOcWUVM/6Nd2ksj8VNng5f8ylyX" crossorigin="anonymous">
<link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet"
integrity="sha384-T8Gy5hrqNKT+hzMclPo118YTQO6cYprQmhrYwIiQ/3axmI1hQomh7Ud2hPOy8SP1" crossorigin="anonymous">
<!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn"t work if you view the page via file:// -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.2/html5shiv.js"></script>
<script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->
<!-- Libraries -->
<script src="https://cdn.jsdelivr.net/d3js/3.5.17/d3.min.js"
integrity="sha256-uB5nPcWK8vr5e83snqtMUYJ2n/5TZ3PV9CCRk1pzob4=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/ace/1.2.3/noconflict/ace.js"
integrity="sha256-Iww1CLn76ly5OU/TUHhiQF9qYy+BpQpg8hI8sIhi32I=" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/js-yaml/3.6.0/js-yaml.min.js"
integrity="sha256-cClLF3hmu8Q/atb1MfoMUg+4h2MTXFMl5+UuvXBWE8g=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/lodash/4.10.0/lodash.min.js"
integrity="sha256-WplZqoBFo5rcW50YJBm/A1DRy7NnlMHTVDZBan+g2ZU=" crossorigin="anonymous"></script>
<script> var lodash = _; </script>
<script src="https://cdn.jsdelivr.net/lodash/4.10.0/lodash.fp.min.js"
integrity="sha256-21hyGphPmEWw6dEv1N50zj2CGTCph/CZOkIQHqGoTfs=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/bluebird/3.4.1/bluebird.min.js"
integrity="sha256-RerJKWlCVH4Or054aLxHuQ4EXbfVwjyYeT99oVAW1pg=" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/clipboard.js/1.5.12/clipboard.min.js"
integrity="sha256-YPxFEfHAzLj9n2T+2UXAKGNCRUINk0BexppujiVhRH0=" crossorigin="anonymous"></script>
<!-- jQuery (necessary for Bootstrap plugins) -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.3/jquery.min.js"
integrity="sha384-6ePHh72Rl3hKio4HiJ841psfsRJveeS+aLoaEf3BWfS+gTF0XdAqku2ka8VddikM" crossorigin="anonymous"></script>
<!-- Bootstrap: all compiled plugins -->
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"
integrity="sha384-0mSbJDEHialfmuBBQP6A4Qrprq5OVfW37PRR3j5ELqxss1yVqOtnepnHVP9aJ7xS" crossorigin="anonymous"></script>
<!-- CSS -->
<link href="build/state-diagram/StateViz.css" rel="stylesheet">
<link href="build/tape/tape.css" rel="stylesheet">
<style>
body {
font-variant-ligatures: contextual;
}
nav .navbar-right {
margin-right: 0; /* override negative margin */
}
.navbar-brand {
font-variant: small-caps;
letter-spacing: .03em; /* for caps */
font-family: 'Avenir Next', 'Avenir', 'Lucida Grande',
'Source Sans Pro', 'Helvetica Neue', Helvetica, Arial, sans-serif;
}
.kern { letter-spacing: -.1em; font-kerning: none; /* kern manually */ }
.navbar-brand .kern-Ma { letter-spacing: 0em }
.navbar-brand .kern-Vi { letter-spacing: -.02em }
pre {
background-color: hsl(0, 0%, 98%);
}
.editor-shortcuts td:first-child {
text-align: right;
}
kbd { /* Adjusted StackOverflow's old <kbd> style https://meta.superuser.com/questions/4788 */
background-color: #f7f7f7;
border: 1px solid #ccc;
border-radius: 3px;
box-shadow: 0 1px 0 rgba(0,0,0,0.2), 0 0 0 2px #fff inset;
color: #333;
display: inline-block;
font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 85%;
line-height: 1.4;
margin: 0 .1em;
padding: .1em .6em;
text-shadow: 0 1px 0 #fff;
}
@media (min-width: 992px) { /* when diagram and editor are side by side */
/* Visually center diagram horiz. (match left and right negative space) */
#diagram-column { padding-right: 0; }
}
/* Editor */
#editor-wrapper {
position: relative;
width: 100%;
max-width: 85ch;
margin: auto;
}
button.tm-editor-revert {
position: absolute;
right: 0;
}
.tm-editor.ace_editor {
border: 1px solid #DDD;
/*border: 1px solid #ccc;*/
border-radius: 4px;
margin-top: 1em;
font-family: 'Source Code Pro', 'source-code-pro', 'Monaco', 'Menlo', 'Ubuntu Mono', 'Consolas', monospace;
text-align: left;
}
/* Print styles */
@media print {
button.btn, hr { display: none }
#tutorial { page-break-before: always }
}
/* "Save" button */
.btn-wide-save {
padding-left: 1.5em;
padding-right:1.5em;
}
/* Checkbox table */
.checkbox-table tr > :first-child {
text-align: right
}
.checkbox-table tr > :last-child {
text-align: right;
}
.checkbox-table tbody tr, input[type="checkbox"] {
cursor: pointer;
}
/* Disclosure triangle */
a.disclosure-triangle {
cursor: pointer;
text-decoration: none;
}
a.disclosure-triangle:before {
content: '▸';
transform: rotate(90deg);
transform-origin: center;
transition: transform 0.1s linear;
display: inline-block;
font-size: larger;
margin-right: 0.2em;
}
a.disclosure-triangle.collapsed:before {
transform: none;
}
a.disclosure-triangle + div.collapse > .panel:first-child,
a.disclosure-triangle + div.collapsing > .panel:first-child {
margin-top: 1em;
}
/* Page footer */
.octicon.octicon-mark-github {
fill: currentColor;
overflow: visible;
}
.page-footer {
margin: 2em 0 0 0;
padding: 1.1em;
border-top: 1px solid #ddd;
background: hsl(0, 0%, 96%);
text-align: center;
line-height: 0; /* to center logo vertically */
}
.page-footer .octicon {
color: hsl(0, 0%, 35%);
}
.page-footer a .octicon:hover {
color: hsl(0, 0%, 0%);
}
/* Fix overflow inside modal caused by td pre */
.modal-dialog td pre {
white-space: pre-wrap;
font-size: smaller;
}
/* Fix some cases of extra margins in bootstrap */
.modal-body .panel:last-child,
.panel-body > *:last-child {
margin-bottom: 0;
}
/* Feature detection */
.download-attr .download-fallback { display: none }
.no-copycommand [data-clipboard-target] { display: none }
.icon-help-block > * { display: table-cell }
.icon-help-block > .glyphicon:first-child { padding-right: 0.5em }
</style>
<!-- Analytics -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-81335742-1', 'auto');
ga('send', 'pageview');
</script>
</head>
<body>
<nav class="navbar navbar-default">
<div class="container-fluid">
<div class="navbar-header">
<span class="navbar-brand">
<span class="kern">T</span>uring <span class="kern-Ma">M</span>achine <span class="kern-Vi">V</span>isualization
</span>
</div>
<div class="navbar-form navbar-left">
<!-- Document Menu -->
<select id="tm-doc-menu" class="form-control"></select>
<!-- Edit Menu -->
<div class="btn-group">
<button type="button" class="btn btn-default btn-sm dropdown-toggle"
data-toggle="dropdown" aria-haspopup="true" aria-expanded="false" >
Edit <span class="caret"></span>
</button>
<ul class="dropdown-menu">
<li><a href="#" id="tm-doc-action-duplicate">Duplicate document…</a></li>
<li><a href="#" id="tm-doc-action-newblank">New blank document…</a></li>
<li role="separator" class="divider"></li>
<!-- "Rename" saves when closed, so don't allow closing with Esc -->
<li><a href="#" data-toggle="modal" data-keyboard="false"
data-target="#renameDialog">Rename…</a></li>
<li role="separator" class="divider"></li>
<li><a href="#" data-toggle="modal" data-target="#deleteDialog">Delete…</a></li>
</ul>
</div>
</div>
<!-- Import and "Share" Menu -->
<div class="navbar-right">
<button type="button" class="btn btn-default navbar-btn tm-needsready" aria-label="Import" disabled
data-toggle="modal" data-target="#importPanel"
data-has-tooltip data-placement="bottom" data-trigger="hover" title="Import">
<span class="glyphicon glyphicon-folder-open" aria-hidden="true"></span>
</button>
<button type="button" class="btn btn-default navbar-btn tm-needsready" aria-label="Share" disabled
data-toggle="modal" data-target="#exportPanel" data-keyboard="false"
data-has-tooltip data-placement="bottom" data-trigger="hover" title="Share">
<span class="glyphicon glyphicon-share" aria-hidden="true"></span>
</button>
</div>
</div>
</nav>
<!-- ** Modal dialogs ** -->
<!-- Dialog for Rename -->
<div id="renameDialog" class="modal" tabindex="-1" role="dialog" aria-labelledby="renameDialogHeader">
<div class="modal-dialog modal-sm" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="renameDialogHeader">Document Name</h4>
</div>
<div class="modal-body">
<form id="renameDialogForm">
<label class="sr-only" for="renameDialogInput">Document Name</label>
<input type="text" class="form-control" id="renameDialogInput" placeholder="document name">
</form>
</div>
</div>
</div>
</div>
<!-- Dialog for Delete -->
<div id="deleteDialog" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="deleteDialogHeader">
<div class="modal-dialog modal-sm" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="deleteDialogHeader">Delete this document?</h4>
</div>
<div class="modal-body">
This will erase the document and remove it from the menu.
You can’t undo this action.
</div>
<div class="modal-footer">
<button id="tm-doc-action-delete" type="button"
class="btn btn-danger pull-left" data-dismiss="modal">Delete</button>
<button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
</div>
</div>
</div>
</div>
<!-- Dialog for Resetting an Example -->
<div id="resetExampleDialog" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="resetExampleDialogHeader">
<div class="modal-dialog" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="resetExampleDialogHeader">Save a copy of your changes?</h4>
</div>
<div class="modal-body">
<p>Resetting this example will erase any changes made to it.</p>
You have the option to save your changes as a new document, or simply discard them.
You can’t undo this action.
</div>
<div class="modal-footer">
<button id="tm-doc-action-resetdiscard" type="button"
class="btn btn-danger pull-left" data-dismiss="modal">Discard</button>
<button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
<button id="tm-doc-action-resetsave" type="button"
class="btn btn-primary btn-wide-save" data-dismiss="modal">Save</button>
</div>
</div>
</div>
</div>
<!-- Dialog for Import button -->
<div id="importPanel" class="modal fade" tabindex="-1" role="dialog"
aria-labelledby="importPanelHeader">
<div class="modal-dialog" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="importPanelHeader">Import</h4>
</div>
<div class="modal-body">
<div class="panel panel-default">
<div class="panel-heading">
<h5 class="panel-title">From GitHub gist</h5>
</div>
<div class="panel-body">
<form id="gistIDForm" class="form-inline">
<div class="input-group">
<span class="input-group-addon">https://gist.github.com/</span>
<input type="text" size="36" class="form-control"
placeholder="gist ID" spellcheck="false"
pattern="[\da-fA-F]+" title="Hex digits (0–9, a–f)">
</div>
<button type="submit" class="btn btn-default">Import</button>
</form>
<span class="help-block">
If the gist contains multiple documents, you’ll be able to choose which ones to import.
</span>
</div>
</div>
<div id="importFilesPanel" class="panel panel-default">
<div class="panel-heading">
<h5 class="panel-title">From files</h5>
</div>
<div class="panel-body">
<div class="form-group">
<p>Choose one or more files to import</p>
<div class="input-group">
<input type="file" name="files" multiple class="form-control">
<span class="input-group-btn">
<button id="importFilesButton"
type="button" class="btn btn-default">Import</button>
</span>
</div>
</div>
<div class="form-group">
<p>…or paste a document’s contents below.</p>
<textarea class="form-control" rows="8" cols="40"></textarea>
</div>
<div class="text-center">
<button id="importContentsButton"
type="button" class="btn btn-default">Import</button>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Dialog for Sharing/Export -->
<div id="exportPanel" class="modal fade" tabindex="-1" role="dialog" aria-labelledby="exportPanelHeader">
<div class="modal-dialog" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="exportPanelHeader">Share & Export</h4>
</div>
<div class="modal-body">
<div class="panel panel-default">
<div class="panel-heading">
<h5 class="panel-title">Share link</h5>
</div>
<div class="panel-body">
<div class="form-group">
<div id="shareGistContainer">
</div>
<p>
You can link to any GitHub gist by its ID:
</p>
<div class="well well-sm">
<samp>turingmachine.io/?import-gist=<var>ID</var></samp>
</div>
<p>
When using your own gists, you gain the ability to update and delete the contents,
and to share multiple documents at once.
</p>
<a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#customGistInstructions">
How to make your own gist
</a>
<div id="customGistInstructions" class="collapse">
<ol>
<li>Open the <a href="https://gist.github.com" target="_blank">new gist page.</a>
Sign into GitHub if you’d like to be able to edit or delete the contents in the future.
</li>
<li>Download the document (below), then drag & drop it onto the new gist page. <br>
Alternatively, copy & paste the contents, and name the file to end with <code>.yaml</code>
</li>
<li>Create the gist. The gist ID will be at the end of the URL.</li>
</ol>
</div>
</div>
</div>
</div>
<div class="panel panel-default">
<div class="panel-heading">
<h5 class="panel-title">Download</h5>
</div>
<div class="panel-body">
<div class="form-group">
<p>Download the current document to get a backup copy
to share and import on other browsers and devices.</p>
<div id="exportDownloadContainer">
</div>
<div class="download-fallback">
<a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#downloadAttrInfo">
Why the extra steps?
</a>
<div id="downloadAttrInfo" class="help-block collapse icon-help-block">
<span class="glyphicon glyphicon-info-sign" aria-hidden="true"></span>
<p>Your browser
<a href="http://caniuse.com/#feat=download" target="_blank">doesn’t support</a>
an HTML5 <a href="https://developer.mozilla.org/en-US/docs/Web/HTML/Element/a#attr-download" target="_blank">feature</a>
to mark links as downloadable.
Without sending your data to a server—just to have it
<a href="https://en.wikipedia.org/wiki/MIME#Content-Disposition" target="_blank">marked</a>
and sent back again—the simplest alternative is to save the file manually.
</p>
</div>
</div>
</div>
<div class="form-group">
<p>The contents of the download are below.</p>
<button id="copyContentsButton" type="button" class="btn btn-default" data-clipboard-target="#exportTextarea">
Copy to clipboard
</button>
</div>
<textarea id="exportTextarea"
class="form-control" rows="8" cols="40" readonly></textarea>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Main Content -->
<div class="container-fluid">
<div class="row">
<div id="diagram-column" class="col-md-7 form-group text-center">
<!-- Diagram -->
<div id="machine-container" class="form-group">
<!-- Noscript notice -->
<noscript>
<div class="panel panel-default">
<div class="panel-heading">
<h3 class="panel-title">Tip: Enable JavaScript</h3>
</div>
<div class="panel-body">
<p>The visualization couldn’t load because JavaScript is disabled.</p>
</div>
</div>
</noscript>
</div>
<!-- Simulator controls -->
<div id="controls-container" class="row text-center">
<div class="col-xs-1">
<button type="button" class="btn btn-warning btn-xs text-center tm-btn-diagram tm-reset">
<span class="glyphicon glyphicon-fast-backward" aria-hidden="true"></span><br>
Reset
</button>
</div>
<div class="col-xs-2 col-xs-offset-4 text-center">
<button type="button" class="btn btn-primary text-center tm-btn-diagram tm-step">
<span class="glyphicon glyphicon-step-forward" aria-hidden="true"></span><br>
Step
</button>
</div>
<div class="col-xs-1">
<button type="button" class="btn btn-default text-center tm-btn-diagram tm-run">
<span class="glyphicon glyphicon-play" aria-hidden="true"></span><br>
Run
</button>
</div>
</div>
</div>
<!-- Code Editor -->
<div class="col-md-5 form-group text-center">
<div id="editor-wrapper">
<div id="editor-alerts-container"></div>
<button type="button" class="btn btn-primary tm-editor-load">
Load machine
</button>
<button type="button" class="btn btn-default tm-editor-revert">
Revert to diagram
</button>
<div id="editor-container" class="tm-editor"></div>
</div>
</div>
</div>
<script>
$(function () {
$('[data-has-tooltip]').tooltip()
});
// Polyfill for IE
if (!('remove' in Element.prototype)) {
Element.prototype.remove = function () { if (this.parentNode) { this.parentNode.removeChild(this); } };
}
</script>
<!-- Entry point -->
<script src="build/TMViz.bundle.js" charset="utf-8"></script>
<script src="build/main.bundle.js" charset="utf-8"></script>
<hr>
<!-- Tutorial -->
<div id="tutorial" class="row">
<section class="col-md-4 col-sm-6">
<h3>Try it out</h3>
<p>
<strong>Run</strong> the machine to see it in action.
At any time, you can <strong>step</strong> or <strong>pause</strong> to get a closer look,
or <strong>reset</strong> to start over.
</p>
<p>There are over a dozen different example machines to explore.</p>
<p>
Most of the examples take input. Experiment with different inputs to see what happens!
Edit the code and click <em>Load machine</em> to sync your changes.
</p>
<section>
<h4>What’s going on?</h4>
<p>The colored circles are <em>states</em>. The squares underneath are <em>tape cells</em>.</p>
<p>The current state and tape cell are highlighted.</p>
<p>At each step, a Turing machine reads its current state and tape symbol,
and looks them up in its <em>transition table</em> for an instruction.
Each <em>instruction</em> does 3 things:</p>
<ol>
<li><strong>write</strong> a symbol to the current tape cell</li>
<li><strong>move</strong> to the left or right by one cell</li>
<li><strong>set</strong> the new state</li>
</ol>
<p>That’s it!</p>
<p>This repeats step after step, until the machine reaches a combination of state and symbol
that don’t have an instruction defined. At that point it <em>halts</em>.
</p>
</section>
<section>
<h4><a href="#tm-details" class="disclosure-triangle collapsed" role="button" data-toggle="collapse">
In more detail
</a></h4>
<div id="tm-details" class="panel-group collapse" role="tablist" aria-multiselectable="true">
<div class="panel panel-default">
<div id="headingBasics" class="panel-heading" role="tab">
<h4 class="panel-title">
<a role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-basics" aria-controls="details-basics" aria-expanded="true">
Basics
</a>
</h4>
</div>
<div id="details-basics" aria-labelledby="headingBasics" class="panel-collapse collapse in" role="tabpanel">
<div class="panel-body">
<p>A <dfn>Turing machine</dfn> is an abstract device to model computation as rote symbol manipulation.</p>
<p>Each machine has a finite number of states, and a finite number of possible symbols.
These are fixed before the machine starts, and do not change as the machine runs.</p>
<p>There are an <em>infinite</em> number of tape cells, however, extending endlessly to the left and right.
Each tape cell bears a symbol. Any cell not part of the input or not yet written to bears the blank symbol by default.
Notice that at any step, only finitely many cells bear a non-blank symbol.</p>
<p>(As a mathematical model, a Turing machine has infinite memory (an infinite tape) so as to not artificially restrict its power.
In practice, many machines of interest take finite memory, and can be fully simulated for manageable input sizes.
Even machines that use infinite memory—and hence never halt—use at most one new tape cell per step, and so can be simulated to an extent.)</p>
</div>
</div>
</div>
<div class="panel panel-default">
<div id="headingFormalDefn" class="panel-heading" role="tab">
<h4 class="panel-title">
<a class="collapsed" role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-formal-defn" aria-controls="details-formal-defn" aria-expanded="false">
Formal definition
</a>
</h4>
</div>
<div id="details-formal-defn" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingFormalDefn">
<div class="panel-body">
<p>The formal definition of a Turing machine has slight variations but essentially is a tuple (ordered list) comprising</p>
<ul>
<li>states Q</li>
<li>start state q₀ ∈ Q</li>
<li>input alphabet Σ</li>
<li>tape alphabet Γ, where Σ ⊆ Γ</li>
<li>blank symbol b ∈ Γ</li>
<li>transition function δ that has the type Q × Γ → Γ × {L, R} × Q</li>
</ul>
<p>where Q, Σ, and Γ are finite nonempty sets.
Some definitions also require that the blank symbol not be part of the input (b ∉ Σ).</p>
<p>As an example, a formal description for the “binary increment” machine is as follows:</p>
<p>
Q = { right, carry, done }
<br>q₀ = right
<br>Σ = { 1, 0 }
<br>Γ = { 1, 0, ' ' }
<br>b = ' '
</p>
<p>
δ(right, 1) = (1, R, right)
<br>δ(right, 0) = (0, R, right)
<br>δ(right, ' ') = (' ', L, carry)
<br>δ(carry, 1) = (0, L, carry)
<br>δ(carry, 0) = (1, L, done)
<br>δ(carry, ' ') = (1, L, done)
</p>
<p>Note that for simplicity, the simulator limits each symbol to one character.
Furthermore, input is not checked for conformance with an input alphabet, in exchange for not having to define input and tape alphabets.</p>
<p>(The behavior of a Turing machine can also be described in mathematical terms if desired.
Without going into too much detail, this involves defining how a <em>configuration</em>
of a machine—its state, tape contents, and tape head position (current cell)—leads to the next configuration, based on the transition function.
To start with, the tape’s contents may be defined as a function from integers to symbols,
with the head position as an integer, and each move {L, R} adding -1 or +1 respectively to the head position.)</p>
</div>
</div>
</div>
<div class="panel panel-default">
<div id="headingVariations" class="panel-heading" role="tab">
<h4 class="panel-title">
<a class="collapsed" role="button" data-toggle="collapse" data-parent="#tm-details" href="#details-variations" aria-controls="details-variations" aria-expanded="false">
Variations
</a>
</h4>
</div>
<div id="details-variations" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingVariations">
<div class="panel-body">
<p>Some aspects of the definition vary from author to author, but the differences come down to preference and do not affect computational power.
That is, machines on one model can be simulated or converted to run on another model.</p>
<p>Some of the variations you may come across:</p>
<ol>
<li>The tape only extends infinitely to the right. The left end is where the tape head (current cell) begins.
Moving left at the left end keeps the tape head on the same cell.</li>
<li>In addition to “move left” (L) or “move right” (R), a tape head movement can be “no move” (N).</li>
<li>Instead of moving the tape head, a movement shifts the tape itself, so that the directions of L & R are swapped.
(Shifting the tape left is the same as moving the head right.)</li>
<li>The machine can only halt in one of two states: a state designated the <em>accept</em> state, or another state designated the <em>reject</em> state.
These states have no exiting transitions. All the other states must have transitions defined for every symbol.</li>
</ol>
<p>The simulator was designed with these and other considerations in mind.</p>
<ol>
<li>Limiting the tape was inconvenient, often requiring marking the left end with a symbol, and writing numbers in reverse.
On the other hand, machines created for a right-infinite tape can run on a doubly-infinite tape with little to no modification.</li>
<li>Compared to L and R, “no move” (N) seems to be seldom used. For now it has been omitted for conceptual simplicity.</li>
<li>It's more intuitive to set the current cell directly by moving the tape head. Turing also follows this convention.
(The visualization however stays centered on the head to avoid issues of the head moving out of view.)</li>
<li>The accept/reject convention still works; it's just not required.
In fact the simulator supports a convenient shorthand, demonstrated in some of the examples:
omit the reject state and all transitions to it, and treat halting on a non-accept state as an implicit rejecting transition.
This reduces tedious boilerplate code and makes for a cleaner diagram.</li>
</ol>
</div>
</div>
</div>
</div>
</section>
<p>
For a very readable introduction to Turing machines, including their significance and interesting implications,
see the excellent <a href="http://plato.stanford.edu/entries/turing-machine" target="_blank">entry in the Stanford Encyclopedia of Philosophy</a>.
</p>
</section>
<section class="col-md-4 col-sm-6">
<h3>Make your own</h3>
<p>Make spinoffs from the examples or your own creations by using
<i>Edit</i> > <i>Duplicate document</i>.
You can also start from scratch with a new blank document.</p>
<p>All it takes to describe a Turing machine is a start state, blank symbol, and transition table.</p>
<h4>Example</h4>
<pre>
# Adds 1 to a binary number.
input: '1011'
blank: ' '
start state: right
table:
# scan to the rightmost digit
right:
1: R
0: R
' ': {L: carry}
# then carry the 1
carry:
1: {write: 0, L}
0: {write: 1, L: done}
' ': {write: 1, L: done}
done:
</pre>
<p>
Here the states are <code>right</code>, <code>carry</code>, and <code>done</code>.<br>
The symbols are '<code>1</code>', '<code>0</code>', and '<code> </code>'.
</p>
<p>
We designate one state the <i>start state</i>,
and one symbol the <i>blank</i> symbol (found on unmarked tape cells).
</p>
<p>
A state and a symbol together map to an instruction.
In the <code>carry</code> state, for instance, the symbol <code>1</code> maps to the instruction <code>{write: 0, L}</code>.
When no instruction is defined, as in the <code>done</code> state, the machine halts.
</p>
<h4>Instruction format</h4>
The general form of an instruction has three parts:
<pre>{write: <var>symbol</var>, <var>move</var>: <var>state</var>}</pre>
<ul>
<li><code>{write: 1, L: done}</code> writes the symbol <code>1</code>,
moves the tape head left (<code>L</code>), and goes to the <code>done</code> state.
</li>
</ul>
<p>For brevity, you can omit the symbol and state if they stay the same.</p>
<ul>
<li><code>{L: carry}</code> writes the same symbol that was read,
moves the tape head left, and goes to the <code>carry</code> state.</li>
<li><code>R</code> (shorthand for {R}) simply moves the tape head right.
It writes back the same symbol and stays in the same state.</li>
</ul>
</section>
<div class="col-md-4 col-sm-12">
<h3>Tips</h3>
<div class="row">
<div class="col-sm-6 col-md-12">
<h4>Editor keyboard shortcuts</h4>
<table id="kbdShortcutTable" class="editor-shortcuts table">
</table>
<noscript>
<p>The code editor and keyboard shortcuts require that JavaScript be enabled.</p>
</noscript>
<p>More keyboard shortcuts are available on the <a href="https://github.com/ajaxorg/ace/wiki/Default-Keyboard-Shortcuts" target="_blank">full list</a>.</p>
</div>
<div class="col-sm-6 col-md-12">
<h4>Misc. tips</h4>
<ul id="misc-tips-list">
<li>Drag or click a state node to fix it in place; double-click to release it.</li>
<li>Don’t hesitate to duplicate.
Use <i>Edit</i> > <i>Duplicate document</i> to create a snapshot of your current document whenever you’re about to make a larger edit.</li>
<li>Changes are autosaved to your browser’s local storage.
They will stay there between sessions, but be careful when clearing browser data. You can create backups by downloading your documents.</li>
<li>Incognito / Private Browsing mode uses a separate temporary storage. This is useful for importing or editing documents that you want to try but don’t want to keep.</li>
</ul>
<a class="disclosure-triangle collapsed" role="button" data-toggle="collapse" href="#aboutSyntax">
More about the syntax
</a>
<div id="aboutSyntax" class="collapse">
<p>The code is written in <a href="https://en.wikipedia.org/wiki/YAML" target="_blank"><abbr>YAML</abbr></a> 1.2, a general-purpose data format.</p>
<p>
If you’re familiar with JSON, YAML is similar, but designed to be more readable.
Mappings can use indent instead of brackets <code>{}</code>, and strings can often be included directly without quotes.
</p>
<p>
Some strings need to be quoted: for example, those that start/end with a space, or include certain characters that have special meaning in YAML.
If a string is causing problems, try putting quotes around it.
</p>
</div>
</div>
</div>
</div>
</div>
</div>
<footer class="page-footer">
<a href="https://github.com/aepsilon/turing-machine-viz" target="_blank" title="View on GitHub">
<svg class="octicon octicon-mark-github" height="24" width="24" viewBox="0 0 16 16" version="1.1" aria-hidden="true">
<path d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59 0.4 0.07 0.55-0.17 0.55-0.38 0-0.19-0.01-0.82-0.01-1.49-2.01 0.37-2.53-0.49-2.69-0.94-0.09-0.23-0.48-0.94-0.82-1.13-0.28-0.15-0.68-0.52-0.01-0.53 0.63-0.01 1.08 0.58 1.23 0.82 0.72 1.21 1.87 0.87 2.33 0.66 0.07-0.52 0.28-0.87 0.51-1.07-1.78-0.2-3.64-0.89-3.64-3.95 0-0.87 0.31-1.59 0.82-2.15-0.08-0.2-0.36-1.02 0.08-2.12 0 0 0.67-0.21 2.2 0.82 0.64-0.18 1.32-0.27 2-0.27 0.68 0 1.36 0.09 2 0.27 1.53-1.04 2.2-0.82 2.2-0.82 0.44 1.1 0.16 1.92 0.08 2.12 0.51 0.56 0.82 1.27 0.82 2.15 0 3.07-1.87 3.75-3.65 3.95 0.29 0.25 0.54 0.73 0.54 1.48 0 1.07-0.01 1.93-0.01 2.2 0 0.21 0.15 0.46 0.55 0.38C13.71 14.53 16 11.53 16 8 16 3.58 12.42 0 8 0z" />
</svg>
</a>
</footer>
<!-- Dialog for Import -->
<div id="importDialog" class="modal fade" tabindex="-1" role="dialog"
aria-labelledby="importDialogHeader">
<div class="modal-dialog" role="document">
<div class="modal-content">
<div class="modal-header">
<button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
<h4 class="modal-title" id="importDialogHeader">Import</h4>
</div>
<div class="modal-body">
</div>
<div class="modal-footer">
</div>
</div>
</div>
</div>
</body>
</html>