Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

Turing Machine


  • Please log in to reply
13 replies to this topic
Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Implementation of the smallest possible universal Turing machine.

Screenshot:

Posted Image

Download:

AutoHotkey.net


Edit: Made the GUI realtime, made a fixed range display, improved GUI, optimized code

Edit: Added a status bar, detailing rules that the machine is following

Edit: Added easy window dragging code from my Awesome Windows script

Edit: Fixed broken link.

Edit: Complete core rewrite, better performance, fixed several obscure bugs in the display (off by one errors, etc.). Tried to make a save/restore system, but is removed for now, until issues can be resolved

Edit: Saves progress to a file on exit. Loads the file on startup if it exists. More restructuring.

Edit: Fixed broken link.

Edit: AHK_L compatible and GUI improvements. Moved to AutoHotkey.net

JoeSchmoe
  • Members
  • 304 posts
  • Last active: Feb 28 2013 05:39 PM
  • Joined: 17 Feb 2008
That's awesome.

I was hoping to see some sort of animation when I started the script, but didn't see anything. Am I missing somethng?

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Hmmm... Well, it currently doesn't have any animations as of yet, but I will add it in a half hour or so.

JoeSchmoe
  • Members
  • 304 posts
  • Last active: Feb 28 2013 05:39 PM
  • Joined: 17 Feb 2008
Animations are crowd pleasers in stuff like this. :-) I want to watch it think....

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Updated first post to integrate suggestions. See note at bottom of the post for details regarding changes.

JoeSchmoe
  • Members
  • 304 posts
  • Last active: Feb 28 2013 05:39 PM
  • Joined: 17 Feb 2008

Updated first post to integrate suggestions. See note at bottom of the post for details regarding changes.

Oh, wow. Much cooler. I approve. :D

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Update: Added status bar, improved GUI.

Also updated the screenshot.

JoeSchmoe
  • Members
  • 304 posts
  • Last active: Feb 28 2013 05:39 PM
  • Joined: 17 Feb 2008
Was going to ask for an example of a simple program to run on the Turing machine, but read the following in scientific American:

The 2,3 Turing machine described in the dense new 40-page proof "chews up a lot of tape" to perform even a simple job, Smith says. Programming it to calculate 2 + 2, he notes, would take up more memory than any known computer contains. And image processing? "It probably wouldn't finish before the end of the universe," he says.

Well then...

BTW, the Scientific American article provides great background explaining what this thing is, etc. and is very readable:
<!-- m -->http://www.scientifi... ... nce&page=1<!-- m -->

You can basically think of this script as simulating a computer that has only 3 machine code instructions and 1 bit of memory, but has been proven to be able to compute anything that any other computer in the world can computer, just much much more slowly.

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Thanks for the link, JoeShmoe.

It's more of a demo than anything, but it does make some inteersting patterns :lol: .

majkinetor
  • Moderators
  • 4512 posts
  • Last active: May 20 2019 07:41 AM
  • Joined: 24 May 2006
Great script. Thx m8.

BTW, I really doubt 2+2 would take that much time. While I was student we were doing simple Turing programs like that.
Posted Image

Uberi As Guest
  • Guests
  • Last active:
  • Joined: --

I happened to stumble across this excellent article at Wikipedia, and I thought it looked very interesting. It claims to be the "smallest possible universal Turing machine". I've implemented this in AHK:

NOTE: The original design has no halt state, so you need to set the number of iterations manually. It is already set to 100,000.

State = A
DefaultCell = 0
ProgramCode = 10122100012001222212102102010020102010210
ProgramOffset = -20

SetBatchLines, -1
Loop, Parse, ProgramCode
 Index := (A_Index - 1) + ProgramOffset, (Index < 0) ? Index := "_" . SubStr(Index,2) : "", Cell%Index% := A_LoopField

