Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 11-14-2018, 03:26 AM   #1
Aaron W.
Carpal \'Tunnel
 
Join Date: Sep 2002
Posts: 29,283
Pseudo-Turing Machine Problems/Puzzles

I've been kicking around an idea in my head for some programming challenges for introductory programming, and I think I need to hear input from other voices. From my past experiences, students at that level are simply quite sloppy in their thinking, and they just don't have a lot of mental organization. I'm trying to figure out how to fix that.

As I was thinking about this, I remembered a type of puzzle that was introduced to me a long time ago. It's basically a simplified model of a Turing machine. You have a finite strip of paper with special markings at the beginning and end to let you know that you've reached the ends. And you have a read/write head that just moves back and forth across that strip.

We're going to sweep the state table (the formal language/construct) under the rug and just proceed with a simple flowchart/pseudocode to explain what we're going to do. You can write any code you want, but you only have the following commands:

* Read/Write: Reads the value or writes a specific value in the position of the head. My memory was that you could only have the symbols 0 or 1, but that's not absolutely necessary.
* Left/Right: Moves the head left or right. If you attempt to move left when you're at the first position there's a feedback that lets you know you're at the beginning. And similarly on the end of the right side.

I don't remember being given any memory to work with, but that can be flexible.

And my recollection about this starts to run dry pretty quickly after that. I remember there being little puzzles. They all started with a random collection of 0s and 1s. For example:
* Move all the 1s to the left or right.
* Create alternating 0s and 1s (or determine this is not possible).
And... that's it.

The basic idea is that anyone can look at that and say "That's easy" but when you actually get them to explain how they would do it step-by-step (ie, using the four commands), they reach that level of cognitive dissonance where they *know* they can do it, but have a hard time explaining exactly what they're doing. And that's what forces them to really slow down and pick things apart more carefully.

So here are my questions:

1) Does anyone have any recollection of something like this? Maybe it was in a magazine or something? I don't think it was from a book or a textbook. There may even be lots of implementations of this idea floating around, and I just haven't looked in the right places.

2) Do you think that these puzzles could be beneficial to students? Or do you think it's "too much" or "too difficult" or "not in the right direction" to try to do this early on?

3) Can you think of any other programming puzzles that would make use this structure?

As far as implementing their plan, I have a pretty basic Python module that I think should do it.

Code:
class Turing:
    def __init__(self, length):
        self.tape = [0] * length
        self.position = 0
    
    def randomize(self):
        from random import randrange
        for position in range(len(self.tape)):
            self.tape[position] = randrange(2)
        self.display()
        return True
    
    def display(self):
        for symbol in self.tape:
            print(symbol, ' ', end='')
        print()
        for _ in range(self.position):
            print('   ', end='')
        print('^')
    
    def move_right(self):
        self.position += 1
        if(self.position) == len(self.tape):
            self.position -= 1
            print('End of Tape')
            self.display()
            return False
        self.display()
        return True

    def move_left(self):
        self.position -= 1
        if(self.position) == -1:
            self.position = 0
            print('End of Tape')
            self.display()
            return False
        self.display()
        return True
    
    def read(self):
        return self.tape[self.position]

    def write(self, value):
        if type(value) != type(0):
            print('You can only write integers')
            return False
        self.tape[self.position] = value
        return True
Aaron W. is offline   Reply With Quote
Old 11-14-2018, 04:18 AM   #2
leavesofliberty
Carpal \'Tunnel
 
Join Date: Jul 2010
Location: probably busto
Posts: 6,245
Re: Pseudo-Turing Machine Problems/Puzzles

Have not tried this, but ProLog might be what you seek.

https://en.wikipedia.org/wiki/Logic_programming
leavesofliberty is offline   Reply With Quote
Old 11-14-2018, 08:22 AM   #3
jukofyork
Carpal \'Tunnel
 
jukofyork's Avatar
 
Join Date: Sep 2004
Posts: 11,364
Re: Pseudo-Turing Machine Problems/Puzzles

Quote:
Originally Posted by Aaron W. View Post
1) Does anyone have any recollection of something like this? Maybe it was in a magazine or something? I don't think it was from a book or a textbook. There may even be lots of implementations of this idea floating around, and I just haven't looked in the right places.
Possibly it's the Scientific American articles from the 70's and 80's by Martin Gardner (and later by Alexander Dewdney), eg:

https://www.jstor.org/stable/2496942...n_tab_contents

Juk
jukofyork is offline   Reply With Quote
Old 11-15-2018, 12:45 AM   #4
Aaron W.
Carpal \'Tunnel
 
Join Date: Sep 2002
Posts: 29,283
Re: Pseudo-Turing Machine Problems/Puzzles

Quote:
Originally Posted by jukofyork View Post
Possibly it's the Scientific American articles from the 70's and 80's by Martin Gardner (and later by Alexander Dewdney), eg:

https://www.jstor.org/stable/2496942...n_tab_contents

Juk
Heh... it might well have been those. Thanks!
Aaron W. is offline   Reply With Quote
Old 11-15-2018, 04:05 AM   #5
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 30,137
Re: Pseudo-Turing Machine Problems/Puzzles

Quote:
Originally Posted by leavesofliberty View Post
Have not tried this, but ProLog might be what you seek.

https://en.wikipedia.org/wiki/Logic_programming
i wouldnt wish to inflict prolog on anyone :/
jmakin is offline   Reply With Quote
Old 11-15-2018, 04:39 PM   #6
river_tilt
adept
 
river_tilt's Avatar
 
Join Date: Apr 2006
Location: Swimming with sharks
Posts: 1,186
Re: Pseudo-Turing Machine Problems/Puzzles

I thought the busy beaver numbers had a state table. The n-th number is based on a n-state machine.

Chaitin's number is also quite an interesting idea in this area.
river_tilt is offline   Reply With Quote
Old 11-15-2018, 11:12 PM   #7
codeartisan
centurion
 
codeartisan's Avatar
 
Join Date: Jun 2008
Posts: 153
Re: Pseudo-Turing Machine Problems/Puzzles

Quote:
Originally Posted by jmakin View Post
i wouldnt wish to inflict prolog on anyone :/
How many Prolog programmers does it take to change a lightbulb?
Yes.
codeartisan is offline   Reply With Quote
Old 11-16-2018, 08:20 AM   #8
jukofyork
Carpal \'Tunnel
 
jukofyork's Avatar
 
Join Date: Sep 2004
Posts: 11,364
Re: Pseudo-Turing Machine Problems/Puzzles

Quote:
Originally Posted by codeartisan View Post
How many Prolog programmers does it take to change a lightbulb?
Yes.
jukofyork is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 10:35 PM.


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online