Jp's Lab

(This is a response directed towards the user 'Forum_account', following the forum thread rooted at http://www.byond.com/members/DreamMakers/forum?id=753427.)

I think you're playing semantics. The halting problem is provably unsolvable in that it is undecideable, and if one assumes the Church-Turing thesis, all undecideable problems are uncomputable - that is, it's impossible to solve the problem, no matter what model of computation you use, because they're all equivalent to the Turing machine. I assumed that in your last post your point was that proved undecideability was not a sufficient condition for the halting problem to be considered proved unsolvable because there could be other modes of computation in which it isn't undecideable - something not Turing-equivalent. Did you perhaps mean something else, or were you pointing out that 'unsolvable' isn't a CS term? I thought it was pretty clear that what I meant by 'unsolvable' was 'it is impossible to write a program to do it in a finite amount of steps'.

I'm not talking in a completely precise manner here. I'm fully aware of that. There's a number of reasons - I'm an engineer, not an academic computer scientist, so I've not exactly been immersed in the pure light of mathematical algorithmic analysis, it's a public forum, not a scientific journal, and because the reason I brought up the matter was to demonstrate that yes, things can be impossible (the halting problem was the first thing that came to mind), and then I continued it because Falacy didn't think about the problem and I thought he could do with hearing about it and digging into it on his own time. I don't think picking apart minor issues in terminology (the biggest one being 'program' versus 'algorithm') in a forum post intended primarily to gently poke people with mathematics exactly constitutes a service to the community.

My intention wasn't to stroke my own ego - it's mostly that the 'nothing is impossible' attitude irritates me. I picked the Halting Problem because it's mathematically demonstrable and reasonably simple to understand, whereas something like Godel's Incompleteness Theorem is a bit trickier and the First Law of Thermodynamics is empirical in nature. The original post was only a few words long, for Eris' sake! It's kind of hard to fit ego-stroking into that many words.

And I'm not sure how it was presented in a way that "wouldn't help anyone here". There's enough there to make people like Falacy have a look into the matter and maybe learn something in the process.

Well, it's 8:27 PM on the 31st of May over here, so I figure I may as well let everyone know what I've managed to Get Done for IainPeregrine's excellent Get Something Done challenge.

For the TL;DR group amongst you, here's the link: http://www.byond.com/members/Jp/files/dreamcatcher.zip . That's a zipfile containing the source and a makefile for building the source. The makefile builds it using GNU flex and bison, which are freely available: flex, bison. Your local equivalent of lex or yacc may be appropriate - I don't know.

This is not likely to be easy to build on a Windows system, I'm afraid. For that matter, it's probably going to only be a bit easier for someone on a UNIX-like system to build. Rest assured that as of yet, Dreamcatcher does very little of use - you're not missing out.

Anyway, what was my Get Something Done project? Well, I described my original goals here. How well did I do?

Not so well, I'm afraid. I'd like to say that real life intervened, but while I'm busy, I wasn't so busy that I couldn't code. I was just lazy for most of this month. Sorry.

But I have done some work, and I've gone a bit beyond where I was last time I fiddled with this stuff.

Dreamcatcher as it is currently built is capable of extracting the object tree, including variables, from a single DM source file without preprocessor statements, procedures, or verbs. It only works on 'usual-ish' DM files - no braces for block structure, no spaces for indents. parent_type isn't understood, nor are some technically legal but kind of odd constructs, like leading derived types with a / character or using ? as an identifier. There are probably more restrictions I can't see because I'm right up against the code. Some of them are a matter of writing a few lines in the flex code, some of them are a little trickier.

So what can it do?

Well, this:



parses out to:

root
        a
                b
                        var
                                c
                d
                        e
                                var
                                        f
                var
                        a
                                b
                                        g
                var
                        d
                                e
                                        h
        i
                var
                        j
        k
                var
                        l

Notice that names that appear more than once aren't collapsed into a single instance (all those 'var' nodes), but that's mostly a matter of data representation. The current code is very proof-of-concept.

Is this at all useful? Probably not. But hopefully it'll lead to something more interesting.

void magic(char* c) {
        size_t len = strlen(c);
        char temp;
        short toggle = 0;
        
        for(size_t it = 0; it < len; it++) {
                for(size_t i = toggle; i < len - 1; i+=2) {
                        temp = c[i]; c[i] = c[i+1]; c[i+1] = temp;
                }
                
                toggle = (toggle+1)%2;
        }
}

An algorithm that may be useful to constructors of conveyor-belt-driven robot-sorters.

I blame Skyspark for this:


He's got me hooked on a generally-awesome game called Manufactoria, in which you construct programs out of conveyer belts.

That mess you see above interprets the string of dots in the robot being processed as a binary number and adds 1 to it.

definitions: definition definitions |

definition: IDENTIFIER NEWLINE definition_contents | IDENTIFIER '/' definition
definition_contents: INDENT definitions DEDENT |

That's a very simple grammar for something approaching the basics of a block structure language. Accepts these sorts of constructs:



See if you can figure out how it works. You read it like this:

definitions: definition definitions |

A 'definitions' is a 'definition' followed by a 'definitions', or it's nothing (':' is assignment, '|' is alternation)

definition: IDENTIFIER NEWLINE definition_contents | IDENTIFIER '/' definition

A 'definition' is an IDENTIFIER followed by NEWLINE followed by 'definition_contents' or an IDENTIFIER followed by the character / followed by a 'definition'.

definition_contents: INDENT definitions DEDENT |

A 'definition_contents' is an INDENT followed by a 'definitions' followed by a DEDENT

Note: Whether this works on tabs or braces or whatever is entirely dependent on the lexer - as long as it returns INDENT and DEDENT tokens when an indent or a dedent happens, it's all good. This also has a NEWLINE occurring before an INDENT and doesn't accept spurious newlines, which is sort of a problem