turing-machine / index.html
raayraay's picture
Add 2 files
a87249a verified
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Turing Machine Visual Guide</title>
<script src="https://cdn.tailwindcss.com"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css">
<style>
.tape-cell {
width: 60px;
height: 60px;
border: 2px solid #94a3b8;
display: flex;
align-items: center;
justify-content: center;
position: relative;
font-size: 1.25rem;
background-color: white;
transition: all 0.3s ease;
}
.head-pointer {
position: absolute;
top: -30px;
left: 50%;
transform: translateX(-50%);
color: #3b82f6;
font-weight: bold;
font-size: 1.5rem;
}
.current-cell {
background-color: #bfdbfe;
transform: scale(1.1);
box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1);
z-index: 10;
}
.transition-table {
border-collapse: collapse;
width: 100%;
}
.transition-table th, .transition-table td {
border: 1px solid #cbd5e1;
padding: 10px;
text-align: center;
}
.transition-table th {
background-color: #f1f5f9;
font-weight: 600;
}
.state-circle {
width: 80px;
height: 80px;
border-radius: 50%;
display: flex;
align-items: center;
justify-content: center;
font-weight: bold;
font-size: 1.25rem;
position: relative;
}
.initial-state {
border: 3px solid #10b981;
}
.final-state {
border: 3px double #ef4444;
}
.regular-state {
border: 3px solid #3b82f6;
}
.state-label {
position: absolute;
top: -25px;
left: 50%;
transform: translateX(-50%);
font-size: 0.9rem;
color: #334155;
}
.state-arrow {
position: absolute;
top: 50%;
transform: translateY(-50%);
font-size: 1.5rem;
color: #64748b;
}
.highlight {
animation: highlight 1.5s ease;
}
@keyframes highlight {
0% { background-color: #fef08a; }
100% { background-color: white; }
}
.slide-in {
animation: slideIn 0.5s ease-out;
}
@keyframes slideIn {
from { transform: translateY(20px); opacity: 0; }
to { transform: translateY(0); opacity: 1; }
}
</style>
</head>
<body class="bg-slate-50 min-h-screen">
<div class="container mx-auto px-4 py-8 max-w-6xl">
<header class="mb-8 text-center">
<h1 class="text-4xl font-bold text-blue-700 mb-2">Turing Machine Visual Guide</h1>
<p class="text-lg text-slate-600">Interactive visualization of Turing Machine components and operation</p>
</header>
<div class="bg-white rounded-xl shadow-lg overflow-hidden mb-8">
<div class="p-4 bg-blue-700 text-white">
<h2 class="text-xl font-semibold">Formal Definition of a Turing Machine</h2>
</div>
<div class="p-6">
<div class="bg-blue-50 p-4 rounded-lg mb-6">
<p class="font-mono text-lg text-center font-bold">M = (Q, Σ, Γ, δ, q₀, ␣, F)</p>
</div>
<div class="grid md:grid-cols-3 gap-4 mb-6">
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-sitemap mr-2"></i> Q
</h4>
<p class="text-slate-700">Finite set of states (control unit states)</p>
<div class="mt-3 flex justify-center">
<div class="state-circle initial-state">
<span class="state-label">q₀</span>
q₀
</div>
<div class="state-arrow"></div>
<div class="state-circle regular-state">
q₁
</div>
<div class="state-arrow"></div>
<div class="state-circle final-state">
<span class="state-label">qf</span>
qf
</div>
</div>
</div>
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in" style="animation-delay: 0.1s;">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-keyboard mr-2"></i> Σ, Γ
</h4>
<p class="text-slate-700 mb-1">Σ: Input alphabet (e.g., {0, 1})</p>
<p class="text-slate-700">Γ: Tape alphabet (Σ ⊆ Γ - {␣})</p>
<div class="mt-3 flex justify-center">
<div class="flex space-x-2">
<div class="w-10 h-10 bg-slate-100 rounded-full flex items-center justify-center">0</div>
<div class="w-10 h-10 bg-slate-100 rounded-full flex items-center justify-center">1</div>
<div class="w-10 h-10 bg-slate-200 rounded-full flex items-center justify-center"></div>
<div class="w-10 h-10 bg-slate-100 rounded-full flex items-center justify-center">X</div>
<div class="w-10 h-10 bg-slate-100 rounded-full flex items-center justify-center">Y</div>
</div>
</div>
</div>
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in" style="animation-delay: 0.2s;">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-exchange-alt mr-2"></i> δ
</h4>
<p class="text-slate-700">Transition function:</p>
<p class="font-mono text-sm">Q × Γ → Q × Γ × {L, R}</p>
<div class="mt-3 bg-slate-50 p-2 rounded">
<p class="text-sm font-mono">δ(q0, 0) = (q1, 1, R)</p>
<p class="text-xs text-slate-500">If in q0 reading 0, go to q1, write 1, move right</p>
</div>
</div>
</div>
<div class="grid md:grid-cols-3 gap-4">
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in" style="animation-delay: 0.3s;">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-flag mr-2"></i> q₀
</h4>
<p class="text-slate-700">Initial state where computation begins</p>
</div>
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in" style="animation-delay: 0.4s;">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-square mr-2"></i>
</h4>
<p class="text-slate-700">Blank symbol (not in Σ, part of Γ)</p>
</div>
<div class="bg-white p-4 rounded-lg shadow border border-slate-200 slide-in" style="animation-delay: 0.5s;">
<h4 class="font-semibold text-blue-600 mb-2 flex items-center">
<i class="fas fa-check-circle mr-2"></i> F
</h4>
<p class="text-slate-700">Set of final/accepting states (F ⊆ Q)</p>
</div>
</div>
</div>
</div>
<div class="bg-white rounded-xl shadow-lg overflow-hidden mb-8">
<div class="p-4 bg-blue-700 text-white">
<h2 class="text-xl font-semibold">Turing Machine Operation</h2>
</div>
<div class="p-6">
<div class="mb-6">
<h3 class="text-lg font-semibold text-slate-800 mb-3">Tape Visualization</h3>
<div class="flex justify-center mb-4">
<div id="tape-container" class="flex items-center"></div>
</div>
<div class="text-center mb-4">
<span class="font-semibold text-blue-600">Current State:</span>
<span id="current-state" class="font-mono bg-blue-100 px-3 py-1 rounded-md ml-2">q₀</span>
</div>
<div class="text-center mb-4">
<span class="font-semibold text-slate-700">Instantaneous Description:</span>
<span id="instantaneous-desc" class="font-mono bg-slate-100 px-3 py-1 rounded-md ml-2">q₀ 0 1 0</span>
</div>
</div>
<div class="mb-6">
<h3 class="text-lg font-semibold text-slate-800 mb-3">Control Panel</h3>
<div class="flex flex-wrap justify-center gap-3 mb-4">
<button id="run-btn" class="px-4 py-2 bg-green-600 text-white rounded-md hover:bg-green-700 transition flex items-center">
<i class="fas fa-play mr-2"></i> Run
</button>
<button id="step-btn" class="px-4 py-2 bg-blue-600 text-white rounded-md hover:bg-blue-700 transition flex items-center">
<i class="fas fa-step-forward mr-2"></i> Step
</button>
<button id="reset-btn" class="px-4 py-2 bg-gray-600 text-white rounded-md hover:bg-gray-700 transition flex items-center">
<i class="fas fa-redo mr-2"></i> Reset
</button>
<button id="slow-btn" class="px-4 py-2 bg-purple-600 text-white rounded-md hover:bg-purple-700 transition flex items-center">
<i class="fas fa-tachometer-alt mr-2"></i> Slow Motion
</button>
</div>
<div class="flex flex-wrap justify-center gap-4">
<div>
<label for="input-string" class="block text-sm font-medium text-slate-700 mb-1">Input String</label>
<input type="text" id="input-string" class="px-3 py-2 border border-slate-300 rounded-md shadow-sm" value="010">
</div>
<div>
<label for="speed-slider" class="block text-sm font-medium text-slate-700 mb-1">Speed</label>
<input type="range" id="speed-slider" min="100" max="2000" value="500" class="w-32">
</div>
</div>
</div>
<div>
<h3 class="text-lg font-semibold text-slate-800 mb-3">Transition Table</h3>
<div class="overflow-x-auto">
<table class="transition-table" id="transition-table">
<thead>
<tr>
<th>Current State</th>
<th>Read Symbol</th>
<th>New State</th>
<th>Write Symbol</th>
<th>Move</th>
</tr>
</thead>
<tbody>
<!-- Will be populated by JavaScript -->
</tbody>
</table>
</div>
</div>
</div>
</div>
<div class="bg-white rounded-xl shadow-lg overflow-hidden mb-8">
<div class="p-4 bg-blue-700 text-white">
<h2 class="text-xl font-semibold">Step-by-Step Operation</h2>
</div>
<div class="p-6">
<div class="grid md:grid-cols-2 gap-6">
<div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">1</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Initialization</h4>
<p class="text-slate-700">The machine starts in state q₀ with the input string on the tape, surrounded by blanks (␣). The head is positioned at the leftmost input symbol.</p>
</div>
</div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">2</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Read Symbol</h4>
<p class="text-slate-700">The head reads the symbol at its current position. This symbol and the current state determine the next action.</p>
</div>
</div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">3</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Transition</h4>
<p class="text-slate-700">The control unit consults δ (transition function) to determine: new state, symbol to write, and head movement direction.</p>
</div>
</div>
</div>
<div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">4</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Write & Move</h4>
<p class="text-slate-700">The head writes the new symbol at its current position, then moves left (L) or right (R) one cell.</p>
</div>
</div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">5</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Repeat</h4>
<p class="text-slate-700">Steps 2-4 repeat until no transition is defined for the current state and symbol (halt).</p>
</div>
</div>
<div class="flex items-start mb-4 p-3 bg-blue-50 rounded-lg">
<div class="bg-blue-600 text-white rounded-full w-8 h-8 flex items-center justify-center mr-3 flex-shrink-0">6</div>
<div>
<h4 class="font-semibold text-blue-700 mb-1">Accept/Reject</h4>
<p class="text-slate-700">If halted in a final state (F), the input is accepted. Otherwise, it's rejected (either by halting in non-final state or infinite loop).</p>
</div>
</div>
</div>
</div>
<div class="bg-slate-50 p-4 rounded-lg border border-slate-200">
<h4 class="font-semibold text-slate-800 mb-2">Instantaneous Description Example</h4>
<p class="text-slate-700 mb-2">The configuration of a TM at any point can be represented as: <span class="font-mono">α q β</span></p>
<ul class="list-disc pl-5 text-slate-700 space-y-1">
<li><span class="font-mono">α</span>: Tape contents to the left of the head</li>
<li><span class="font-mono">q</span>: Current state</li>
<li><span class="font-mono">β</span>: Tape contents at and to the right of the head</li>
</ul>
<div class="mt-3 font-mono bg-white p-3 rounded border border-slate-200">
<p>Initial: <span class="text-blue-600">q₀</span> 0 1 0 ␣</p>
<p>After 1st transition: 1 <span class="text-blue-600">q₁</span> 1 0 ␣</p>
<p>After 2nd transition: 1 0 <span class="text-blue-600">q₁</span> 0 ␣</p>
<p>Final: 1 0 1 <span class="text-red-600">qf</span> ␣ (Accepted)</p>
</div>
</div>
</div>
</div>
<footer class="text-center text-slate-600 text-sm">
<p>Interactive Turing Machine visualization for educational purposes. Use the simulator to explore how each component works together.</p>
</footer>
</div>
<script>
// Turing Machine definition for the simulator
const exampleTM = {
name: "Simple 0/1 Flipper",
states: ['q0', 'q1', 'qf'],
inputAlphabet: ['0', '1'],
tapeAlphabet: ['0', '1', '␣'],
initialState: 'q0',
blankSymbol: '␣',
finalStates: ['qf'],
transitions: [
{currentState: 'q0', readSymbol: '0', newState: 'q1', writeSymbol: '1', move: 'R'},
{currentState: 'q0', readSymbol: '1', newState: 'q1', writeSymbol: '0', move: 'R'},
{currentState: 'q1', readSymbol: '0', newState: 'q1', writeSymbol: '1', move: 'R'},
{currentState: 'q1', readSymbol: '1', newState: 'q1', writeSymbol: '0', move: 'R'},
{currentState: 'q1', readSymbol: '␣', newState: 'qf', writeSymbol: '␣', move: 'R'}
]
};
// Simulator variables
let currentConfig = null;
let headPosition = 0;
let isRunning = false;
let stepTimeout = null;
let stepSpeed = 500;
let slowMotion = false;
let history = [];
// Initialize the simulator
function initSimulator() {
// Set up transition table
updateTransitionTable();
// Reset the machine
resetTM();
}
// Update the transition table display
function updateTransitionTable() {
const tableBody = document.getElementById('transition-table').querySelector('tbody');
tableBody.innerHTML = '';
exampleTM.transitions.forEach(transition => {
const row = document.createElement('tr');
row.innerHTML = `
<td>${transition.currentState}</td>
<td>${transition.readSymbol}</td>
<td>${transition.newState}</td>
<td>${transition.writeSymbol}</td>
<td>${transition.move}</td>
`;
tableBody.appendChild(row);
});
}
// Reset the Turing Machine
function resetTM() {
const input = document.getElementById('input-string').value;
// Initialize tape with input surrounded by blanks
currentConfig = {
tape: ['␣', ...input.split(''), '␣'],
state: exampleTM.initialState,
head: 1 // Start at first input symbol
};
headPosition = 1;
history = [];
updateHistory();
// Update display
updateTapeDisplay();
document.getElementById('current-state').textContent = currentConfig.state;
document.getElementById('current-state').className = 'font-mono bg-blue-100 px-3 py-1 rounded-md ml-2';
// Clear any running execution
if (stepTimeout) {
clearTimeout(stepTimeout);
stepTimeout = null;
}
isRunning = false;
}
// Update the tape display
function updateTapeDisplay() {
const tapeContainer = document.getElementById('tape-container');
tapeContainer.innerHTML = '';
// Show cells around the head position (5 to left, 5 to right)
const start = Math.max(0, headPosition - 5);
const end = Math.min(currentConfig.tape.length, headPosition + 6);
for (let i = start; i < end; i++) {
const cell = document.createElement('div');
cell.className = 'tape-cell';
if (i === headPosition) cell.classList.add('current-cell');
// Highlight recently changed cells
if (history.some(step => step.position === i && step.step === history.length)) {
cell.classList.add('highlight');
}
const symbol = currentConfig.tape[i];
cell.textContent = symbol;
if (i === headPosition) {
const pointer = document.createElement('div');
pointer.className = 'head-pointer';
pointer.innerHTML = '<i class="fas fa-chevron-down"></i>';
cell.appendChild(pointer);
}
tapeContainer.appendChild(cell);
}
// Update instantaneous description
updateInstantaneousDesc();
}
// Update the instantaneous description
function updateInstantaneousDesc() {
let leftPart = currentConfig.tape.slice(0, headPosition).join(' ');
let rightPart = currentConfig.tape.slice(headPosition).join(' ');
let desc = `${leftPart} <span class="text-blue-600">${currentConfig.state}</span> ${rightPart}`;
document.getElementById('instantaneous-desc').innerHTML = desc;
}
// Update history of tape changes
function updateHistory() {
// Record current tape state and head position
history.push({
step: history.length + 1,
state: currentConfig.state,
tape: [...currentConfig.tape],
position: headPosition
});
}
// Execute one step of the Turing Machine
function stepTM() {
const currentSymbol = currentConfig.tape[headPosition];
// Find matching transition
const transition = exampleTM.transitions.find(t =>
t.currentState === currentConfig.state && t.readSymbol === currentSymbol
);
if (!transition) {
// No transition found - halt
isRunning = false;
// Check if we're in a final state
if (exampleTM.finalStates.includes(currentConfig.state)) {
document.getElementById('current-state').className = 'font-mono bg-green-100 px-3 py-1 rounded-md ml-2';
showAlert('Accepted! The machine halted in a final state.', 'green');
} else {
document.getElementById('current-state').className = 'font-mono bg-red-100 px-3 py-1 rounded-md ml-2';
showAlert('Rejected! The machine halted in a non-final state.', 'red');
}
return;
}
// Record previous state for animation
const prevState = currentConfig.state;
const prevSymbol = currentConfig.tape[headPosition];
const prevPos = headPosition;
// Apply the transition
currentConfig.tape[headPosition] = transition.writeSymbol;
currentConfig.state = transition.newState;
// Move the head
if (transition.move === 'L') {
headPosition--;
if (headPosition < 0) {
// Extend tape to the left
currentConfig.tape.unshift(exampleTM.blankSymbol);
headPosition = 0;
}
} else if (transition.move === 'R') {
headPosition++;
if (headPosition >= currentConfig.tape.length) {
// Extend tape to the right
currentConfig.tape.push(exampleTM.blankSymbol);
}
}
// Record this step in history
updateHistory();
// Update display
updateTapeDisplay();
document.getElementById('current-state').textContent = currentConfig.state;
// Highlight the transition in the table
highlightTransition(transition);
// Check if we're in a final state
if (exampleTM.finalStates.includes(currentConfig.state)) {
isRunning = false;
document.getElementById('current-state').className = 'font-mono bg-green-100 px-3 py-1 rounded-md ml-2';
showAlert('Accepted! The machine halted in a final state.', 'green');
return;
}
// Continue if running
if (isRunning) {
if (slowMotion) {
// In slow motion mode, pause between steps
stepTimeout = setTimeout(stepTM, stepSpeed);
} else {
// Otherwise proceed immediately to next step
stepTM();
}
}
}
// Highlight the current transition in the table
function highlightTransition(transition) {
const tableRows = document.querySelectorAll('#transition-table tbody tr');
// Remove any existing highlights
tableRows.forEach(row => {
row.classList.remove('bg-yellow-100');
});
// Find and highlight the matching transition
for (let i = 0; i < tableRows.length; i++) {
const cells = tableRows[i].querySelectorAll('td');
if (cells[0].textContent === transition.currentState &&
cells[1].textContent === transition.readSymbol) {
tableRows[i].classList.add('bg-yellow-100');
break;
}
}
}
// Show an alert message
function showAlert(message, color) {
const alertDiv = document.createElement('div');
alertDiv.className = `fixed bottom-4 right-4 px-4 py-2 rounded-md shadow-lg text-white bg-${color}-600`;
alertDiv.textContent = message;
document.body.appendChild(alertDiv);
setTimeout(() => {
alertDiv.remove();
}, 3000);
}
// Run the Turing Machine continuously
function runTM() {
if (!isRunning) {
isRunning = true;
slowMotion = false;
stepTM();
}
}
// Run in slow motion
function runSlowMotion() {
if (!isRunning) {
isRunning = true;
slowMotion = true;
stepTM();
}
}
// Event listeners
document.getElementById('run-btn').addEventListener('click', runTM);
document.getElementById('step-btn').addEventListener('click', () => {
if (!isRunning) stepTM();
});
document.getElementById('reset-btn').addEventListener('click', resetTM);
document.getElementById('slow-btn').addEventListener('click', runSlowMotion);
document.getElementById('input-string').addEventListener('change', resetTM);
document.getElementById('speed-slider').addEventListener('input', function() {
stepSpeed = 2100 - this.value; // Invert so right is faster
});
// Initialize the simulator
initSimulator();
</script>
<p style="border-radius: 8px; text-align: center; font-size: 12px; color: #fff; margin-top: 16px;position: fixed; left: 8px; bottom: 8px; z-index: 10; background: rgba(0, 0, 0, 0.8); padding: 4px 8px;">Made with <img src="https://enzostvs-deepsite.hf.space/logo.svg" alt="DeepSite Logo" style="width: 16px; height: 16px; vertical-align: middle;display:inline-block;margin-right:3px;filter:brightness(0) invert(1);"><a href="https://enzostvs-deepsite.hf.space" style="color: #fff;text-decoration: underline;" target="_blank" >DeepSite</a> - 🧬 <a href="https://enzostvs-deepsite.hf.space?remix=raayraay/turing-machine" style="color: #fff;text-decoration: underline;" target="_blank" >Remix</a></p></body>
</html>