Gui, Color, Black
Gui, +ToolWindow +AlwaysOnTop +LastFound -Caption
WindowID := WinExist()
Gui, Font, s6 cWhite, Arial
Loop, 61
{
 XIndex := ((A_Index - 1) * 15) + 1
 Gui, Add, Progress, x%XIndex% y1 w14 h40 vCell%A_Index% BackgroundWhite
 Gui, Add, Text, x%XIndex% y42 w15 h10 vLabel%A_Index% Center, 200
}
Gui, Add, Text, x2 y54 w26 h10 vState
Gui, Add, Text, x35 y54 w50 h10 vCurrentCell
Gui, Add, Text, x350 y54 w158 h10 vActions
Gui, Add, Text, x844 y54 w33 h10, Iterations:
Gui, Add, Text, x884 y54 w29 h10 vIterations Right
Gui, Font, s4 cWhite Bold, Arial
Gui, Add, Text, x450 y1 w15 h10 Center, V
GuiControl, Move, Cell31, x451 y8 w14 h33
RuleA0 := "Print 1, Move right, Switch to state B", RuleA1 := "Print 2, Move left, Do not switch state", RuleA2 := "Print 1, Move left, Do not switch state", RuleB0 := "Print 2, Move left, Switch to state A", RuleB1 := "Print 2, Move right, Do not switch state", RuleB2 := "Print 0, Move right, Switch to state A"
Gui, Show, w916 h64, Wolfram's 2-State 3-Symbol Turing Machine

Index := 0, MaxIndex := Index, MinIndex := Index
Loop
{
 CurrentCell := Cell%Index%, (CurrentCell = "") ? (CurrentCell := DefaultCell) : "", (State = "A") ? ((CurrentCell = 0) ? (Direction := "Right", State := "B", CurrentCell := 1) : (Direction := "Left", State := "A", CurrentCell := !(CurrentCell - 1) + 1)) : ((CurrentCell = 0) ? (Direction := "Left", State := "A", CurrentCell := 2) : (Temp1 := !(CurrentCell - 1), Direction := "Right", State := Chr(65 + Temp1), CurrentCell := Temp1 * 2)), Cell%Index% := CurrentCell, (SubStr(Index,1,1) = "_") ? Index := "-" . SubStr(Index,2) : "", (Direction = "Left") ? Index -- : Index ++, (Index > MaxIndex) ? MaxIndex := Index : "", (Index < MinIndex) ? MinIndex := Index : "", (Index < 0) ? Index := "_" . SubStr(Index,2)
 GuiControl,, State, State: %State%
 GuiControl,, CurrentCell, Current Cell: %CurrentCell%
 GuiControl,, Actions, % "Actions: " . Rule%State%%CurrentCell%
 GuiControl,, Iterations, %A_Index% 
 Temp3 := ((SubStr(Index,1,1) = "_") ? SubStr(Index,2) * -1 : Index) - 31
 Loop, 61
 {
  Temp1 := Temp3 + A_Index, Temp2 := Temp1, (Temp1 < 0) ? Temp1 := "_" . SubStr(Temp1,2) : "", CurrentCell := Cell%Temp1%, CellColor := (CurrentCell = 1) ? "FF8800" : ((CurrentCell = 2) ? "Red" : "White")
  GuiControl, +Background%CellColor%, Cell%A_Index%
  GuiControl,, Label%A_Index%, %Temp2%
 }
 Sleep, 300
}

;Loop, % MaxIndex - MinIndex
 ;Index := (A_Index - 1) + MinIndex, (Index < 0) ? Index := "_" . SubStr(Index,2) : "", Result .= Cell%Index%

;Clipboard = %Result%
Return

~LButton::
CoordMode, Mouse, Relative
MouseGetPos, OffsetX, OffsetY, CurrentWin
CoordMode, Mouse
If CurrentWin <> %WindowID%
 Return
IfWinNotActive, ahk_id %CurrentWin%
 Return
SetTimer, MoveWin, 50
Return

MoveWin:
MouseGetPos, MouseX, MouseY
If Not GetKeyState("LButton")
{
 SetTimer, MoveWin, Off
 Return
}
Gui, +LastFound
WinGetPos, WinX, WinY, WinW, WinH
WinX -= OffsetX - MouseX, WinY -= OffsetY - MouseY
WinMove, WinX, WinY
Return

GuiEscape:
GuiClose:
ExitApp

And here is a screenshot:

Posted Image

Edit: Made the GUI realtime, made a fixed range display, improved GUI, optimized code

Edit: Added a status bar, detailing rules that the machine is following

Edit: Added easy window dragging code from my Awesome Windows script


Edit: Fixed broken link

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
Update: Rewrote the core for better performance, fixed some off-by-one errors in the GUI. See first post for more details, as well as the updated code.

It now uses a 2 dimensional array to get the instructions. Each iterations takes about 0.07 ms to complete, better than the 0.09 ms iteration time previously.

Uberi
  • Moderators
  • 1119 posts
  • Last active: May 02 2015 06:05 PM
  • Joined: 23 Aug 2010
More updates: See first post for details.

Most importantly, a save-file system is implemented, and some more off by one bugs in the iteration count were fixed.